ccplusplus.com: iterator category c++

Iterator Categories C++ : Standard Template Library Tutorial, ccplusplus.com

Iterator Categories

Iterators are objects that can iterate over elements of a sequence. They do this via a common interface that is adapted from ordinary pointers. Iterators follow the concept of pure abstraction: Anything that behaves like an iterator is an iterator. However, iterators have different abilities. These abilities are important because some algorithms require special iterator abilities. For example, sorting algorithms require iterators that can perform random access because otherwise the run-time would be poor. For this reason, iterators have different categories (figure below). The abilities of these categories are listed in table below, and discussed in the following coming posts.

Figure:- Iterator Categories

Table:- Abilities of Iterator Categories
Iterator Category	Ability	Providers
Input iterator	Reads forward	istream
Output iterator	Writes forward	ostream, inserter
Forward iterator	Reads and writes forward
Bidirectional iterator	Reads and writes forward and backward	list, set, multiset, map, multimap
Random access iterator	Reads and writes with random access	vector, deque string, array

Input Iterators

Input iterators can only step forward element-by-element with read access. Thus, they return values elementwise. Table below lists the operations of input iterators.

Note that input iterators can read elements only once. Thus, if you copy an input iterator and let the original and the copy read forward, they might iterate over different values.

Almost all iterators have the abilities of input iterators. However, usually they can have more. A typical example of a pure input iterator is an iterator that reads from the standard input (typically the keyboard). The same value can't be read twice. After a word is read from an input stream (out of the input buffer), the next read access returns another word.

Two input iterators are equal if they occupy the same position. However, as stated previously, this does not mean that they return the same value on element access.

Table:- Operations of Input Iterators
Expression	Effect
*iter	Provides read access to the actual element
iter ->member	Provides read access to a member (if any) of the actual element
++iter	Steps forward (returns new position)
iter++	Steps forward (returns old position)
Iter1 == iter2	Returns whether two iterators are equal
Iter1 != iter2	Returns whether two iterators are not equal
TYPE(iter)	Copies iterator (copy constructor)

You should always prefer the preincrement operator over the postincrement operator because it might perform better. This is because the preincrement operator does not have to return an old value that must be stored in a temporary object. So, for any iterator pos (and any abstract data type), you should prefer

rather than

