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

Question

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 1

I tried doing it this way (sorry for the STL and std namespace):

#include <bits/stdc++.h>
using namespace std;

struct Student{
    int id;
    string name;
};

bool compareId(Student &s1, Student &s2)
{
    // Assuming unique ids
    return (s1.id < s2.id);
}

void showStudents(vector<Student> &students){
    for(auto &s: students){
        cout<< s.id << "\t" << s.name << endl;
    }
}

int main() {

    vector<Student> v1{
        Student{101, "Ramesh"},
        Student{103, "Shyam"},
        Student{102, "Pankaj"},
        Student{104, "Sai"},
    };

    showStudents(v1);

    sort(v1.begin(), v1.end(), compareId);

    cout<<"\nAfter sorting:"<<endl;
    showStudents(v1);

    return 0;
}

I got the output as:

101     Ramesh
103     Shyam
102     Pankaj
104     Sai

After sorting:
101     Ramesh
102     Pankaj
103     Shyam
104     Sai

Answer 2

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);

Answer 3

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,

for( range_declaration : range_expression )

unlike most parts of the C++ standard, is specified to expand to something equivalent to:

{
  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 c++17 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 c++11 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
  // C++20 only line: (off C++20 it generates a hard error)
  requires std::random_access_iterator<It>
  {
    return end()-begin(); // do not use distance: O(n) size() is toxic
  }

  bool empty() const { return begin()==end(); }
 
  range_t without_back() const {
    if(emptty()) return *this;
    return {begin(), std::prev(end())};
  }

  range_t without_back( std::size_t n ) const
  // C++20 only line: (see below)
  requires !std::random_access_iterator<It>
  {
    auto r=*this;
    while(n-->0 && !r.empty())
      r=r.without_back();
    return r;
  }

  range_t without_front() const {
    if(empty()) return *this;
    return {std::next(begin()), end()};
  }

  range_t without_front( std::size_t n ) const
  // C++20 only line: (see below)
  requires !std::random_access_iterator<It>
  {
    auto r=*this;
    while(n-->0 && !r.empty())
      r=r.without_front();
    return r;
  }

  // C++20 section:
  range_t without_back( std::size_t n ) const
  requires std::random_access_iterator<It>
  {
    n = (std::min)(n, size());
    return {b, e-n};
  }
  range_t without_front( std::size_t n ) const
  requires std::random_access_iterator<It>
  {
    n = (std::min)(n, size());
    return {b+n, e};
  }
  // end C++20 section


  decltype(auto) front() const { return *begin(); }
  decltype(auto) back() const { return *(std::prev(end())); }
};
template<class It>
range_t(It,It)->range_t<It>;
template<class C>
auto make_range( C&& c ) {
  using std::begin; using std::end;
  return range_t{ begin(c), end(c) };
}

using c++17 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.

Answer 4

I think I don't have anything to explain since the answers already do that. But I maybe have to cite this quote from the standard (N4885):

[stmt.ranged]/1: (emphasise mine)

The range-based for statement

for ( init-statement(opt) for-range-declaration :
      for-range-initializer 
    ) statement(possibly curly-braced)

is equivalent to:

   { // starts namespace scope of for-range-initializer

       init-statement; (opt)
       auto &&range = for-range-initializer ;
       auto begin = begin-expr ;
       auto end = end-expr ;
       for ( ; begin != end; ++begin ) 
       {
          for-range-declaration = * begin ;
          statement ;   
       }

    } // ends namespace scope of for-range-initializer

where

(1.1) if the for-range-initializer is an expression, it is regarded as if it were surrounded by parentheses (so that a comma operator cannot be reinterpreted as delimiting two init-declarators);

(1.2) range, begin, and end are variables defined for exposition only; and

(3.1) begin-expr and end-expr are determined as follows:

(1.3.1) if the for-range-initializer is an expression of array type R, begin-expr and end-expr are range and range+N, respectively, where N is the array bound. If R is an array of unknown bound or an array of incomplete type, the program is ill-formed;

(1.3.2) if the for-range-initializer is an expression of class type C, and [class.member.lookup] in the scope of C for the names begin and end each find at least one declaration, begin-expr and end-expr are range.begin() and range.end(), respectively;

(1.3.3) otherwise, begin-expr and end-expr are begin(range) and end(range), respectively, where begin and end undergo argument-dependent lookup ([basic.lookup.argdep]).

---

Note that strings, arrays, and all STL containers are iterable data structures, so they can be iterated over with the range-based for-loop already. In order to make a data structure iterable, it must work similarly to the existing STL iterators:

1- There must be begin and end methods that operate on that structure, either as members or as stand-alone functions, and that return iterators to the beginning and end of the structure.

2- The iterator itself must support an operator*() method, an operator !=() method, and an operator++(void) method, either as members or as stand-alone functions.

---

#include <iostream>
#include <vector>
#define print(me) std::cout << me << std::endl

template <class T>
struct iterator
{
    iterator(T* ptr) : m_ptr(ptr) {};
    bool operator!=(const iterator& end) const { return (m_ptr != end.m_ptr); }
    T operator*() const { return *m_ptr; }
    const iterator& operator++()
    {
        ++m_ptr;
        return *this;
    }

private:
    T* m_ptr;
};

template <class T, size_t N>
struct array
{
    typedef iterator<T> iterator;

