14
ITERATORS

Say “friend” and enter.
—J.R.R. Tolkein, The Lord of the Rings

Iterators are the STL component that provides the interface between containers and algorithms to manipulate them. An iterator is an interface to a type that knows how to traverse a particular sequence and exposes simple, pointer-like operations to elements.

Every iterator supports at least the following operations:

• Access the current element (operator*) for reading and/or writing
• Go to the next element (operator++)
• Copy construct

Iterators are categorized based on which additional operations they support. These categories determine which algorithms are available and what you can do with an iterator in your generic code. In this chapter, you’ll learn about these iterator categories, convenience functions, and adapters.

Iterator Categories

An iterator’s category determines the operations it supports. These operations include reading and writing elements, iterating forward and backward, reading multiple times, and accessing random elements.

Because code that accepts an iterator is usually generic, the iterator’s type is typically a template parameter that you can encode with concepts, which you learned about in “Concepts” on page 163. Although you probably won't have to interact with iterators directly (unless you’re writing a library), you’ll still need to know the iterator categories so you don’t try to apply an algorithm to inappropriate iterators. If you do, you’re likely to get cryptic compiler errors. Recall from “Type Checking in Templates” on page 161 that because of how templates instantiate, error messages generated from inappropriate type arguments are usually inscrutable.

Output Iterators

You can use an output iterator to write into and increment but nothing else. Think of an output iterator as a bottomless pit that you throw data into.

When using an output iterator, you write, then increment, then write, then increment, ad nauseam. Once you’ve written to an output iterator, you cannot write again until you’ve incremented at least once. Likewise, once you’ve incremented an output iterator, you cannot increment again before writing.

To write to an output iterator, dereference the iterator using the dereference operator (*) and assign a value to the resulting reference. To increment an output iterator, use operator++ or operator++(int).

Again, unless you’re writing a C++ library, it’s unlikely that you’ll have to implement your own output iterator types; however, you’ll use them quite a lot.

One prominent usage is writing into containers as if they were output iterators. For this, you use insert iterators.

Insert Iterators

An insert iterator (or inserter) is an output iterator that wraps a container and transforms writes (assignments) into insertions. Three insert iterators exist in the STL’s <iterator> header as class templates:

• std::back_insert_iterator
• std::front_insert_iterator
• std::insert_iterator

The STL also offers three convenience functions for building these iterators:

• std::back_inserter
• std::front_inserter
• std::inserter

The back_insert_iterator transforms iterator writes into calls to the container’s push_back, whereas front_insert_iterator calls to push_front. Both of these insert iterators expose a single constructor that accepts a container reference, and their corresponding convenience functions take a single argument. Obviously, the wrapped container must implement the appropriate method. For example, a vector won’t work with a front_insert_iterator, and a set won’t work with either of them.

The insert_iterator takes two constructor arguments: a container to wrap and an iterator pointing into a position in that container. The insert_iterator then transforms writes into calls to the container’s insert method, and it will pass the position you provided on construction as the first argument. For example, you use the insert_iterator to insert into the middle of a sequential container or to add elements into a set with a hint.

Listing 14-1 illustrates the basic usages of the three insert iterators by adding elements to a deque.

#include <deque>
#include <iterator>

TEST_CASE("Insert iterators convert writes into container insertions.") {
  std::deque<int> dq;
  auto back_instr = std::back_inserter(dq); ➊
  *back_instr = 2; ➋ // 2
  ++back_instr; ➌
  *back_instr = 4; ➍ // 2 4
  ++back_instr;

  auto front_instr = std::front_inserter(dq); ➎
  *front_instr = 1; ➏ // 1 2 4
  ++front_instr;

  auto instr = std::inserter(dq, dq.begin()+2); ➐
  *instr = 3; ➑ // 1 2 3 4
  instr++;

  REQUIRE(dq[0] == 1);
  REQUIRE(dq[1] == 2);
  REQUIRE(dq[2] == 3);
  REQUIRE(dq[3] == 4); ➒
}

Listing 14-1: Insert iterators convert writes into container insertions.

