Previous Section
 < Free Open Study > 
Next Section


Iterators

In many data structures and containers, we need some idea of the position or location of an item in the structure. In C, and in C++ before the STL, the pointer met this need. Pointers have the advantage of speed but require great care to avoid pitfalls. The STL provides the iterator as a replacement for pointers that is as efficient as pointers but is much safer. Each STL container provides one or more iterator types appropriate to the internal structure of the container.

We have seen that iterators are objects that specify position in STL containers and allow STL algorithms to cycle through the items in a container. This is done through a common interface through which an iterator is manipulated. Specifically, every iterator type must support at least the following operations:

Prefix *

Dereference (access the item currently pointed to)

++

Increment (point to the next item)

Additional operations are required for different categories of iterators.

An essential point is that behavior defines iterators. Anything that acts like an iterator is an iterator. It turns out that a variable of type int* (pointer to int) can serve as an iterator for a built-in int array. This fact enables many of the generic STL algorithms to be used directly with built-in arrays. In contrast, a pointer cannot serve as an iterator into a list container. If the list object happens to be implemented with a linked list of dynamically allocated nodes, the pointer operation p++ almost certainly doesn't point to the next node in the linked list (because list nodes are not likely to reside in consecutive memory locations). Therefore, a class like list<int> supplies a data type list<int>::iterator, which overloads the ++ operator in its own way to advance the iterator to the next item in the list.

In summary, an iterator can be either an ordinary pointer (if the container is a built-in array) or an object of a class that defines pointer-like operations that meet the STL requirements.

Iterator Categories

Different STL containers have different properties, so iterators for the various containers also have different properties. Similarly, different STL algorithms require different properties of the iterators they use. For example, sorting a container requires random access; otherwise, performance suffers. Consequently, iterators are classified in increasing "strength" of properties into input iterators, output iterators, forward iterators, bidirectional iterators, and random access iterators. Figure A.1 displays the relationships among the iterator categories. As we'll see later, if an STL algorithm requires an iterator of a particular category, then the programmer can use an iterator of that category or of any stronger category, but not of a weaker category.

Below, the arrow means "is stronger than"

Random access Bidirectional Forward Input Output


Figure A.1: Relationships among iterator categories

Some additional types of iterators are reverse iterators, stream iterators, insertion iterators, and raw storage iterators. Reverse iterators allow iteration through containers from the back to the front. Stream iterators allow you to read and write files from STL algorithms. Insertion iterators allow adding new items to the container rather than overwriting the position referred to by the iterator. We are able to discuss only the first of these in the space of this appendix. However, the references at the end of the appendix allow you to explore the others and more.

Input Iterators

Input iterators can only be stepped forward by one item per step. Furthermore, they may be dereferenced only to fetch (but not store into) an item from a collection. Table A.1 displays the allowable operations on an input iterator.

Table A.1: Operations on Input Iterators

Below, r and r2 are input iterators.

*r

Provides read access to the item at the position denoted by r

r++

Steps r forward one position in the container; returns the old position

++r

Steps r forward one position in the container; returns the new position

r == r2

Returns true if r and r2 denote the same position, else returns false

r != r2

Returns true if r and r2 denote different positions, else returns false

An example of an input iterator is a stream iterator that treats the keyboard input stream as a "container" and iterates through the stream, fetching one input character after the next. (The iostream header file provides such iterators.) We do not explore input stream iterators in this appendix.

Output Iterators

As with input iterators, output iterators can only be stepped forward by one item per step. However, output iterators may be dereferenced only to store a value at (but not fetch a value from) the specified location. Table A.2 shows the allowable operations on an output iterator.

Table A.2: Operations on Output Iterators

Below, r is an output iterator.

*r = value

Stores value at the position denoted by r

r++

Steps r forward one position in the container; returns the old position

++r

Steps r forward one position in the container; returns the new position

At first, it might seem strange that we can modify something but not fetch it, but it begins to make more sense if you consider that output iterators are often used for sending data to an output stream such as cout. (The iostream header file provides output stream iterators.) The idea is to treat an output stream as a "container" of characters and, using an output iterator, write each new character to the stream, one by one. We do not discuss stream iterators further in this appendix.

