Iterators

  • An iterator is simply an object that can iterate over elements. An iterator represents a certain position in a container and allows to navigate from element to element. An iterator is a pure abstraction, so anything that behaves like an iterator is an iterator!

  • An iterator must support these fundamental operations that define its behavior:

    • Operator * “dereferences” the iterator and returns the element at the current position.

    • Operator ++ moves the iterator to the next element. Most iterators also define the operator -- that moves the iterator to the previous element.

    • Operators == and != return whether two iterators represent the same position within a container.

    • Operator = assigns an iterator and sets the position of the element to which it refers.

    As you can see, iterators’ behavior is very much like that of pointers. But iterators let you work with more complicated data structures. Their real behavior and implementation depend on the data structure over which they iterate.

  • All container classes provide the same basic methods (member functions) that allow you to use iterators to navigate over their elements. The most important ones are begin and end.

    • begin returns an iterator that refers to the element at the beginning of the container.

    • end returns an iterator that represents the end of the container. This position is after the last element in the container.

      iterators.png

    As you can see, begin and end define a half-open range that includes the first element but excludes the last.

  • An implication of the behavior of begin and end is that you can write for loops that look like this.

    vector<int> numbers = {1, 2, 3, 4};
for (vector<int>::iterator itr = numbers.begin(); itr != numbers.end(); ++itr) {
    cout << *itr << " ";
}
cout << endl;

    The above code prints

    1 2 3 4

    With C++11, you can replace vector<int>::iterator with auto and the type of itr will be automatically determined.

    vector<int> numbers = {1, 2, 3, 4};
for (auto itr = numbers.begin(); itr != numbers.end(); ++itr) {
    cout << *itr << " ";
}
cout << endl;

    C++11 also introduced range-based for loops, so you can simplify your code even further as you iterate through elements in a container.

    vector<int> numbers = {1, 2, 3, 4};
for (auto number : numbers) {
    cout << number << " ";
}
cout << endl;

  • Every STL container defines two iterator types.

    • container::iterator provides read and write access to the container’s elements.

    • container::const_iterator provides read-only access to the container’s elements.

Iterator Categories

  • Iterators are divided into several categories based on their abilities. Each container class in the STL provides iterators that belong to one of the following three categories.

    • Forward iterators only have the basic abilities outlined in the beginning of this section. Iterators of the forward_list container class are forward iterators. The iterators of the container classes unordered_set, unordered_multiset, unordered_map and unordered_multimap are “at least” forward iterators.

    • Bidirectional iterators are able to iterate both forward and backward. Iterators of the container classes list, set, multiset, map and multimap are bidirectional iterators.

    • Random-access iterators have all the abilities of bidirectional iterators in addition to being able to perform random access. You can add and subtract offsets, compute distance between two random-access iterators and compare them using relational operators, such as < and >. Iterators of vector, deque, array and string are random-access iterators.

    In addition to the above categories, there are two other categories.

    • Input iterators provide read-only access while iterating forward. Input stream iterators are an example thereof.

    • Output iterators provide write-only access while iterating forward. Output stream iterators are an example thereof.

Iterator Functions

  • The C++ library provides some auxiliary functions for dealing with iterators.

  • advance() increments the position of an iterator passed as the argument.

  • next() and prev() return an iterator at the position before or after the iterator passed as the argument.

  • distance() processes the difference between two iterators.

  • iter_swap() swaps the values to which two iterators refer.

Iterator Adapters

  • Remember that anything that behaves as an iterator is an iterator. Conveniently, STL provides some special iterators that allow algorithms to operate in reverse, in insert mode and with streams.

  • Here is an example that inserts the elements of one vector in the middle of another:

    vector<int> numbers = {183, 203, 281, 370, 376};
vector<int> otherNumbers = {203, 280};
vector<int>::iterator it = find(numbers.begin(), numbers.end(), 281);
insert_iterator<vector<int>> insertIt(numbers, it);
copy(otherNumbers.begin(), otherNumbers.end(), insertIt);

    Whereas normally the std::copy function overwrites existing elements in the container, using an insert iterator allows us to instead insert new elements without erasing the old ones. So after calling std::copy, the numbers vector contains the elements {183, 203, 203, 280, 281, 370, 376}.

Reverse Iterators

  • Reverse iterators allow us to process elements in a container in reverse order.

  • Reverse iterators redefine increment and decrement operators so that they behave in reverse. Thus, if you use these iterators instead of ordinary iterators, algorithms process elements in reverse order.

  • All containers that provide bidirectional iterators also provide reverse iterators.

  • Here is an example of code that uses a reverse iterator to print the elements of a vector in reverse order:

    vector<int> numbers = {183, 203, 280, 281, 370, 376};
reverse_iterator<vector<int>::iterator> reverseIt;

for (reverseIt = numbers.rbegin(); reverseIt != numbers.rend(); ++reverseIt) {
    cout << *reverseIt << " ";
}

    The output is 376 370 281 280 203 183.

Insert Iterators

  • Insert iterators, also called inserters, are iterator adapters that transform an assignment of a new value into an insertion of that new value. By using insert iterators, algorithms can insert values when they would normally overwrite old ones.

  • All insert iterators are considered output iterators, so they provide only the ability to assign new values.

Stream Iterators

  • A stream iterator allows you to use a stream as a source or destination of algorithms. In particular, an input stream iterator can be used to read elements from an input stream (such as cin or an input file stream), and an ostream iterator can be used to write values to an output stream (such as cout or an output file stream).

  • Below is some of the interface provided by istream iterators:

    • istream_iterator<T>(istream) creates an istream iterator for an input stream (istream) and reads the first value.

    • istream_iterator<T>() creates an end-of-stream iterator.

    • *iter returns the value that was read before.

    • iter = value writes value to ostream, followed by delim if set. This is equivalent to ostream << value << delim.

    • ++iter reads the next value from the stream and returns its position.

    • iter++ reads the next value but returns an iterator for the previous value.

  • Below is some of the interface provided by ostream iterators:

    • ostream_iterator<T>(ostream) creates an ostream iterator for an output stream (ostream).

    • ostream_iterator<T>(ostream, delim) creates an ostream iterator for an output stream ostream, with const char* delim as the delimiter between the values.

    • iter = value writes value to ostream, followed by delim if set. This is equivalent to ostream << value << delim.

  • Consider this snippet of code for example:

    vector<int> inputNumbers;
copy(istream_iterator<int>(cin), istream_iterator<int>(),
     back_inserter(inputNumbers));

    It would read all integers from standard input and insert them in the inputNumbers vector.

  • Here’s another example and combines input stream iterators and output stream iterators:

    copy(istream_iterator<int>(cin), istream_iterator<int>(),
     ostream_iterator<int>(cout, "\n"));

    This example reads all integers from standard input and prints them to standard output separated by a newline character.

results matching ""

    No results matching ""