StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>It's very important to realize that Standard Library containers are semi-open ranges <code>[begin, end)</code>, i.e. you can iterate one-past-the-end. For bidirectional (and random) iterators you can also do <code>--end()</code> and come back from the brink. Dereferencing one-past-the-end by <code>*end()</code> is undefined behavior, and so is decrementing the begin iterator by <code>--begin()</code> or <code>begin() - 1</code>. There is only one exception to this: <code>std::forward_list</code> which has a non-dereferenceable iterator <code>before_begin()</code> that satisfies <code>++before_begin() == begin()</code> (but note that for a <code>forward_list</code> you cannot decrement <code>begin()</code> either).</p> <p>This fundamental asymmetry for bidirectional iterators means that reverse iterators are thin wrappers around regular iterators. In most Standard Library implementations they simply contain a copy <code>base_</code> of the underyling iterator. Incrementing a <code>std::reverse_iterator</code> calls something like <code>--base_; return *this;</code>, and dereferencing it does <code>auto old = base_; return *--old;</code>. At no point is the underlying iterator decremented to before <code>begin()</code>, and no dereferencing of <code>end()</code> is done that way.</p> <p>Below are the four ways to iterate over a container supporting bidirectional or random iterators, and the relations between the various iterators (<code>.base()</code> converts a <code>std::reverse_iterator</code> back to its underlying iterator)</p> <pre><code>#include <iomanip> #include <iostream> #include <iterator> #include <map> #include <string> int main() { auto c = std::map<int, std::string>{ {1, "hello"}, {2, "world"} }; { // 1) forward iteratation auto it = begin(c); for (; it != end(c); ++it){} std::cout << std::boolalpha << (it == c.rbegin().base()) << "\n"; } { // 2) meh, backward iteration auto it = end(c); for (; it != begin(c); --it){} std::cout << std::boolalpha << (it == c.rend().base()) << "\n"; } { // 2') better: reverse iteration auto it = c.rbegin(); for (; it != c.rend(); ++it){} std::cout << std::boolalpha << (it.base() == begin(c)) << "\n"; } { // 1') backward reverse, better avoid this auto it = c.rend(); for (; it != c.rbegin(); --it){} std::cout << std::boolalpha << (it.base() == end(c)) << "\n"; } } </code></pre> <p><a href="http://coliru.stacked-crooked.com/a/0b1279702f712c01" rel="nofollow"><strong>Live Example</strong></a></p> <p>If you have data structure that should support bidirectional iteration but there are no member iterators <code>.rbegin()</code> or <code>rend()</code>, you can easily define them yourself by <code>std::reverse_iterator(end())</code> and <code>std::reverse_iterator(begin())</code>, respectively (this is also the way the Standard Library usually implements them). </p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload