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

ID : 10455

viewed : 28

Tags : c++for-loopc++11customizationc++17c++

Top 5 Answer for c++ - How to make my custom type to work with "range-based for loops"?

vote vote

93

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.

vote vote

83

I write my answer because some people might be more happy with simple real life example without STL includes.

I have my own plain only data array implementation for some reason, and I wanted to use the range based for loop. Here is my solution:

 template <typename DataType>  class PodArray {  public:    class iterator {    public:      iterator(DataType * ptr): ptr(ptr){}      iterator operator++() { ++ptr; return *this; }      bool operator!=(const iterator & other) const { return ptr != other.ptr; }      const DataType& operator*() const { return *ptr; }    private:      DataType* ptr;    };  private:    unsigned len;    DataType *val;  public:    iterator begin() const { return iterator(val); }    iterator end() const { return iterator(val + len); }     // rest of the container definition not related to the question ...  }; 

Then the usage example:

PodArray<char> array; // fill up array in some way for(auto& c : array)   printf("char: %c\n", c); 
vote vote

77

The relevant part of the standard is 6.5.4/1:

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 with argument-dependent lookup (3.4.2). For the purposes of this name lookup, namespace std is an associated namespace.

So, you can do any of the following:

  • define begin and end member functions
  • define begin and end free functions that will be found by ADL (simplified version: put them in the same namespace as the class)
  • specialize std::begin and std::end

std::begin calls the begin() member function anyway, so if you only implement one of the above, then the results should be the same no matter which one you choose. That's the same results for ranged-based for loops, and also the same result for mere mortal code that doesn't have its own magical name resolution rules so just does using std::begin; followed by an unqualified call to begin(a).

If you implement the member functions and the ADL functions, though, then range-based for loops should call the member functions, whereas mere mortals will call the ADL functions. Best make sure they do the same thing in that case!

If the thing you're writing implements the container interface, then it will have begin() and end() member functions already, which should be sufficient. If it's a range that isn't a container (which would be a good idea if it's immutable or if you don't know the size up front), you're free to choose.

Of the options you lay out, note that you must not overload std::begin(). You are permitted to specialize standard templates for a user-defined type, but aside from that, adding definitions to namespace std is undefined behavior. But anyway, specializing standard functions is a poor choice if only because the lack of partial function specialization means you can only do it for a single class, not for a class template.

vote vote

69

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

As far as I know, that is enough. You also have to make sure that incrementing the pointer would get from the begin to the end.

Next example (it is missing const version of begin and end) compiles and works fine.

#include <iostream> #include <algorithm>  int i=0;  struct A {     A()     {         std::generate(&v[0], &v[10], [&i](){  return ++i;} );     }     int * begin()     {         return &v[0];     }     int * end()     {         return &v[10];     }      int v[10]; };  int main() {     A a;     for( auto it : a )     {         std::cout << it << std::endl;     } } 

Here is another example with begin/end as functions. They have to be in the same namespace as the class, because of ADL :

#include <iostream> #include <algorithm>   namespace foo{ int i=0;  struct A {     A()     {         std::generate(&v[0], &v[10], [&i](){  return ++i;} );     }      int v[10]; };  int *begin( A &v ) {     return &v.v[0]; } int *end( A &v ) {     return &v.v[10]; } } // namespace foo  int main() {     foo::A a;     for( auto it : a )     {         std::cout << it << std::endl;     } } 
vote vote

50

In case you want to back a class's iteration directly with its std::vector or std::map member, here is the code for that:

#include <iostream> using std::cout; using std::endl; #include <string> using std::string; #include <vector> using std::vector; #include <map> using std::map;   ///////////////////////////////////////////////////// /// classes /////////////////////////////////////////////////////  class VectorValues { private:     vector<int> v = vector<int>(10);  public:     vector<int>::iterator begin(){         return v.begin();     }     vector<int>::iterator end(){         return v.end();     }     vector<int>::const_iterator begin() const {         return v.begin();     }     vector<int>::const_iterator end() const {         return v.end();     } };  class MapValues { private:     map<string,int> v;  public:     map<string,int>::iterator begin(){         return v.begin();     }     map<string,int>::iterator end(){         return v.end();     }     map<string,int>::const_iterator begin() const {         return v.begin();     }     map<string,int>::const_iterator end() const {         return v.end();     }      const int& operator[](string key) const {         return v.at(key);     }     int& operator[](string key) {         return v[key];     }  };   ///////////////////////////////////////////////////// /// main /////////////////////////////////////////////////////  int main() {     // VectorValues     VectorValues items;     int i = 0;     for(int& item : items) {         item = i;         i++;     }     for(int& item : items)         cout << item << " ";     cout << endl << endl;      // MapValues     MapValues m;     m["a"] = 1;     m["b"] = 2;     m["c"] = 3;     for(auto pair: m)         cout << pair.first << " " << pair.second << endl; } 

Top 3 video Explaining c++ - How to make my custom type to work with "range-based for loops"?

Related QUESTION?