First, you build a back_insert_iterator with back_inserter to wrap a deque called dq ➊. When you write into the back_insert_iterator, it translates the write into a push_back, so the deque contains a single element, 2 ➋. Because output iterators require incrementing before you can write again, you follow with an increment ➌. When you write 4 to the back_insert_iterator, it again translates the write into a push_back so the deque contains the elements 2 4 ➍.

Next, you build a front_insert_iterator with front_inserter to wrap dq ➎. Writing 1 into this newly constructed inserter results in a call to push_front, so the deque contains the elements 1 2 4 ➏.

Finally, you build an insert_iterator with inserter by passing dq and an iterator pointing to its third element (4). When you write 3 into this inserter ➑, it inserts just before the element pointed to by the iterator you passed at construction ➐. This results in dq containing the elements 1 2 3 4 ➒.

Table 14-1 summarizes the insert iterators.

Table 14-1: Summary of Insert Iterators

Class	Convenience function	Delegated function	Example containers
back_insert_iterator	back_inserter	push_back	vectors, deques, lists
front_insert_iterator	front_inserter	push_front	deques, lists
insert_iterator	inserter	insert	vectors, deques, lists, sets

List of Supported Output Iterator Operations

Table 14-2 summarizes the output iterator’s supported operations.

Table 14-2: Output Iterator’s Supported Operations

Operation	Notes
*itr=t	Writes into the output iterator. After operation, iterator is incrementable but not necessarily dereferencable.
++itr itr++	Increments the iterator. After operation, iterator is either dereferencable or exhausted (past the end) but is not necessarily incrementable.
iterator-type{ itr }	Copy-constructs an iterator from itr.

Input Iterators

You can use an input iterator to read from, increment, and check for equality. It’s the foil to the output iterator. You can only iterate through an input iterator once.

The usual pattern when reading from an input iterator is to obtain a half-open range with a begin and an end iterator. To read through the range, you read the begin iterator using operator* followed by an increment with operator++. Next, you evaluate whether the iterator equals end. If it does, you’ve exhausted the range. If it doesn’t, you can continue reading/incrementing.

A canonical usage of an input iterator is to wrap a program’s standard input (usually the keyboard). Once you’ve read a value from standard input, it’s gone. You cannot go back to the beginning and replay. This behavior matches an input iterator’s supported operations really well.

In “A Crash Course in Iterators” on page 412, you learned that every container exposes iterators with begin/cbegin/end/cend methods. All of these methods are at least input iterators (and they might support additional functionality). For example, Listing 14-2 illustrates how to extract a range from a forward_list and manipulate the iterators manually for reading.

#include <forward_list>

TEST_CASE("std::forward_list begin and end provide input iterators") {
  const std::forward_list<int> easy_as{ 1, 2, 3 }; ➊
  auto itr = easy_as.begin(); ➋
  REQUIRE(*itr == 1); ➌
  itr++; ➍
  REQUIRE(*itr == 2);
  itr++;
  REQUIRE(*itr == 3);
  itr++;
  REQUIRE(itr == easy_as.end()); ➎
}

Listing 14-2: Interacting with input iterators from a forward_list

You create a forward_list containing three elements ➊. The container’s constness means the elements are immutable, so the iterators support only read operations. You extract an iterator with the begin method of forward_list ➋. Using operator*, you extract the element pointed to by itr ➌ and follow up with the obligatory incrementation ➍. Once you’ve exhausted the range by reading/incrementing, itr equals the end of the forward_list ➎.

Table 14-3 summarizes the input iterator’s supported operations.

Table 14-3: Input Iterator’s Supported Operations

Operation	Notes
*itr	Dereferences the pointed-to member. Might or might not be read-only.
itr->mbr	Dereferences the member mbr of the object pointed-to by itr.
++itr itr++	Increments the iterator. After operation, iterator is either dereferencable or exhausted (past the end).
itr1 == itr2 itr1 != itr2	Compares whether the iterators are equal (pointing to the same element).
iterator-type{ itr }	Copy-constructs an iterator from itr.

Forward Iterators

A forward iterator is an input iterator with additional features: a forward iterator can also traverse multiple times, default construct, and copy assign. You can use a forward iterator in place of an input iterator in all cases.

All STL containers provide forward iterators. Accordingly, the forward_list used in Listing 14-2 actually provides a forward iterator (which is also an input iterator).

