Simulating the range-based for loop's begin/end behavior

Question

Consider the specification of the range-based for loop's begin-expr and end-expr (N4140 [stmt.ranged]/p1). Given a range __range of type _RangeT,

begin-expr and end-expr are determined as follows:

if _RangeT is an array type, begin-expr and end-expr are __range and __range + __bound, respectively, where __bound is the array bound. If _RangeT is an array of unknown size or an array of incomplete type, the program is ill-formed;

if _RangeT is a class type, the unqualified-ids begin and end are looked up in the scope of class _RangeT as if by class member access lookup (3.4.5), and if either (or both) finds at least one declaration, begin-expr and end-expr are __range.begin() and __range.end(), respectively;

otherwise, begin-expr and end-expr are begin(__range) and end(__range), respectively, where begin and end are looked up in the associated namespaces (3.4.2). [ Note: Ordinary unqualified lookup (3.4.1) is not performed. —end note ]

Is it possible to simulate this exact behavior in ordinary C++ code? i.e., can we write a magic_begin and a magic_end function template such that

for(auto&& p : range_init) { /* statements */ }

and

{
    auto&& my_range = range_init;
    for(auto b = magic_begin(my_range), e = magic_end(my_range); b != e; ++b){
        auto&& p = *b;
        /* statements */
    }
}

always have the exact same behavior?

Non-answers include qualified calls to std::begin/std::end (doesn't handle the third bullet, among other things) and using std::begin; begin(range); because, among other things, that is ambiguous if ADL for begin finds an overload that's equally good as std::begin.

For illustration, given

namespace foo {
    struct A { int begin; }; 
    struct B { using end = int; };
    class C { int* begin(); int *end(); }; // inaccessible
    struct D { int* begin(int); int* end();};
    struct E {};

    template<class T> int* begin(T&) { return nullptr; }
    template<class T> int* end(T&) { return nullptr; }
}

foo::A a; foo::B b; foo::C c; foo::D d; foo::E e;

I want magic_begin(a)/magic_begin(b)/magic_begin(c)/magic_begin(d) to be a compile error, and magic_begin(e) to return (int*)nullptr.

You mean, you want magic_end to be a compile error for b, right? — Columbo
@Columbo Well, if we are following range-based for's spec, then both would be errors. But I'm happy with "at least one of magic_begin and magic_end result in an error". — T.C.
@Columbo Now you got me intrigued :) The ideal solution would work for both, but if you have one that works on all non-final classes I'll take it. — T.C.

Columbo Columbo · Accepted Answer · 2015-09-13T11:00:57

The following SFINAE-friendly approach seems to work as desired (see below for exceptions):

#include <type_traits>

namespace detail {
    struct empty {};
    template <typename T>
    using base = std::conditional_t<std::is_class<T>{} && not std::is_final<T>{},
                                    T, empty>;

    struct P1 {typedef int begin, end;};
    template <typename U>
    struct TestMemType : base<U>, P1 {
        template <typename T=TestMemType, typename=typename T::begin>
        static std::true_type test_begin(int);
        template <typename T=TestMemType, typename=typename T::end>
        static std::true_type test_end(int);

        static std::false_type test_begin(float), test_end(float);
    };

    template <typename T>
    constexpr bool hasMember = !decltype(TestMemType<T>::test_begin(0)){}
                            || !decltype(TestMemType<T>::test_end(0)){};

    //! Step 1
    template <typename T, std::size_t N>
    constexpr auto begin(int, T(&a)[N]) {return a;}
    template <typename T, std::size_t N>
    constexpr auto end(int, T(&a)[N]) {return a+N;}

    //! Step 2 - this overload is less specialized than the above.
    template <typename T>
    constexpr auto begin(int, T& a) -> decltype(a.begin()) {return a.begin();}
    template <typename T>
    constexpr auto end(int, T& a) -> decltype(a.end()) {return a.end();}

    //! Step 3
    namespace nested_detail {
        void begin(), end();
        template <typename T>
        constexpr auto begin_(T& a) -> decltype(begin(a)) {return begin(a);}
        template <typename T>
        constexpr auto end_(T& a) -> decltype(end(a)) {return end(a);}
    }
    template <typename T, typename=std::enable_if_t<not hasMember<std::decay_t<T>>>>
    constexpr auto begin(float, T& a) -> decltype(nested_detail::begin_(a))
    {return nested_detail::begin_(a);}
    template <typename T, typename=std::enable_if_t<not hasMember<std::decay_t<T>>>>
    constexpr auto end(float, T& a) -> decltype(nested_detail::end_(a))
    {return nested_detail::end_(a);}
}

template <typename T>
constexpr auto magic_begin(T& a) -> decltype(detail::begin(0, a))
{return detail::begin(0, a);}
template <typename T>
constexpr auto magic_end  (T& a) -> decltype(detail::end  (0, a))
{return detail::  end(0, a);}

Demo. Note that GCCs lookup is broken as it doesn't consider non-type names for typename T::begin in TestMemType::test_end/begin. A workaround sketch can be found here.

The check in step 2 requires that the class type be derivable, which implies that this method doesn't properly work with final classes or unions - if those have an inaccessible member with name begin/end.

Simulating the range-based for loop's begin/end behavior

2 Answers