The same applies to decrement operators, as long as they are defined (they aren't for input iterators).

Output Iterators

Output iterators are the counterparts of input iterators. They can only step forward with write access. Thus, you can assign new values only element-by-element. You can't use an output iterator to iterate twice over the same range. The goal is to write a value into a "black hole" (whatever that means). So, if you write something for the second time at the same position into the same black hole, it is not guaranteed that you will overwrite a previous value. Table below lists the valid operations for output iterators. The only valid use of operator * is on the left side of an assignment statement.

Table:- Operations of Output Iterators
Expression	Effect
*iter = value	Writes value to where the iterator refers
++iter	Steps forward (returns new position)
iter++	Steps forward (returns old position)
TYPE (iter)	Copies iterator (copy constructor)

Note that no comparison operations are required for output iterators. You can't check whether an output iterator is valid or whether a "writing" was successful. The only thing you can do is to write, and write, and write values.

Usually iterators can read and write values. So, as for input iterators, almost all iterators also have the abilities of output iterators. A typical example of a pure output iterator is an iterator that writes to the standard output (for example, to the screen or a printer). If you use two output iterators to write to the screen, the second word follows the first rather than overwriting it. Another typical example of output iterators are inserters. Inserters are iterators that insert values into containers. If you assign a value, you insert it. If you then write a second value, you don't overwrite the first value; you just also insert it.

Forward Iterators

Forward iterators are combinations of input and output iterators. They have all the abilities of input iterators and most of those of output iterators. Table below summarizes the operations of forward iterators.

Table :- Operations of Forward Iterators
Expression	Effect
*iter	Provides access to the actual element
iter-> member	Provides access to a member of the actual element
++iter	Steps forward (returns new position)
iter++	Steps forward (returns old position)
iter1 == iter2	Returns whether two iterators are equal
iter1 != iter2	Returns whether two iterators are not equal
TYPE()	Creates iterator (default constructor)
TYPE(iter)	Copies iterator (copy constructor)
iter1 = iter2	Assigns an iterator

Unlike input iterators and output iterators, forward iterators can refer to the same element in the same collection and process the same element more than once. You might wonder why a forward iterator does not have all of the abilities of an output iterator. One restriction applies that prohibits valid code for output iterators from being valid for forward iterators:

For output iterators, writing data without checking for the end of a sequence is correct. In fact, you can't compare an output iterator with an end iterator because output iterators do not have to provide a comparison operation. Thus, the following loop is correct for output iterator pos:

//OK for output iterators //ERROR for forward iterators while (true) { *pos = foo(); ++pos; }
For forward iterators, you must ensure that it is correct to dereference (access the data) before you do this. Thus, the previous loop is not correct for forward iterators. This is because it would result in dereferencing the end() of a collection, which results in undefined behavior. For forward iterators, the loop must be changed in the following manner:

//OK for forward iterators //IMPOSSIBLE for output iterators while (pos != coll.end()) { *pos = foo(); ++pos; }

This loop does not compile for output iterators because operator ! = is not defined for them.

Bidirectional Iterators

Bidirectional iterators are forward iterators that provide the additional ability to iterate backward over the elements. Thus, they provide the decrement operator to step backward (table below).

Table :- Additional Operations of Bidirectional Iterators
Expression	Effect
-- iter	Steps backward (returns new position)
iter--	Steps backward (returns old position)

Random Access Iterators

Random access iterators are bidirectional iterators that can perform random access. Thus, they provide operators for "iterator arithmetic" (in accordance with the "pointer arithmetic" of ordinary pointers). That is, they can add and subtract offsets, process differences, and compare iterators with relational operators such as < and >. Table lists the additional operations of random access iterators.

Random access iterators are provided by the following objects and types:

Containers with random access (vector, deque)
Strings (string, wstring)
Ordinary arrays (pointers)

Table:- Additional Operations of Random Access Iterators
Expression	Effect
iter[n]	Provides access to the element that has index n
iter+=n	Steps n elements forward (or backward, if n is negative)
iter-=n	Steps n elements backward (or forward, if n is negative)
iter+n	Returns the iterator of the nth next element
n+iter	Returns the iterator of the nth next element
iter-n	Returns the iterator of the nth previous element
iter1-iter2	Returns the distance between iter1 and iter2
iter1<iter2	Returns whether iter1 is before iter2
iter1>iter2	Returns whether iter1 is after iter2
iter1<=iter2	Returns whether iter1 is not after iter2
iter1>=iter2	Returns whether iter1 is not before iter2

The following program demonstrates the special abilities of random access iterators:

#include <vector>
   #include <iostream>
   using namespace std;

int main()
   {
      vector<int> coll;

//insert elements from -3 to 9
      for (int i=-3; i<=9; ++i) {
          coll.push_back (i);
      }

/* print number of elements by processing the distance between beginning and end
       * - NOTE: uses operator -for iterators
       */
      cout << "number/distance: " << coll.end()-coll.begin() << endl;

/* print all elements
       * - NOTE: uses operator < instead of operator ! =
       */
      vector<int>::iterator pos;
       for (pos=coll.begin(); pos<coll.end(); ++pos) {
           cout << *pos << ' '; 
       }
       cout << endl;

/* print all elements
        * - NOTE: uses operator [ ] instead of operator *
        */
       for (int i=0; i<coll.size(); ++i) {
           cout << coll.begin() [i] << ' ';
       }
       cout << endl;

/* print every second element
        * - NOTE: uses operator +=
        */
       for (pos = coll.begin(); pos < coll.end()-1; pos += 2) {
           cout << *pos << ' ';
       }
       cout << endl;
   }

The output of the program is as follows:

This example won't work with lists, sets, and maps because all operations that are marked with NOTE: are provided only for random access iterators. In particular, keep in mind that you can use operator < as an end criterion in loops for random access iterators only.

Note that in the last loop the expression

requires that coll contains at least one element. If the collection was empty, coll.end() -1 would be the position before coll.begin(). The comparison might still work; but, strictly speaking, moving an iterator to before the beginning results in undefined behavior. Similarly, the expression pos += 2 might result in undefined behavior if it moves the iterator beyond the end() of the collection. Therefore, changing the final loop to the following is very dangerous because it results in undefined behavior if the collection contains an even number of elements (figure below):

Figure :- Incrementing Iterators by More than One Element

The Increment and Decrement Problem of Vector Iterators

The use of the increment and decrement operators of iterators includes a strange problem. In general, you can increment and decrement temporary iterators. However, for vectors and strings, you typically can't. Consider the following vector example:

Typically, the compilation of sort() fails. However, if you use, for example, a deque rather than a vector, it will compile. It might compile even with vectors, depending on the implementation of class vector.

The reason for this strange problem lies in the fact that vector iterators are typically implemented as ordinary pointers. And for all fundamental data types, such as pointers, you are not allowed to modify temporary values. For structures and classes, however, it is allowed. Thus, if the iterator is implemented as an ordinary pointer, the compilation fails; if implemented as a class, it succeeds. It always works with deques, lists, sets, and maps because you can't implement iterators as ordinary pointers for them. But for vectors, whether it works depends on the implementation. Usually, ordinary pointers are used. But if, for example, you use a "safe version" of the STL, the iterators are implemented as classes. To make your code portable you should not code as the previous example, using vectors. Instead, you should use an auxiliary object:

The problem is not as bad as it sounds. You can't get unexpected behavior because it is detected at compile time. But it is tricky enough to spend time solving it. This problem also applies to strings. String iterators are usually also implemented as ordinary character pointers, although this is not required.

-----------------------------------------------------------------
See Also:
-----------------------------------------------------------------

-----------------------------------------------------------------

ccplusplus.com

Wednesday, February 19, 2014

iterator category c++

Figure:- Iterator Categories

Table:- Abilities of Iterator Categories

Input Iterators

Table:- Operations of Input Iterators

Output Iterators

Table:- Operations of Output Iterators

Forward Iterators

Table :- Operations of Forward Iterators

Bidirectional Iterators

Table :- Additional Operations of Bidirectional Iterators

Random Access Iterators

Table:- Additional Operations of Random Access Iterators

Figure :- Incrementing Iterators by More than One Element

The Increment and Decrement Problem of Vector Iterators

No comments:

Post a Comment