Listing 14-3 updates Listing 14-2 to iterate over the forward_list multiple times.

TEST_CASE("std::forward_list’s begin and end provide forward iterators") {
  const std::forward_list<int> easy_as{ 1, 2, 3 }; ➊
  auto itr1 = easy_as.begin(); ➋
  auto itr2{ itr1 }; ➌
  int double_sum{};
  while (itr1 != easy_as.end()) ➍
    double_sum += *(itr1++);
  while (itr2 != easy_as.end()) ➎
    double_sum += *(itr2++);
  REQUIRE(double_sum == 12); ➏
}

Listing 14-3: Traversing a forward iterator twice

Again you create a forward_list containing three elements ➊. You extract an iterator called itr1 with the begin method of forward_list ➋, then create a copy called itr2 ➌. You exhaust itr1 ➍ and itr2 ➎, iterating over the range twice while summing both times. The resulting double_sum equals 12 ➏.

Table 14-4 summarizes the forward iterator’s supported operations.

Table 14-4: Forward Iterator’s Supported Operations

Operation	Notes
*itr	Dereferences the pointed-to member. Might or might not be read-only.
itr->mbr	Dereferences the member mbr of the object pointed-to by itr.
++itr itr++	Increments the iterator so it points to the next element.
itr1 == itr2 itr1 != itr2	Compares whether the iterators are equal (pointing to the same element).
iterator-type{}	Default constructs an iterator.
iterator-type{ itr }	Copy-constructs an iterator from itr.
itr1 = itr2	Assigns an iterator itr1 from itr2.

Bidirectional Iterators

A bidirectional iterator is a forward iterator that can also iterate backward. You can use a bidirectional iterator in place of a forward or input iterator in all cases.

Bidirectional iterators permit backward iteration with operator-- and operator—(int). The STL containers that provide bidirectional iterators are array, list, deque, vector, and all of the ordered associative containers.

Listing 14-4 illustrates how to iterate in both directions using the bidirectional iterator of list.

#include <list>

TEST_CASE("std::list begin and end provide bidirectional iterators") {
  const std::list<int> easy_as{ 1, 2, 3 }; ➊
  auto itr = easy_as.begin(); ➋
  REQUIRE(*itr == 1); ➌
  itr++; ➍
  REQUIRE(*itr == 2);
  itr--; ➎
  REQUIRE(*itr == 1); ➏
  REQUIRE(itr == easy_as.cbegin());
}

Listing 14-4: The std::list methods begin and end provide bidirectional iterators.

Here, you create a list containing three elements ➊. You extract an iterator called itr with the begin method of list ➋. As with the input and forward iterators, you can dereference ➌ and increment ➍ the iterator. Additionally, you can decrement the iterator ➎ so you can go back to elements you’ve already iterated over ➏.

Table 14-5 summarizes a bidirectional iterator’s supported operations.

Table 14-5: Bidirectional Iterator’s Supported Operations

Operation	Notes
*itr	Dereferences the pointed-to member. Might or might not be read-only.
itr->mbr	Dereferences the member mbr of the object pointed to by itr.
++itr itr++	Increments the iterator so it points to the next element.
--itr itr--	Decrements the iterator so it points to the previous element.
itr1 == itr2 itr1 != itr2	Compares whether the iterators are equal (pointing to the same element).
iterator-type{}	Default constructs an iterator.
iterator-type{ itr }	Copy-constructs an iterator from itr.
itr1 = itr2	Assigns an iterator itr1 from itr2.

Random-Access Iterators

A random-access iterator is a bidirectional iterator that supports random element access. You can use a random-access iterator in place of bidirectional, forward, and input iterators in all cases.

Random-access iterators permit random access with operator[] and also iterator arithmetic, such as adding or subtracting integer values and subtracting other iterators to find distances. The STL containers that provide random-access iterators are array, vector, and deque. Listing 14-5 illustrates how to access arbitrary elements using a random-access iterator from a vector.

#include <vector>

