3.4.2. Iterator Arithmetic

Incrementing an iterator moves the iterator one element at a time. All the library containers have iterators that support increment. Similarly, we can use == and != to compare two valid iterators (§ 3.4, p. 106) into any of the library container types.

Iterators for string and vector support additional operations that can move an iterator multiple elements at a time. They also support all the relational operators. These operations, which are often referred to as iterator arithmetic, are described in Table 3.7.

Table 3.7. Operations Supported by vector and string Iterators

Arithmetic Operations on Iterators

We can add (or subtract) an integral value and an iterator. Doing so returns an iterator positioned forward (or backward) that many elements. When we add or subtract an integral value and an iterator, the result must denote an element in the same vector (or string) or denote one past the end of the associated vector (or string). As an example, we can compute an iterator to the element nearest the middle of a vector:

// compute an iterator to the element closest to the midpoint of vi
auto mid= vi.begin() + vi.size() / 2;

If vi has 20 elements, then vi.size()/2 is 10. In this case, we’d set mid equal to vi.begin() + 10. Remembering that subscripts start at 0, this element is the same as vi[10], the element ten past the first.

In addition to comparing two iterators for equality, we can compare vector and string iterators using the relational operators (<, <=, >, >=). The iterators must be valid and must denote elements in (or one past the end of) the same vector or string. For example, assuming it is an iterator into the same vector as mid, we can check whether it denotes an element before or after mid as follows:

if (it < mid)
    // process elements in the first half of vi

We can also subtract two iterators so long as they refer to elements in, or one off the end of, the same vector or string. The result is the distance between the iterators. By distance we mean the amount by which we’d have to change one iterator to get the other. The result type is a signed integral type named difference_type . Both vector and string define difference_type. This type is signed, because subtraction might have a negative result.

Using Iterator Arithmetic

A classic algorithm that uses iterator arithmetic is binary search. A binary search looks for a particular value in a sorted sequence. It operates by looking at the element closest to the middle of the sequence. If that element is the one we want, we’re done. Otherwise, if that element is smaller than the one we want, we continue our search by looking only at elements after the rejected one. If the middle element is larger than the one we want, we continue by looking only in the first half. We compute a new middle element in the reduced range and continue looking until we either find the element or run out of elements.

We can do a binary search using iterators as follows:

// text must be sorted
// beg and end will denote the range we're searching
auto beg = text.begin(), end = text.end();
auto mid= text.begin() + (end - beg)/2; // original midpoint
// while there are still elements to look at and we haven't yet found sought
while (mid != end && *mid != sought) {
    if (sought < *mid)     // is the element we want in the first half?
        end = mid;         // if so, adjust the range to ignore the second half
    else                   // the element we want is in the second half
        beg = mid + 1;     // start looking with the element just after mid
    mid= beg + (end - beg)/2;  // new midpoint
}

We start by defining three iterators: beg will be the first element in the range, end one past the last element, and mid the element closest to the middle. We initialize these iterators to denote the entire range in a vector<string> named text.

Our loop first checks that the range is not empty. If mid is equal to the current value of end, then we’ve run out of elements to search. In this case, the condition fails and we exit the while. Otherwise, mid refers to an element and we check whether mid denotes the one we want. If so, we’re done and we exit the loop.

If we still have elements to process, the code inside the while adjusts the range by moving end or beg. If the element denoted by mid is greater than sought, we know that if sought is in text, it will appear before the element denoted by mid. Therefore, we can ignore elements after mid, which we do by assigning mid to end. If *mid is smaller than sought, the element must be in the range of elements after the one denoted by mid. In this case, we adjust the range by making beg denote the element just after mid. We already know that mid is not the one we want, so we can eliminate it from the range.

At the end of the while, mid will be equal to end or it will denote the element for which we are looking. If mid equals end, then the element was not in text.