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.
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.
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
.
Exercise 3.24: Redo the last exercise from § 3.3.3 (p. 105) using iterators.
Exercise 3.25: Rewrite the grade clustering program from § 3.3.3 (p. 104) using iterators instead of subscripts.
Exercise 3.26: In the binary search program on page 112, why did we write mid= beg + (end - beg) / 2;
instead of mid= (beg + end) /2;
?