TEST_CASE("std::vector begin and end provide random-access iterators") {
  const std::vector<int> easy_as{ 1, 2, 3 }; ➊
  auto itr = easy_as.begin(); ➋
  REQUIRE(itr[0] == 1); ➌
  itr++; ➍
  REQUIRE(*(easy_as.cbegin() + 2) == 3); ➎
  REQUIRE(easy_as.cend() - itr == 2); ➏
}

Listing 14-5: Interacting with a random-access iterator

You create a vector containing three elements ➊. You extract an iterator called itr with the begin method of vector ➋. Because this is a random-access iterator, you can use operator[] to dereference arbitrary elements ➌. Of course, you can still increment the iterator using operator++ ➍. You can also add to or subtract from an iterator to access elements at a given offset ➎➏.

List of Supported Random-Access Iterator Operations

Table 14-6 summarizes the random-access iterator’s supported operations.

Table 14-6: Random-Access Iterator’s Supported Operations

Operation	Notes
itr[n]	Dereferences the element with index n.
itr+n itr-n	Returns the iterator at offset n from itr.
itr2-itr1	Computes the distance between itr1 and itr2.
*itr	Dereferences the pointed-to member. Might or might not be read-only.
itr->mbr	Dereferences the member mbr of the object pointed to by itr.
++itr itr++	Increments the iterator so it points to the next element.
--itr itr--	Decrements the iterator so it points to the previous element.
itr1 == itr2 itr1 != itr2	Compares whether the iterators are equal (pointing to the same element).
iterator-type{}	Default constructs an iterator.
iterator-type{ itr }	Copy-constructs an iterator from itr.
itr1 < itr2 itr1 > itr2 itr1 <= itr2 itr1 >= itr2	Performs the corresponding comparison to the iterators’ positions.

Contiguous Iterators

A contiguous iterator is a random-access iterator with elements adjacent in memory. For a contiguous iterator itr, all elements itr[n] and itr[n+1] satisfy the following relation for all valid selections of indices n and offsets i:

&itr[n] + i == &itr[n+i]

The vector and array containers provide contiguous iterators, but list and deque don’t.

Mutable Iterators

All forward iterators, bidirectional iterators, random-access iterators, and contiguous iterators can support read-only or read-and-write modes. If an iterator supports read and write, you can assign values to the references returned by dereferencing an iterator. Such iterators are called mutable iterators. For example, a bidirectional iterator that supports reading and writing is called a mutable bidirectional iterator.

In each of the examples so far, the containers used to underpin the iterators have been const. This produces iterators to const objects, which are of course not writable. Listing 14-6 extracts a mutable, random-access iterator from a (non-const) deque, allowing you to write into arbitrary elements of the container.

#include <deque>

TEST_CASE("Mutable random-access iterators support writing.") {
  std::deque<int> easy_as{ 1, 0, 3 }; ➊
  auto itr = easy_as.begin(); ➋
  itr[1] = 2; ➌
  itr++; ➍
  REQUIRE(*itr == 2); ➎
}

Listing 14-6: A mutable random-access iterator permits writing.

You construct a deque containing three elements ➊ and then obtain an iterator pointing to the first element ➋. Next, you write the value 2 to the second element ➌. Then, you increment the iterator so it points to the element you just modified ➍. When you dereference the pointed-to element, you get back the value you wrote in ➎.

Figure 14-1 illustrates the relationship between the input iterator and all its more featureful descendants.

Figure 14-1: Input iterator categories and their nested relationships

To summarize, the input iterator supports only read and increment. Forward iterators are also input iterators, so they also support read and increment but additionally allow you to iterate over their range multiple times (“multi-pass”). Bidirectional iterators are also forward iterators, but they additionally permit decrement operations. Random access iterators are also bidirectional iterators, but you can access arbitrary elements in the sequence directly. Finally, contiguous iterators are random-access iterators that guarantee their elements are contiguous in memory.

Auxiliary Iterator Functions

If you write generic code dealing with iterators, you should use auxiliary iterator functions from the <iterator> header to manipulate iterators rather than using the supported operations directly. These iterator functions perform common tasks of traversing, swapping, and computing distances between iterators. The major advantage of using the auxiliary functions instead of direct iterator manipulation is that the auxiliary functions will inspect an iterator’s type traits and determine the most efficient method for performing the desired operation. Additionally, auxiliary iterator functions make generic code even more generic because it will work with the widest range of iterators.

