Data Structures in C++:Iterators
The iterator in C++ abstracts the notion of a position in the container. As we have already seen, there are several ways to obtain such a position. All containers provide begin and end member functions that return iterators representing the first item and end marker, respectively. Many containers provide a searching member function (e.g. set::find) that returns an iterator viewing the found item, or the end marker if the item is not found.
Throughout our discussion we have used iterator as a type. In reality, in C++, each container defines several iterator types, nested in the scope of the container, and these specific iterator types are used by the programmer instead of simply using the word iterator. For instance, if we have a vector<int>, the basic iterator type is vector<int>::iterator. The basic iterator can be used to traverse and change the contents of the container.
Another iterator type, vector<int>::const iterator, does not allow changes to the container on which the iterator is operating. All iterators are guaranteed to have at least the following set of operations:
• ++itr and itr++: advance the iterator itr to the next location. Both the prefix and postfix forms are available. This does not cause any change to the container.
• *itr: returns a reference to the container object that itr is currently represent- ing. The reference that is returned is modifiable for basic iterators, but is not modifiable (i.e. a constant reference) for const iterators.
• itr1==itr2: returns true if iterators itr1 and itr2 refer to the same position in the same container and false otherwise.
• itr1!=itr2: returns true if iterators itr1 and itr2 refer to different positions or different containers and false otherwise.
Some iterators efficiently support --itr and itr--. Those iterators are called bidirectional iterators. All of the iterators for the common containers vector, list, deque, set, and map are bidirectional.
Some iterators efficiently support both itr+=k and itr+k. Those iterators are called random-access iterators. itr+=k advances the iterator k positions. itr+k returns a new iterator that is k positions ahead of itr. Also supported by random-access iterators are itr-=k and itr-k, with obvious semantics, and itr1-itr2 which yields a separation dis- tance as an integer. The iterators for vector and deque support random access.
All C++ containers have two member functions, begin and end that return iterators. Each collection defines four member functions:
• iterator begin( )
• const iterator begin( ) const
• iterator end( )
• const iterator end( ) const
begin returns an iterator that is positioned at the first item in the container. end returns an iterator that is positioned at the end marker, which represents a position one past the last element in the container. On an empty container, begin and end return the same position. For random access iterators, the result of subtracting the return values of end and begin is always the size of the container.
Typically we initialize a local iterator to be a copy of the begin iterator, and have it step through the container, stopping as soon as it hits the endmarker.
As an example, Figure 42.5 shows a print function that prints the elements of any container, provided that the elements in the container have provided an operator<<. Note that we must use a const iterator to traverse the container, because the container is itself immutable in the scope of print. The test program illustrates five different containers that invoke the print function, along with the expected output (in comments). Observe that both set and multiset output in sorted order, with multiset allowing the second insertion of beta. Additionally, for map to be compatible with the print routine, we must provide an operator<< that works for the elements of the map, namely the appropriate pairs.
Sometimes it is important to be able to traverse a container in the reverse direction. Be- cause of the asymmetric nature of begin and end (representing the first element and the end marker, rather than the last element, respectively) this is cumbersome to do, even for bidirectional iterators. As a result, containers that support bidirectional iterators typically also provide a reverse iterator. The reverse iterator comes in two flavors: reverse iterator and const reverse iterator. For reverse iterators, ++ retreats one position toward the beginning, while -- advances one position toward the end. Container member functions rbegin and rend are used to obtain iterators representing the last element and the beginmarker, respectively. order.
As a result, the code in Figure 42.6 prints any container in reverse
Comments
Post a Comment