    array(std::initializer_list<T> lst)
    {

        m_ptr = new T[N]{};
        std::copy(lst.begin(), lst.end(), m_ptr);
    };

    iterator begin() const { return iterator(m_ptr); }
    iterator end() const { return iterator(m_ptr + N); }

    ~array() { delete[] m_ptr; }

private:
    T* m_ptr;
};

int main()
{
    array<std::vector<std::string>, 2> str_vec{ {"First", "Second"}, {"Third", "Fourth"} };
    for(auto&& ref : str_vec)
        for (size_t i{}; i != ref.size(); i++) 
            print(ref.at(i));

      //auto &&range = str_vec;
      //auto begin = range.begin();
      //auto end = range.end();
      //for (; begin != end; ++begin)
      //{
         // auto&& ref = *begin;
         // for (size_t i{}; i != ref.size(); i++) 
         //     print(ref.at(i));
      //}
}

The output of this program is:

First Second Third Fourth

Answer 5

Inspired by BitTickler's comment about how to make it work for non-"container" types, here's a minimal example of something that works for doubles:

class dranged {
    double start, stop, step, cur;
    int index;

public:
    dranged(double start, double stop, double step) :
        start(start), stop(stop), step(step),
        cur(start), index(0) {}

    auto begin() { return *this; }
    auto end() { return *this; }

    double operator*() const { return cur; }

    auto& operator++() {
        index += 1;
        cur = start + step * index;
        return *this;
    }

    bool operator!=(const dranged &rhs) const {
        return cur < rhs.stop;
    }
};

Note that the use of < in the != operator maintains the correct invariant, but obviously assumes step is positive and wouldn't be appropriate everywhere a more general range would be. I've used an integer index to prevent propagation of floating point error, but have aimed for simplicity otherwise.

This can be used as:

double sum() {
    double accum = 0;
    for (auto val : dranged(0, 6.28, 0.1)) {
        accum += val;
    }
    return accum;
}

GCC and Clang both produce very reasonable code when compiled with optimisations (i.e. either -Os or above -O1 for GCC or -O2 for Clang).

Answer 6

I would like to elaborate some parts of @Steve Jessop's answer, for which at first I didn't understand. Hope it helps.

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!

---

https://en.cppreference.com/w/cpp/language/range-for :

• If ...
• If range_expression is an expression of a class type C that has both a member named begin and a member named end (regardless of the type or accessibility of such member), then begin_expr is __range.begin() and end_expr is __range.end();
• Otherwise, begin_expr is begin(__range) and end_expr is end(__range), which are found via argument-dependent lookup (non-ADL lookup is not performed).

For range-based for loop, member functions are selected first.

But for

using std::begin;
begin(instance);

ADL functions are selected first.

---

Example:

#include <iostream>
#include <string>
using std::cout;
using std::endl;

namespace Foo{
    struct A{
        //member function version
        int* begin(){
            cout << "111";
            int* p = new int(3);  //leak I know, for simplicity
            return p;
        }
        int *end(){
            cout << "111";
            int* p = new int(4);
            return p;
        }
    };

    //ADL version

    int* begin(A a){
        cout << "222";
        int* p = new int(5);
        return p;
    }

    int* end(A a){
        cout << "222";
        int* p = new int(6);
        return p;
    }

}

int main(int argc, char *args[]){
//    Uncomment only one of two code sections below for each trial

//    Foo::A a;
//    using std::begin;
//    begin(a);  //ADL version are selected. If comment out ADL version, then member functions are called.


//      Foo::A a;
//      for(auto s: a){  //member functions are selected. If comment out member functions, then ADL are called.
//      }
}

Answer 7

Chris Redford's answer also works for Qt containers (of course). Here is an adaption (notice I return a constBegin(), respectively constEnd() from the const_iterator methods):

class MyCustomClass{
    QList<MyCustomDatatype> data_;
public:    
    // ctors,dtor, methods here...

    QList<MyCustomDatatype>::iterator begin() { return data_.begin(); }
    QList<MyCustomDatatype>::iterator end() { return data_.end(); }
    QList<MyCustomDatatype>::const_iterator begin() const{ return data_.constBegin(); }
    QList<MyCustomDatatype>::const_iterator end() const{ return data_.constEnd(); }
};

Answer 8

Here, I am sharing the simplest example of creating custom type, that will work with "range-based for loop":

#include<iostream>
using namespace std;

template<typename T, int sizeOfArray>
class MyCustomType
{
private:
    T *data;
    int indx;
public:
    MyCustomType(){
        data = new T[sizeOfArray];
        indx = -1;
    }
    ~MyCustomType(){
        delete []data;
    }
    void addData(T newVal){
        data[++indx] = newVal;
    }

    //write definition for begin() and end()
    //these two method will be used for "ranged based loop idiom"
    T* begin(){
        return &data[0];
    }
    T* end(){
        return  &data[sizeOfArray];
    }
};
int main()
{
    MyCustomType<double, 2> numberList;
    numberList.addData(20.25);
    numberList.addData(50.12);
    for(auto val: numberList){
        cout<<val<<endl;
    }
    return 0;
}

Hope, it will be helpful for some novice developer like me :p :)
Thank You.

Answer 9

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;
}

Answer 10

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;
    }
}

Answer 11

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.