std::advance

The std::advance auxiliary iterator function allows you to increment or decrement by the desired amount. This function template accepts an iterator reference and an integer value corresponding to the distance you want to move the iterator:

void std::advance(InputIterator&➊ itr, Distance➋ d);

The InputIterator template parameter must be at least an input iterator ➊, and the Distance template parameter is usually an integer ➋.

The advance function doesn’t perform bounds checking, so you must ensure that you’ve not exceeded the valid range for the iterator’s position.

Depending on the iterator’s category, advance will perform the most efficient operation that achieves the desired effect:

Input iterator The advance function will invoke itr++ the correct number of times; dist cannot be negative.

Bidirectional iterator The function will invoke itr++ or itr-- the correct number of times.

Random access iterator It will invoke itr+=dist; dist can be negative.

Listing 14-7 illustrates how to use advance to manipulate a random-access iterator.

#include <iterator>

TEST_CASE("advance modifies input iterators") {
  std::vector<unsigned char> mission{ ➊
    0x9e, 0xc4, 0xc1, 0x29,
    0x49, 0xa4, 0xf3, 0x14,
    0x74, 0xf2, 0x99, 0x05,
    0x8c, 0xe2, 0xb2, 0x2a
  };
  auto itr = mission.begin(); ➋
  std::advance(itr, 4); ➌
  REQUIRE(*itr == 0x49);
  std::advance(itr, 4); ➍
  REQUIRE(*itr == 0x74);
  std::advance(itr, -8); ➎
  REQUIRE(*itr == 0x9e);
}

Listing 14-7: Using advance to manipulate a contiguous iterator

Here, you initialize a vector called mission with 16 unsigned char objects ➊. Next, you extract an iterator called itr using the begin method of mission ➋ and invoke advance on itr to advance four elements so it points at the fourth element (with value 0x49) ➌. You advance again four elements to the eighth element (with value 0x74) ➍. Finally, you invoke advance with −8 to retreat eight values, so the iterator again points to the first element (with value 0x9e) ➎.

std::next and std::prev

The std::next and std::prev auxiliary iterator functions are function templates that compute offsets from a given iterator. They return a new iterator pointing to the desired element without modifying the original iterator, as demonstrated here:

ForwardIterator std::next(ForwardIterator& itr➊, Distance d=1➋);
BidirectionalIterator std::prev(BidirectionalIterator& itr➌, Distance d=1➍);

The function next accepts at least a forward iterator ➊ and optionally a distance ➋, and it returns an iterator pointing to the corresponding offset. This offset can be negative if itr is bidirectional. The prev function template works like next in reverse: it accepts at least a bidirectional iterator ➌ and optionally a distance ➍ (which can be negative).

Neither next nor prev performs bounds checking. This means you must be absolutely sure that your math is correct and that you’re staying within the sequence; otherwise, you’ll get undefined behavior.

Listing 14-8 illustrates how to use next to obtain a new iterator pointing to the element at a given offset.

#include <iterator>

TEST_CASE("next returns iterators at given offsets") {
  std::vector<unsigned char> mission{
    0x9e, 0xc4, 0xc1, 0x29,
    0x49, 0xa4, 0xf3, 0x14,
    0x74, 0xf2, 0x99, 0x05,
    0x8c, 0xe2, 0xb2, 0x2a
  };
  auto itr1 = mission.begin(); ➊
  std::advance(itr1, 4); ➋
  REQUIRE(*itr1 == 0x49); ➌

  auto itr2 = std::next(itr1); ➍
  REQUIRE(*itr2 == 0xa4); ➎

  auto itr3 = std::next(itr1, 4); ➏
  REQUIRE(*itr3 == 0x74); ➐

  REQUIRE(*itr1 == 0x49); ➑
}

Listing 14-8: Using next to obtain offsets from an iterator

As in Listing 14-7, you initialize a vector containing 16 unsigned chars and extract an iterator itr1 pointing to the first element ➊. You use advance to increment the iterator four elements ➋ so it points to the element with the value 0x49 ➌. The first use of next omits a distance argument, which defaults to 1 ➍. This produces a new iterator, itr2, which is one past itr1 ➎.

