Channels ▼

Andrew Koenig

Dr. Dobb's Bloggers

How C++ Reverse Iterators Represent Boundaries

July 02, 2014

Last week, we noted that we can use pointers to represent boundaries by taking the view that a pointer has the same representation as the boundary immediately preceding it, and by implication, that a boundary has the same representation as the pointer immediately following it. Let's continue by looking more closely at how these representations interact with reverse iterators.

Suppose that c is a container. Then we can access c's elements in order by writing

 
     for (auto it = c.begin(), it != c.end(); ++it)
           // access the element at *it
 

We can also access c's elements in reverse order by writing

 
     for (auto rt = c.rbegin(), rt != c.rend(); ++rt)
           // access the element at *it
 

Obviously, it and rt must have different types. If nothing else, giving them different types makes it possible for ++it to move it to the next element to the right, and for --rt to move rt to the next element to the left. No problem so far.

Where things get interesting is when we think about the value of c.rbegin(). Surely we would like that value to be the same as what we get when we convert c.end() to a reverse iterator. However, c.end() is an off-the-end iterator, which means that it does not refer to an element. In contrast, unless c is empty, c.rbegin() most definitely does refer to an element, namely the rightmost one! The implication seems to be that when we convert an iterator into the corresponding reverse iterator, we change the element to which the iterator refers.

How can such a design make sense? Surely an iterator should refer to the same element of a container regardless of the direction in which we are processing the container's elements!

Well — of course, it shouldn't; otherwise, I wouldn't have bothered to raise your expectations with that remark. The missing link is that when we think about iterators and directions together, we should be thinking about ranges, and when we think about ranges, we should be thinking about boundaries, not pointers.

The c.begin() and c.end() iterators do not exist in isolation; they work together to represent a range. When we think of them in that way, c.begin() really represents the boundary immediately to the left of the first element of c, and c.end() represents the boundary immediately to the right of c's last element. When we write c.rbegin(), we intend it to represent the same boundary — not necessarily the same element — as c.end(). In order to represent that boundary as a pointer, we want to use a pointer to the element immediately after the boundary, just as we do for c.begin(). Because we are now traversing c right to left, that element that we use to represent c.rbegin() is the one to the left of the boundary.

In short, although it may seem odd for c.begin() and c.rend() to refer to different positions in a container, and similarly, for c.rbegin() and c.end() to refer to different positions, this difference makes it possible for the c.begin()/c.end() pair to refer to the same range of elements as the c.rbegin()/c.rend() pair, albeit in the opposite order.

Next week, we'll look at some concrete examples of how to intermix iterators and reverse iterators, with an eye toward explaining why these forward/backward conversions are less confusing than they appear at first glance.

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 


Video