iterator category

iterator category c++

Iterators can have capabilities in addition to their fundamental operations. The additional abilities depend on the internal structure of the container type. As usual, the STL provides only those operations that have good performance. For example, if containers have random access (such as vectors or deques) their iterators are also able to perform random access operations (for example, positioning the iterator directly at the fifth element). 

Iterators are subdivided into different categories that are based on their general abilities. The iterators of the predefined container classes belong to one of the following two categories:

1. Bidirectional iterator : As the name indicates, bidirectional iterators are able to iterate in two directions: forward, by using the increment operator, and backward, by using the decrement operator.  The iterators of the container classes list, set, multiset, map, and multimap are bidirectional iterators. 
2. Random access iterator :  Random access iterators have all the properties of bidirectional iterators. In addition, theycan perform random access. In particular, they provide operators for "iterator  arithmetic"(in accordance with "pointer arithmetic" of an ordinary pointer). You can add and subtract offsets, process differences, and compare iterators by using relational operators such as < and >. The iterators of the container classes vector and deque, and iterators of strings are random access iterators.

To write generic code that is as independent of the container type as possible, you should not use special operations for random access iterators. For example, the following loop works with any container:

for (pos = coll.begin(); pos != coll.end(); ++pos) {

   /*

    * some functionality here

    */

}

However, the following does not work with all containers:

for (pos = coll.begin() ; pos < coll.end(); ++pos) {

   /*

    * some functionality here

    */

}

The only difference is the use of operator < instead of operator != in the condition of the loop. Operator < is only provided for random access iterators, so this loop does not work with lists, sets, and maps. To write generic code for arbitrary containers,  you should use operator != rather than operator <. However, doing  so might lead to code that is less safe. This is because you may not recognize that pos gets a position behind end().

It's up to you to decide which version to use. It might be a question of the context, or it might even be a question of taste. To avoid misunderstanding, note that I am talking about "categories" and not "classes." A category only defines the abilities of iterators. The type doesn't matter. The generic concept of the STL works with pure abstraction; that is, anything that behaves like a bidirectional iterator is a bidirectional iterator.

See Also:

Standard Template Library Concepts and sample codes in C++