You invoke next a second time with a distance argument of 4 ➏. This produces another new iterator, itr3, which points to four past the element of itr1 ➐. Neither of these invocations affects the original iterator itr1 ➑.

std::distance

The std::distance auxiliary iterator function enables you to compute the distance between two input iterators itr1 and itr2:

Distance std::distance(InputIterator itr1, InputIterator itr2);

If the iterators are not random access, itr2 must refer to an element after itr1. It’s a good idea to ensure that itr2 comes after itr1, because you’ll get undefined behavior if you accidentally violate this requirement and the iterators are not random access.

Listing 14-9 illustrates how to compute the distance between two random access iterators.

#include <iterator>

TEST_CASE("distance returns the number of elements between iterators") {
  std::vector<unsigned char> mission{ ➊
    0x9e, 0xc4, 0xc1, 0x29,
    0x49, 0xa4, 0xf3, 0x14,
    0x74, 0xf2, 0x99, 0x05,
    0x8c, 0xe2, 0xb2, 0x2a
  };
  auto eighth = std::next(mission.begin(), 8); ➋
  auto fifth = std::prev(eighth, 3); ➌
  REQUIRE(std::distance(fifth, eighth) == 3); ➍
}

Listing 14-9: Using distance to obtain the distance between iterators

After initializing your vector ➊, you create an iterator pointing to the eighth element using std::next ➋. You use std::prev on eighth to obtain an iterator to the fifth element by passing 3 as the second argument ➌. When you pass fifth and eighth as the arguments to distance, you get 3 ➍.

std::iter_swap

The std::iter_swap auxiliary iterator function allows you to swap the values pointed to by two forward iterators itr1 and itr2:

Distance std::iter_swap(ForwardIterator itr1, ForwardIterator itr2);

The iterators don’t need to have the same type, as long as their pointed-to types are assignable to one another. Listing 14-10 illustrates how to use iter_swap to exchange two vector elements.

#include <iterator>

TEST_CASE("iter_swap swaps pointed-to elements") {
  std::vector<long> easy_as{ 3, 2, 1 }; ➊
  std::iter_swap(easy_as.begin()➋, std::next(easy_as.begin(), 2)➌);
  REQUIRE(easy_as[0] == 1); ➍
  REQUIRE(easy_as[1] == 2);
  REQUIRE(easy_as[2] == 3);
}

Listing 14-10: Using iter_swap to exchange pointed-to elements

After you construct a vector with the elements 3 2 1 ➊, you invoke iter_swap on the first element ➋ and the last element ➌. After the exchange, the vector contains the elements 1 2 3 ➍.

Additional Iterator Adapters

In addition to insert iterators, the STL provides move iterator adapters and reverse iterator adapters to modify iterator behavior.

Move Iterator Adapters

A move iterator adapter is a class template that converts all iterator accesses into move operations. The convenience function template std::make_move_iterator in the <iterator> header accepts a single iterator argument and returns a move iterator adapter.

The canonical use of a move iterator adapter is to move a range of objects into a new container. Consider the toy class Movable in Listing 14-11, which stores an int value called id.

struct Movable{
  Movable(int id) : id{ id } { } ➊
  Movable(Movable&& m) {
    id = m.id; ➋
    m.id = -1; ➌
  }
  int id;
};

Listing 14-11: The Movable class stores an int.

The Movable constructor takes an int and stores it into its id field ➊. Movable is also move constructible; it will steal the id from its move-constructor argument ➋, replacing it with −1 ➌.

Listing 14-12 constructs a vector of Movable objects called donor and moves them into a vector called recipient.

#include <iterator>

TEST_CASE("move iterators convert accesses into move operations") {
  std::vector<Movable> donor; ➊
  donor.emplace_back(1); ➋
  donor.emplace_back(2);
  donor.emplace_back(3);
  std::vector<Movable> recipient{
    std::make_move_iterator(donor.begin()), ➌
    std::make_move_iterator(donor.end()),
  };
  REQUIRE(donor[0].id == -1); ➍
  REQUIRE(donor[1].id == -1);
  REQUIRE(donor[2].id == -1);
  REQUIRE(recipient[0].id == 1); ➎
  REQUIRE(recipient[1].id == 2);
  REQUIRE(recipient[2].id == 3);
}

