How to make my custom type to work with "range-based for loops"?

ereOn picture ereOn · Nov 17, 2011 · Viewed 94.6k times · Source

Like many people these days I have been trying the different features that C++11 brings. One of my favorites is the "range-based for loops".

I understand that:

for(Type& v : a) { ... }

Is equivalent to:

for(auto iv = begin(a); iv != end(a); ++iv)
{
  Type& v = *iv;
  ...
}

And that begin() simply returns a.begin() for standard containers.

But what if I want to make my custom type "range-based for loop"-aware?

Should I just specialize begin() and end()?

If my custom type belongs to the namespace xml, should I define xml::begin() or std::begin() ?

In short, what are the guidelines to do that?

Answer

Yakk - Adam Nevraumont picture Yakk - Adam Nevraumont · Jul 16, 2015

The standard has been changed since the question (and most answers) were posted in the resolution of this defect report.

The way to make a for(:) loop work on your type X is now one of two ways:

  • Create member X::begin() and X::end() that return something that acts like an iterator

  • Create a free function begin(X&) and end(X&) that return something that acts like an iterator, in the same namespace as your type X

And similar for const variations. This will work both on compilers that implement the defect report changes, and compilers that do not.

The objects returned do not have to actually be iterators. The for(:) loop, unlike most parts of the C++ standard, is specified to expand to something equivalent to:

for( range_declaration : range_expression )

becomes:

{
  auto && __range = range_expression ;
  for (auto __begin = begin_expr,
            __end = end_expr;
            __begin != __end; ++__begin) {
    range_declaration = *__begin;
    loop_statement
  }
}

where the variables beginning with __ are for exposition only, and begin_expr and end_expr is the magic that calls begin/end

The requirements on the begin/end return value are simple: You must overload pre-++, ensure the initialization expressions are valid, binary != that can be used in a boolean context, unary * that returns something you can assign-initialize range_declaration with, and expose a public destructor.

Doing so in a way that isn't compatible with an iterator is probably a bad idea, as future iterations of C++ might be relatively cavalier about breaking your code if you do.

As an aside, it is reasonably likely that a future revision of the standard will permit end_expr to return a different type than begin_expr. This is useful in that it permits "lazy-end" evaluation (like detecting null-termination) that is easy to optimize to be as efficient as a hand-written C loop, and other similar advantages.


¹ Note that for(:) loops store any temporary in an auto&& variable, and pass it to you as an lvalue. You cannot detect if you are iterating over a temporary (or other rvalue); such an overload will not be called by a for(:) loop. See [stmt.ranged] 1.2-1.3 from n4527.

² Either call the begin/end method, or ADL-only lookup of free function begin/end, or magic for C-style array support. Note that std::begin is not called unless range_expression returns an object of type in namespace std or dependent on same.


In the range-for expression has been updated

{
  auto && __range = range_expression ;
  auto __begin = begin_expr;
  auto __end = end_expr;
  for (;__begin != __end; ++__begin) {
    range_declaration = *__begin;
    loop_statement
  }
}

with the types of __begin and __end have been decoupled.

This permits the end iterator to not be the same type as begin. Your end iterator type can be a "sentinel" which only supports != with the begin iterator type.

A practical example of why this is useful is that your end iterator can read "check your char* to see if it points to '0'" when == with a char*. This allows a C++ range-for expression to generate optimal code when iterating over a null-terminated char* buffer.

struct null_sentinal_t {
  template<class Rhs,
    std::enable_if_t<!std::is_same<Rhs, null_sentinal_t>{},int> =0
  >
  friend bool operator==(Rhs const& ptr, null_sentinal_t) {
    return !*ptr;
  }
  template<class Rhs,
    std::enable_if_t<!std::is_same<Rhs, null_sentinal_t>{},int> =0
  >
  friend bool operator!=(Rhs const& ptr, null_sentinal_t) {
    return !(ptr==null_sentinal_t{});
  }
  template<class Lhs,
    std::enable_if_t<!std::is_same<Lhs, null_sentinal_t>{},int> =0
  >
  friend bool operator==(null_sentinal_t, Lhs const& ptr) {
    return !*ptr;
  }
  template<class Lhs,
    std::enable_if_t<!std::is_same<Lhs, null_sentinal_t>{},int> =0
  >
  friend bool operator!=(null_sentinal_t, Lhs const& ptr) {
    return !(null_sentinal_t{}==ptr);
  }
  friend bool operator==(null_sentinal_t, null_sentinal_t) {
    return true;
  }
  friend bool operator!=(null_sentinal_t, null_sentinal_t) {
    return false;
  }
};

live example of this.

Minimal test code is:

struct cstring {
  const char* ptr = 0;
  const char* begin() const { return ptr?ptr:""; }// return empty string if we are null
  null_sentinal_t end() const { return {}; }
};

cstring str{"abc"};
for (char c : str) {
    std::cout << c;
}
std::cout << "\n";

Here is a simple example.

namespace library_ns {
  struct some_struct_you_do_not_control {
    std::vector<int> data;
  };
}

Your code:

namespace library_ns {
  int* begin(some_struct_you_do_not_control& x){ return x.data.data(); }
  int* end(some_struct_you_do_not_control& x){ return x.data.data()+x.data.size(); }
  int const* cbegin(some_struct_you_do_not_control const& x){ return x.data.data(); }
  int* cend(some_struct_you_do_not_control const& x){ return x.data.data()+x.data.size(); }
  int const* begin(some_struct_you_do_not_control const& x){ return cbegin(x); }
  int const* end(some_struct_you_do_not_control const& x){ return cend(x); }
}

this is an example how you can augment a type you don't control to be iterable.

Here I return pointers-as-iterators, hiding the fact I have a vector under the hood.

For a type you do own, you can add methods:

struct egg {};
struct egg_carton {
  auto begin() { return eggs.begin(); }
  auto end() { return eggs.end(); }
  auto cbegin() const { return eggs.begin(); }
  auto cend() const { return eggs.end(); }
  auto begin() const { return eggs.begin(); }
  auto end() const { return eggs.end(); }
private:
  std::vector<egg> eggs;
};

here I reuse the vector's iterators. I use auto for brevity; in I'd have to be more verbose.

Here is a quick and dirty iterable range-view:

template<class It>
struct range_t {
  It b, e;
  It begin() const { return b; }
  It end() const { return e; }
  std::size_t size() const { return end()-begin(); }
  bool empty() const { return begin()==end(); }
 
  range_t without_back( std::size_t n = 1 ) const {
    n = (std::min)(n, size());
    return {begin(), end()-n};
  }
  range_t without_front( std::size_t n = 1 ) const {
    n = (std::min)(n, size());
    return {begin()+n, end()};
  }
  decltype(auto) front() const { return *begin(); }
  decltype(auto) back() const { return *(std::prev(end())); }
};
template<class C>
auto make_range( C&& c ) {
  using std::begin; using std::end;
  return range_t{ begin(c), end(c) };
}

using template class deduction.

std::vector<int> v{1,2,3,4,5};
for (auto x : make_range(v).without_front(2) ) {
  std::cout << x << "\n";
}

prints 3 4 5, skipping first 2.