Forward Iterators

We have looked at two categories of iterators that step forward through a container, one permitting only fetching, the other permitting only storing. Often we would like to both fetch and store a value at a particular position as we step through a container. Forward iterators allow us to do so. Specifically, the valid operations on a forward iterator are the same as those of an input iterator plus the ability to store into the referenced item (see Table A.3).

Table A.3: Operations on Forward Iterators

Below, r and r2 are forward iterators.

*r

Provides read access to the item at the position denoted by r

*r = value

Stores value at the position denoted by r

r++

Steps r forward one position in the container; returns the old position

++r

Steps r forward one position in the container; returns the new position

r == r2

Returns true if r and r2 denote the same position, else returns false

r != r2

Returns true if r and r2 denote different positions, else returns false

The following is a generic algorithm that illustrates the use of forward iterators.

    // In any container that supports forward iterators,
    // replace every occurrence of an x value by a y value.

    template <class ForwardIterator, class T>
    void replace( ForwardIterator first, ForwardIterator pastLast,
                  const T& x, const T& y)
    {
      while (first != pastLast)
      {
        if (*first == x)
          *first = y;
        ++first;
      }
    }

Notice that the second parameter, pastLast, must denote a position that is one past that of the last item to be considered. In other words, the replace function replaces items in the container beginning at the position denoted by first and continuing up to but not including the position denoted by pastLast. Alternatively, we can say it this way: The algorithm processes items in the range [first, pastLast), a mathematical notation meaning an interval that is closed on the left (it includes the left endpoint) but open on the right (it does not include the right endpoint).

A call to the replace function might look like this:

    list<int> 1st;
      
    replace(1st.begin(), 1st.end(), 25, 125);

Recall from earlier in this appendix that 1st.begin() returns the location of the first list item and 1st.end() returns the past-the-end location.

The STL implements algorithms such as replace with the weakest iterator that is capable of carrying out the task at hand. In replace, the forward iterator is sufficient. Any stronger iterator may be used where a forward iterator is specified.

Bidirectional Iterators

Bidirectional iterators have all the properties of forward iterators but allow backward as well as forward movement through a container (see Table A.4).

Table A.4: Operations on Bidirectional Iterators

To the operations on forward iterators, add the following operations.

r--

Steps r backward one position in the container; returns the old position

--r

Steps r backward one position in the container; returns the new position

Adding the decrement operator makes some algorithms easier to implement. We will see that all the STL containers support either bidirectional iterators or random access iterators. The list container provides bidirectional iterators. (Hence, some people like to think of list as an abstraction of a doubly-linked list because it allows efficient traversal in either direction.)

Random Access Iterators

Random access iterators have all the properties of bidirectional iterators but support additional operations to allow random (direct) access to any item in a container (see Table A.5).

Table A.5: Operations on Random Access Iterators

To the operations on bidirectional iterators, add the following operations.

r[i]

Provides indexed read or store access to the item at the position denoted by r

r += i

Steps r forward by i positions in the container

r -= i

Steps r backward by i positions in the container

r + i

Returns an iterator value that is i positions beyond r in the container

r - i

Returns an iterator value that is i positions prior to r in the container

r - r2

Returns the number of items that exist between the positions denoted by r and r2

r < r2

Returns true if and only if the position denoted by r is before the position denoted by r2

r > r2

Returns true if and only if the position denoted by r is after the position denoted by r2

r <= r2

Returns true if and only if the position denoted by r is not after the position denoted by r2

r >= r2

Returns true if and only if the position denoted by r is not before the position denoted by r2

The vector container provides random access iterators, which makes sense because vector is an abstraction of a one-dimensional array.

We have not yet mentioned reverse iterators, which are of considerable importance. We delay introducing these iterators until we discuss vector containers, because vector supports reverse iterators as well as random access iterators.



Previous Section
 < Free Open Study > 
Next Section
Converted from CHM to HTML with chm2web Pro 2.85 (unicode)