Listing 14-12: Using the move iterator adapter to convert iterator operations into move operations

Here, you default construct a vector called donor ➊, which you use to emplace_back three Movable objects with id fields 1, 2, and 3 ➋. You then use the range constructor of vector with the begin and end iterators of donor, which you pass to make_move_iterator ➌. This converts all iterator operations into move operations, so the move constructor of Movable gets called. As a result, all the elements of donor are in a moved-from state ➍, and all the elements of recipient match the previous elements of donor ➎.

Reverse Iterator Adapters

A reverse iterator adapter is a class template that swaps an iterator’s increment and decrement operators. The net effect is that you can reverse the input to an algorithm by applying a reverse iterator adapter. One common scenario where you might want to use a reverse iterator is when searching backward from the end of a container. For example, perhaps you’ve been pushing logs onto the end of a deque and want to find the latest entry that meets some criterion.

Almost all containers in Chapter 13 expose reverse iterators with rbegin/rend/crbegin/crend methods. For example, you can create a container with the reverse sequence of another container, as shown in Listing 14-13.

TEST_CASE("reverse iterators can initialize containers") {
  std::list<int> original{ 3, 2, 1 }; ➊
  std::vector<int> easy_as{ original.crbegin(), original.crend() }; ➋
  REQUIRE(easy_as[0] == 1); ➌
  REQUIRE(easy_as[1] == 2);
  REQUIRE(easy_as[2] == 3);
}

Listing 14-13: Creating a container with the reverse of another container’s elements

Here, you create a list containing the elements 3 2 1 ➊. Next, you construct a vector with the reverse of the sequence by using the crbegin and crend methods ➋. The vector contains 1 2 3, the reverse of the list elements ➌.

Although containers usually expose reverse iterators directly, you can also convert a normal iterator into a reverse iterator manually. The convenience function template std::make_reverse_iterator in the <iterator> header accepts a single iterator argument and returns a reverse iterator adapter.

Reverse iterators are designed to work with half-open ranges that are exactly opposite of normal half-open ranges. Internally, a reverse half-open range has an rbegin iterator that refers to 1 past a half-open range’s end and an rend iterator that refers to the half-open range’s begin, as shown in Figure 14-2.

Figure 14-2: A reverse half-open range

However, these implementation details are all transparent to the user. The iterators dereference as you would expect. As long as the range isn’t empty, you can dereference the reverse-begin iterator, and it will return the first element. But you cannot dereference the reverse-end iterator.

Why introduce this representational complication? With this design, you can easily swap the begin and end iterators of a half-open range to produce a reverse half-open range. For example, Listing 14-14 uses std::make_reverse_iterator to convert normal iterators to reverse iterators, accomplishing the same task as Listing 14-13.

TEST_CASE("make_reverse_iterator converts a normal iterator") {
  std::list<int> original{ 3, 2, 1 };
  auto begin = std::make_reverse_iterator(original.cend()); ➊
  auto end = std::make_reverse_iterator(original.cbegin()); ➋
  std::vector<int> easy_as{ begin, end }; ➌
  REQUIRE(easy_as[0] == 1);
  REQUIRE(easy_as[1] == 2);
  REQUIRE(easy_as[2] == 3);
}

Listing 14-14: The make_reverse_iterator function converts a normal iterator to a reverse iterator

Pay special attention to the iterators you’re extracting from original. To create the begin iterator, you extract an end iterator from original and pass it to make_reverse_iterator ➊. The reverse iterator adapter will swap increment and decrement operators, but it needs to start in the right place. Likewise, you need to terminate at the original’s beginning, so you pass the result of cbegin to make_reverse_iterator to produce the correct end ➋. Passing these to the range constructor of easy_as ➌ produces identical results to Listing 14-13.

Summary

In this short chapter, you learned all the iterator categories: output, input, forward, bidirectional, random-access, and contiguous. Knowing the basic properties of each category provides you with a framework for understanding how containers connect with algorithms. The chapter also surveyed iterator adapters, which enable you to customize iterator behavior, and the auxiliary iterator functions, which help you write generic code with iterators.