How to make my custom type to work with range-based for loops?
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()andX::end()that return something that acts like an iteratorCreate a free function
begin(X&)andend(X&)that return something that acts like an iterator, in the same namespace as your typeX.¹
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 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 { 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 {
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 {
auto r=*this;
while(n-->0 && !r.empty())
r=r.without_front();
return r;
}
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.
Is there a range class in C++11 for use with range based for loops?
The C++ standard library does not have one, but Boost.Range has boost::counting_range, which certainly qualifies. You could also use boost::irange, which is a bit more focused in scope.
C++20's range library will allow you to do this via view::iota(start, end).
Can range-based C++11 for do/check extra operations/conditions?
Unfortunately, you can't put the increment into the range based for loop. However, in your specific case - as std::vector stores its elements contigously in memory - you can simulate option 2 by falling back to pointers (thanks to @M.M and @Jarod42 for corrections and improvements):
for ( const int& val : v ) {
std::cout << "v at index " << &val-v.data() << " is " << val;
}
more generic:
for ( const auto& val : v ) {
std::cout << "v at index " << std::addressof(val)-v.data() << " is " << val;
}
The other thing you can do is to write a index_range class, that represents a collections of indexes over which you can iterate in your range based for loop:
struct index_range_it {
size_t idx;
size_t operator*(){
return idx;
}
index_range_it& operator++() {
idx++;
return (*this);
}
};
bool operator!=(index_range_it l,index_range_it r) {
return l.idx != r.idx;
}
struct index_range {
size_t size;
index_range_it end(){return index_range_it{size};}
index_range_it begin(){return index_range_it{0};}
};
int main()
{
for (auto i: index_range{v.size()}){
std::cout << "v at index " << i << " is " << v[i];
}
}
A full fledged implementation of this idea can be found e.g. here
Such a range can then also be composed to something, where the iterator returns a proxy object containing the index as well as a reference to the current object and with c++17's structured binding that would be even more convenient to use.
What is the correct way of using C++11's range-based for?
TL;DR: Consider the following guidelines:
For observing the elements, use the following syntax:
for (const auto& elem : container) // capture by const referenceIf the objects are cheap to copy (like
ints,doubles, etc.),
it's possible to use a slightly simplified form:for (auto elem : container) // capture by value
For modifying the elements in place, use:
for (auto& elem : container) // capture by (non-const) referenceIf the container uses "proxy iterators" (like
std::vector<bool>), use:for (auto&& elem : container) // capture by &&
Of course, if there is a need to make a local copy of the element inside the loop body, capturing by value (for (auto elem : container)) is a good choice.
Detailed Discussion
Let's start differentiating between observing the elements in the container
vs. modifying them in place.
Observing the elements
Let's consider a simple example:
vector<int> v = {1, 3, 5, 7, 9};
for (auto x : v)
cout << x << ' ';
The above code prints the elements (ints) in the vector:
1 3 5 7 9
Now consider another case, in which the vector elements are not just simple integers,
but instances of a more complex class, with custom copy constructor, etc.
// A sample test class, with custom copy semantics.
class X
{
public:
X()
: m_data(0)
{}
X(int data)
: m_data(data)
{}
~X()
{}
X(const X& other)
: m_data(other.m_data)
{ cout << "X copy ctor.\n"; }
X& operator=(const X& other)
{
m_data = other.m_data;
cout << "X copy assign.\n";
return *this;
}
int Get() const
{
return m_data;
}
private:
int m_data;
};
ostream& operator<<(ostream& os, const X& x)
{
os << x.Get();
return os;
}
If we use the above for (auto x : v) {...} syntax with this new class:
vector<X> v = {1, 3, 5, 7, 9};
cout << "\nElements:\n";
for (auto x : v)
{
cout << x << ' ';
}
the output is something like:
[... copy constructor calls for vector<X> initialization ...]
Elements:
X copy ctor.
1 X copy ctor.
3 X copy ctor.
5 X copy ctor.
7 X copy ctor.
9
As it can be read from the output, copy constructor calls are made during range-based for loop iterations.
This is because we are capturing the elements from the container by value
(the auto x part in for (auto x : v)).
This is inefficient code, e.g., if these elements are instances of std::string,
heap memory allocations can be done, with expensive trips to the memory manager, etc.
This is useless if we just want to observe the elements in a container.
So, a better syntax is available: capture by const reference, i.e. const auto&:
vector<X> v = {1, 3, 5, 7, 9};
cout << "\nElements:\n";
for (const auto& x : v)
{
cout << x << ' ';
}
Now the output is:
[... copy constructor calls for vector<X> initialization ...]
Elements:
1 3 5 7 9
Without any spurious (and potentially expensive) copy constructor call.
So, when observing elements in a container (i.e., for read-only access),
the following syntax is fine for simple cheap-to-copy types, like int, double, etc.:
for (auto elem : container)
Else, capturing by const reference is better in the general case,
to avoid useless (and potentially expensive) copy constructor calls:
for (const auto& elem : container)
Modifying the elements in the container
If we want to modify the elements in a container using range-based for,
the above for (auto elem : container) and for (const auto& elem : container)
syntaxes are wrong.
In fact, in the former case, elem stores a copy of the original
element, so modifications done to it are just lost and not stored persistently
in the container, e.g.:
vector<int> v = {1, 3, 5, 7, 9};
for (auto x : v) // <-- capture by value (copy)
x *= 10; // <-- a local temporary copy ("x") is modified,
// *not* the original vector element.
for (auto x : v)
cout << x << ' ';
The output is just the initial sequence:
1 3 5 7 9
Instead, an attempt of using for (const auto& x : v) just fails to compile.
g++ outputs an error message something like this:
TestRangeFor.cpp:138:11: error: assignment of read-only reference 'x'
x *= 10;
^
The correct approach in this case is capturing by non-const reference:
vector<int> v = {1, 3, 5, 7, 9};
for (auto& x : v)
x *= 10;
for (auto x : v)
cout << x << ' ';
The output is (as expected):
10 30 50 70 90
This for (auto& elem : container) syntax works also for more complex types,
e.g. considering a vector<string>:
vector<string> v = {"Bob", "Jeff", "Connie"};
// Modify elements in place: use "auto &"
for (auto& x : v)
x = "Hi " + x + "!";
// Output elements (*observing* --> use "const auto&")
for (const auto& x : v)
cout << x << ' ';
the output is:
Hi Bob! Hi Jeff! Hi Connie!
The special case of proxy iterators
Suppose we have a vector<bool>, and we want to invert the logical boolean state
of its elements, using the above syntax:
vector<bool> v = {true, false, false, true};
for (auto& x : v)
x = !x;
The above code fails to compile.
g++ outputs an error message similar to this:
TestRangeFor.cpp:168:20: error: invalid initialization of non-const reference of
type 'std::_Bit_reference&' from an rvalue of type 'std::_Bit_iterator::referen
ce {aka std::_Bit_reference}'
for (auto& x : v)
^
The problem is that std::vector template is specialized for bool, with an
implementation that packs the bools to optimize space (each boolean value is
stored in one bit, eight "boolean" bits in a byte).
Because of that (since it's not possible to return a reference to a single bit),vector<bool> uses a so-called "proxy iterator" pattern.
A "proxy iterator" is an iterator that, when dereferenced, does not yield an
ordinary bool &, but instead returns (by value) a temporary object,
which is a proxy class convertible to bool.
(See also this question and related answers here on StackOverflow.)
To modify in place the elements of vector<bool>, a new kind of syntax (using auto&&)
must be used:
for (auto&& x : v)
x = !x;
The following code works fine:
vector<bool> v = {true, false, false, true};
// Invert boolean status
for (auto&& x : v) // <-- note use of "auto&&" for proxy iterators
x = !x;
// Print new element values
cout << boolalpha;
for (const auto& x : v)
cout << x << ' ';
and outputs:
false true true false
Note that the for (auto&& elem : container) syntax also works in the other cases
of ordinary (non-proxy) iterators (e.g. for a vector<int> or a vector<string>).
(As a side note, the aforementioned "observing" syntax of for (const auto& elem : container) works fine also for the proxy iterator case.)
Summary
The above discussion can be summarized in the following guidelines:
For observing the elements, use the following syntax:
for (const auto& elem : container) // capture by const referenceIf the objects are cheap to copy (like
ints,doubles, etc.),
it's possible to use a slightly simplified form:for (auto elem : container) // capture by value
For modifying the elements in place, use:
for (auto& elem : container) // capture by (non-const) referenceIf the container uses "proxy iterators" (like
std::vector<bool>), use:for (auto&& elem : container) // capture by &&
Of course, if there is a need to make a local copy of the element inside the loop body, capturing by value (for (auto elem : container)) is a good choice.
Additional notes on generic code
In generic code, since we can't make assumptions about generic type T being cheap to copy, in observing mode it's safe to always use for (const auto& elem : container).
(This won't trigger potentially expensive useless copies, will work just fine also for cheap-to-copy types like int, and also for containers using proxy-iterators, like std::vector<bool>.)
Moreover, in modifying mode, if we want generic code to work also in case of proxy-iterators, the best option is for (auto&& elem : container).
(This will work just fine also for containers using ordinary non-proxy-iterators, like std::vector<int> or std::vector<string>.)
So, in generic code, the following guidelines can be provided:
For observing the elements, use:
for (const auto& elem : container)For modifying the elements in place, use:
for (auto&& elem : container)
Custom class range based for-loop over a 2D map
Yes, It can be done. You must introduce iterator functionality.
If you look in the CPP reference here, then you can see the requirements for the range based for loop in the explanation. Only 5 functions are needed.
Your class must have a
begin()function that returns a custom iteratorYour class must have a
end()function that returns a custom iteratorYour class must have a custom iterator and a function for dereferencing it
Your class must have a custom iterator and a function for incrementing it
Your class must have a custom iterator and a function for comparison
The implementation of a custom iterator is very simple.
You write 5 using statements to fulfill formal requirements. Then, you need to define the internal representation of your iterator, for example a pointer or a other iterator.
In the example below, we reuse the 2 iterators from the nested maps. An iterator to the outer map and an interator for the inner map. For easier implementation of functionality, we will also store a pointer to the surrounding custom class.
The increment (and decrement operation) causes a little bit more effort, because we need to handle the wrap around of the inner map iterator.
Example: If the inner iterator reaches the end, we must increment the outer iterator and then reset the inner iterator to the begin position.
I adedd also a decrement function which faces similar challenges.
By adding a difference function, I make the whole thing even sortable, by destroying the relation of the strings to the double. So, do not do that.
But with that function, we can easily implement space ship like comparision of iterators.
Please see one of many potential solutions below. I added some more functions for your convenience.
#include<string>
#include<map>
#include<iostream>
#include <iterator>
#include <algorithm>
#include <numeric>
using Map = std::map<std::string, double>;
using MapMap = std::map<std::string, Map>;
struct MyClass {
struct iterator; // Forward declaration
MapMap mp{};
bool empty() { return mp.empty(); }
size_t size() { return std::accumulate(mp.begin(), mp.end(), 0u, [](const size_t& sum, const auto& m) { return sum + m.second.size(); }); }
iterator begin() { return iterator(&mp, mp.begin()->second.begin(), mp.begin()); }
iterator end() { return iterator(&mp, ((--mp.end())->second).end(), mp.end()); }
// iterator stuff ---------------------------------------------------------------------------
struct iterator {
// Definitions ----------------
using iterator_category = std::bidirectional_iterator_tag;
using difference_type = std::ptrdiff_t;
using value_type = double;
using pointer = double*;
using reference = double&;
// Data
MapMap* outerMapPtr{}; // Reference to surrounding nested map
MapMap::iterator outerMapIterator{}; // Iterator to the outer part of the nesed map
Map::iterator innerMapIterator{}; // Iterator to the outer part of the nesed map
// Constructor for iterator. Take a pointer to the surrounding nested map and both iterators
iterator(MapMap* const mmSD, const Map::iterator& msdIter, const MapMap::iterator& mmsdIter) :
outerMapPtr(mmSD), innerMapIterator(msdIter), outerMapIterator(mmsdIter) {}
// Dereferencing
reference operator *() const { return innerMapIterator->second; }
reference operator->() const { return **this; }
// Comparison. Must be template, because the other iterator may be of different type
template <typename Iter>
bool operator != (const Iter& other) const { return(outerMapIterator != other.outerMapIterator) or (innerMapIterator != other.innerMapIterator); }
template <typename Iter>
bool operator == (const Iter& other) const { return(outerMapIterator == other.outerMapIterator) and (innerMapIterator == other.innerMapIterator); }
bool operator < (const iterator& other) const { return other - *this < 0; };
bool operator <= (const iterator& other) const { return other - *this <= 0; };
bool operator > (const iterator& other) const { return other - *this > 0; };
bool operator >= (const iterator& other) const { return other - *this >= 0; };
// Arithmetic operations
// A little bit complex
iterator operator ++() {
// If we are at the end with the outer iterator, we do nothing
if (outerMapPtr->empty() or (outerMapIterator != outerMapPtr->end())) {
// We want to increment the inner iterator. Before we do that, we check, if this is already at the end
if (innerMapIterator != outerMapIterator->second.end())
++innerMapIterator;
// So, now the innerMapIterator can be at the end, either from the beginning or after incrementing it
if (innerMapIterator == outerMapIterator->second.end()) {
// Increment outer iterator
++outerMapIterator;
// And reset the inner interator back to begin, but only if the outer iterator is not at the end now
if (outerMapIterator != outerMapPtr->end())
innerMapIterator = outerMapIterator->second.begin();
}
}
return *this;
}
iterator operator --() {
// No decrementation on empty container
if (not outerMapPtr->empty()) {
// If we are at the end of the outer iterator then decrement it
if (outerMapIterator == outerMapPtr->end())
--outerMapIterator;
// If we are not at the begin the inner iterator
if (innerMapIterator != outerMapIterator->second.begin())
--innerMapIterator;
else {
// Inner iterator was at begin, therefore also decrement outer one
if (outerMapIterator != outerMapPtr->begin()) {
--outerMapIterator;
innerMapIterator = outerMapIterator->second.end();
if (innerMapIterator != outerMapIterator->second.begin())
--innerMapIterator;
}
}
}
return *this;
}
// Derived functions
iterator operator++(int) { iterator tmp = *this; ++* this; return tmp; }
iterator operator--(int) { iterator tmp = *this; --* this; return tmp; }
iterator operator +(const difference_type& n) const {
iterator temp{ *this }; difference_type k{ n }; if (k > 0) while (k--)++temp; else while (k++)--temp; return temp;
}
iterator operator +=(const difference_type& n) {
difference_type k{ n }; if (k > 0) while (k--)++* this; else while (k++)--* this; return *this;
};
iterator operator -(const difference_type& n) const {
iterator temp{ *this }; difference_type k{ n }; if (k > 0) while (k--)--temp; else while (k++)++temp; return temp;
}
iterator operator -=(const difference_type& n) {
difference_type k{ n }; if (k > 0) while (k--)--* this; else while (k++)++* this; return *this;
};
// Difference. Very inefficient
difference_type operator-(const iterator& other) const {
difference_type result{};
// No subtraction on empty container
if (not outerMapPtr->empty()) {
int indexThis{ }, indexOther{ }, index{};
iterator current(outerMapPtr, outerMapPtr->begin()->second.begin(), outerMapPtr->begin());
iterator last(outerMapPtr, ((--outerMapPtr->end())->second).end(), outerMapPtr->end());
for (; current != last; ++current, ++index) {
if (current == *this)
indexThis = index;
if (current == other)
indexOther = index;
}
if (current == *this)
indexThis = index;
if (current == other)
indexOther = index;
if (indexThis >= 0 and indexOther >= 0)
result = indexThis - indexOther;
}
return result;
}
};
};
int main()
{
MyClass mycls;
mycls.mp["a"]["a"] = 1;
mycls.mp["a"]["b"] = 2;
mycls.mp["a"]["c"] = 3;
mycls.mp["b"]["a"] = 4;
mycls.mp["b"]["b"] = 5;
mycls.mp["b"]["c"] = 6;
Related Topics
Is It a Good Idea to Return " Const Char * " from a Function
Installing C++ Libraries on Os X
Mixing C++11 Atomics and Openmp
Loading 8 Chars from Memory into an _M256 Variable as Packed Single Precision Floats
Variadic Function Template with Pack Expansion Not in Last Parameter
Why Do Compilers Allow String Literals Not to Be Const
Too Many Initializers for 'Int [0]' C++
What am I Not Understanding About Getline+Strings
Using Class Name in a Class Template Without Template Parameters
How to Get Pkcs7_Sign Result into a Char * or Std::String
Linker Error When Calling a C Function from C++ Code in Different VS2010 Project
Is Accessing Data in the Heap Faster Than from the Stack
C++ Convert Vector<Int> to Vector<Double>
Detecting Constexpr with Sfinae
Is Storing an Invalid Pointer Automatically Undefined Behavior