|< C++ STL Container Adaptor | Main | C++ STL Iterator 2 >|Site Index |Download |

MODULE 31

THE C++ STL ITERATOR PART 1

What do we have in this session?

An Introduction
Iterators
An iterator, a list container simple example
An iterator, a set container example
An iterator, a multiset container example
An iterator, a map container simple example
An iterator, a multimap container simple example
Iterator Categories
The <iterator> Header
The <iterator> Header Members – member functions
advance() prototypes
iterator, advance() example

My Training Period: xx hours

This module contains more C++ STL Iterators class templates programming tutorial. Program examples compiled usingVC++7.0 / .Net, win32 empty console mode application.g++ program example compilation is given at the end of this Module. The source code in text for this tutorial is available inC++ STL Iterator source code.

C++ STL iterators abilities that supposed to be acquired:

Able to understand and useiterators.
To understand the member functions program examples.
Able to understand and use iterator template classes.

31.1 An Introduction

In the previous Modules, we have learned how to construct various types of containers. At the same time, in the program examples, iterators and algorithm also have been introduced.
In this Module we are going to discuss an iterator in more detail and on the way we go through the program examples, you may find that the same member functions used in iterators as used in containers tutorials, you will find containers, iterators and algorithms used in the program examples. So, be familiar with these STL objects.

31.2 Iterators

An iterator is an object that can iterate or navigate or traverse over elements in the containers that represent data structures. These elements may be the entire or just a portion of a STL container. It represents a certain position in a container.
For example, the following basic operations:output, input, forward, bidirectional and random access define the behavior of an iterator.
Iterators are a generalization of pointers, abstracting from their requirements in a way that allows a C++ program to work with different data structures in a uniform manner. Iterators act as intermediaries between containers and generic algorithms.
Instead of operating on specific data types, algorithms are defined to operate on a range specified by a type of iterator. Any data structure that satisfies the requirements of the iterator may then be operated on by the algorithm.
The name of an iterator type or its prefix indicates the category of iterators required for that type.
There are five types or categories of iterator, each with its own set of requirements and operations are shown below and are arranged in the order of the strength of their functionalities.

Iterator Type	Description
Output	Forward moving, may store but not retrieve values, provided by ostream and inserter. An output iterator Ican only have a valueV stored indirect on it, after which it must be incremented before the next store, as in (I ++ = V),(I = V, ++ I), or (*I = V, I ++).
Input	Forward moving, may retrieve but not store values, provided by istream. An input iterator I can represent a singular value that indicates end of sequence. If an input iterator does not compare equal to its end-of-sequence value, it can have a value V accessed indirect on it any number of times, as in(V = I). To progress to the next value or end of sequence, you increment it (post or pre-increment), as in ++ I,I ++, or by pointer,(V = I ++). Once you increment any copy of an input iterator, none of the other copies can safely be compared, dereferenced, or incremented thereafter.
Forward	Forward moving, may store and retrieve values. A forward iteratorI can take the place of an output iterator for writing or an input iterator for reading. You can, however, read (throughV = I) what you just wrote (through I = V) through a forward iterator. You can also make multiple copies of a forward iterator, each of which can be dereferenced and incremented independently.
Bidirectional	Forward and backward moving, may store and retrieve values, provided by list, set, multiset, map, and multimap. A bidirectional iteratorX can take the place of a forward iterator. You can, however, also decrement (pre or post-decrement) a bidirectional iterator, as in-- I,I --, or a pointer, (V = *I --).
Random-access	Elements accessed in any order, may store and retrieve values, provided by vector, deque, string, and array. A random-access iteratorI can take the place of a bidirectional iterator. You can also perform much the same integer arithmetic on a random-access iterator that you can on an object pointer. ForN, an integer object, you can write x[N],x + N,x - N, andN + X.
Table 31.1: Iterator types

Note that an object pointer can take the place of a random-access iterator or any other iterator. All iterators can be assigned or copied.
They are assumed to be lightweight objects and are often passed and returned by value, not by reference. Note also that none of the operations previously described can throw an exception when performed on a valid iterator.
The hierarchy of iterator categories can be summarized by showing three sequences. For write-only access to a sequence, you can use any of the following:

Output iterator	or can be replaced by
forward iterator	or can be replaced by
bidirectional iterator	or can be replaced by
random-access iterator

Any algorithm that calls for an output iterator should work nicely with a forward iterator, for example, but not the other way around.
For read-only access to a sequence, you can use any of the following:

Input iterator	or can be replaced by
forward iterator	or can be replaced by
bidirectional iterator	or can be replaced by
random-access iterator

Aninput iterator is the weakest of all categories, in this case.
Finally, for read/write access to a sequence, you can use any of the following:

forward iterator	or can be replaced by
bidirectionaliterator	or can be replaced by
random-access iterator

An object pointer can always serve as a random-access iterator, so it can serve as any category of iterator if it supports the proper read/write access to the sequence it designates.
An iterator Iterator other than an object pointer must also define the member types required by the specialization iterator_traits<Iterator>. Note that these requirements can be met by deriving Iterator from the public base class iterator.
It is important to understand the promises and limitations of each iterator category to see how iterators are used by containers and algorithms in the STL.
For a simple operator examples:

Operator	Description
++	Make the iterator step forward to the next element.
== and!=	Return whether two iterators represent the same position or not.
=	Assigns an iterator.
Table 31.2: Operators and iterator

Compared to the traditional usage of this operator on arrays, iterators are smart pointers that iterate over more complicated data structures of containers.
Each container type supplies its own kind of iterator.
Hence, iterators share the same interface but have different types, then operations use the same interface but different types, and we can use templates to formulate generic operations that work with arbitrary types that satisfy the interface.
All container classes provide the same basic member functions that enable them to use iterators to navigate over their elements.
The most frequently functions used in the program examples in the previousContainers Modules are begin() andend().

Member function	Description
begin()	Returns an iterator that represents the beginning of the elements in the container. The beginning is the position of the first element (if any).
end()	Returns an iterator that represents the end of the elements in the container. As shown in the previous modules before, the end is the position behind the last element.
Table 31.3: begin() and end() member functions

The following example demonstrates a simple use of iterators.

// an iterator, a list container simple example

#include <iostream>

#include <list>

using namespace std;

int main()

{

// lst, list container for character elements

list<char> lst;

// append elements from 'A' to 'Z' to the list lst container

for(char chs='A'; chs<='Z'; ++chs)

lst.push_back(chs);

// iterate over all elements and print, separated by space

list<char>::const_iterator pos;

for(pos = lst.begin(); pos != lst.end(); ++pos)

cout<<*pos<<' ';

cout<<endl;

return 0;

}

Output:

C++ STL Iterator very simple general iterator program example

// an iterator, a set container example

#include <iostream>

#include <set>

using namespace std;

int main()

{

// set container of int data type

set<int> tst;

// insert elements

tst.insert(12);

tst.insert(21);

tst.insert(32);

tst.insert(31);

tst.insert(9);

tst.insert(14);

tst.insert(21);

tst.insert(31);

tst.insert(7);

// iterate over all elements and print, separated by space

set<int>::const_iterator pos;

// pre-increment and pre-decrement are faster than post-increment and post-decrement...

for(pos = tst.begin(); pos != tst.end(); ++pos)

cout<<*pos<<' ';

cout<<endl;

return 0;

}

Output:

C++ STL Iterator set program example

// an iterator, a multiset container example

#include <iostream>

#include <set>

using namespace std;

int main()

{

// multiset container of int data type

multiset<int> tst;

// insert elements

tst.insert(12);

tst.insert(21);

tst.insert(32);

tst.insert(31);

tst.insert(9);

tst.insert(14);

tst.insert(21);

tst.insert(31);

tst.insert(7);

// iterate over all elements and print, separated by space

multiset<int>::const_iterator pos;

// pre-increment and pre-decrement are faster than post-increment and post-decrement...

for(pos = tst.begin(); pos != tst.end(); ++pos)

cout<<*pos<<' ';

cout<<endl;

return 0;

}

Output:

C++ STL Iterator multiset program example

// an iterator, a map container simple example

#include <iostream>

#include <map>

#include <string>

using namespace std;

int main()

{

// type of the collection

map<int, string> mp;

// set container for int/string values insert some elements in arbitrary order

// notice a value with key 1...

mp.insert(make_pair(5,"learn"));

mp.insert(make_pair(2,"map"));

mp.insert(make_pair(1,"Testing"));

mp.insert(make_pair(7,"tagged"));

mp.insert(make_pair(4,"strings"));

mp.insert(make_pair(6,"iterator!"));

mp.insert(make_pair(1,"the"));

mp.insert(make_pair(3,"tagged"));

// iterate over all elements and print, element member second is the value

map<int, string>::iterator pos;

for(pos = mp.begin(); pos != mp.end(); ++pos)

cout<<pos->second<<' ';

cout<<endl;

return 0;

}

Output:

C++ STL Iterator map program example

// an iterator, a multimap container simple example

#include <iostream>

#include <map>

#include <string>

using namespace std;

int main()

{

// type of the collection

multimap<int, string> mmp;

// set container for int/string values insert some elements in arbitrary order

// notice a value of key 1

mmp.insert(make_pair(5,"learn"));

mmp.insert(make_pair(2,"map"));

mmp.insert(make_pair(1,"Testing"));

mmp.insert(make_pair(7,"tagged"));

mmp.insert(make_pair(4,"strings"));

mmp.insert(make_pair(6,"iterator!"));

mmp.insert(make_pair(1,"the"));

mmp.insert(make_pair(3,"tagged"));

// iterate over all elements and print, element member second is the value

multimap<int, string>::iterator pos;

for(pos = mmp.begin(); pos != mmp.end(); ++pos)

cout<<pos->second<<' ';

cout<<endl;

return 0;

}

Output:

C++ STL Iterator multimap program example

31.3 Iterator Categories

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:

Category	Description
Bidirectional iterator	Bidirectional iterators are able to iterate in two directions, forward and backward, by using the increment operator (e.g. ++) and decrement operators (e.g. --)respectively. The iterators of the container classes list, set, multiset, map, and multimap are bidirectional iterators.
Random access iterator	Random access iterators have all the properties of bidirectional iterators plus they can perform random access. 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.
Table 31.4: Iterator category

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

for(pos = contner.begin(); pos != contner.end(); ++pos)

{...}

However, the following does not work with all containers:

for(pos = contner.begin(); pos < contner.end(); ++pos)

{...}

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
A category only defines the abilities of iterators, not the type of the iterators.
Let dig more details what are provided for us in <iterator> header.

31.4 The <iterator> Header

Defines the iterator primitives, predefined iterators and stream iterators, as well as several supporting templates. The predefined iterators include insert and reverse adaptors.
There are three classes of insert iterator adaptors: front, back, and general.
They provide insert semantics rather than the overwrite semantics that the container member function iterators provide. As usual, to use iterator we must include the iterator header as shown below.

#include <iterator>

The <iterator> Header Members

Member Functions

Member function	Description
advance()	Increments an iterator by a specified number of positions.
back_inserter()	Creates an iterator that can insert elements at the back of a specified container.
distance()	Determines the number of increments between the positions addressed by two iterators.
front_inserter()	Creates an iterator that can insert elements at the front of a specified container.
inserter()	An iterator adaptor that adds a new element to a container at a specified point of insertion.
Table 31.5: Iterator member functions

advance() prototypes

template<class InputIterator, class Distance>

   void advance( InputIterator& _InIt, Distance _Off );

Parameters

Parameter	Description
_InIt	The iterator that is to be incremented and that must satisfy the requirements for an input iterator.
_Off	An integral type that is convertible to the iterator's difference type and that specifies the number of increments the position of the iterator is to be advanced.
Table 31.6

The range advanced through must be nonsingular, where the iterators must be dereferenceable or past the end.
If the InputIterator satisfies the requirements for a bidirectional iterator type, then _Off may be negative. If InputIterator is an input or forward iterator type, _Off must be nonnegative.
Theadvance function has constant complexity whenInputIterator satisfies the requirements for a random-access iterator; otherwise, it has linear complexity and so is potentially expensive.

// iterator, advance()

#include <iterator>

#include <list>

#include <iostream>

using namespace std;

int main()

{

int i;

list<int> lst;

for(i = 1; i <= 10; ++i)

lst.push_back(i);

list<int>::iterator lstIter, lstpos = lst.begin();

cout<<"The lst list data: ";

for(lstIter = lst.begin(); lstIter != lst.end(); lstIter++)

cout<<*lstIter<<" ";

cout<<endl;

cout<<"The the first element pointed by iterator lstpos is: "<<*lstpos<<endl;

advance(lstpos, 5);

cout<<"Advanced lstpos 5 steps forward pointing to the "<<*lstpos<<endl;

advance(lstpos, -4);

cout<<"Moved lstpos 4 steps backward pointing to the "<<*lstpos<<endl;

advance(lstpos, 8);

cout<<"Finally, the last element pointed by iterator lstpos is: "<<*lstpos<<endl;

return 0;

}

Output:

C++ STL Iterator advance()

tenouk C++ STL tutorial

Further C++ STL iterators related reading:

The source code in text for this tutorial is available inC++ STL Iterator source code.
Acomplete C Standard Library.
Acomplete C++ Standard Library documentation that includes STL.
C++ Templates programming tutorials.
Check thebest selling C / C++ and STL books at Amazon.com.

|< C++ STL Container Adaptor | Main | C++ STL Iterator 2 >|Site Index |Download |

|< C++ STL Container Adaptor | Main | C++ STL Iterator 2 >|Site Index |Download |

MODULE 31

THE C++ STL ITERATOR PART 1

What do we have in this session?

An Introduction

Iterators

An iterator, a list container simple example

An iterator, a set container example

An iterator, a multiset container example

An iterator, a map container simple example

An iterator, a multimap container simple example

Iterator Categories

The <iterator> Header

The <iterator> Header Members – member functions

advance() prototypes

iterator, advance() example

My Training Period: xx hours

C++ STL iterators abilities that supposed to be acquired:

Able to understand and useiterators.

To understand the member functions program examples.

Able to understand and use iterator template classes.

31.1 An Introduction

31.2 Iterators

Output:

Output:

Output:

Output:

Output:

31.3 Iterator Categories

31.4 The <iterator> Header

The <iterator> Header Members

Member Functions

advance() prototypes

Parameters

Parameter

Description

_InIt

The iterator that is to be incremented and that must satisfy the requirements for an input iterator.

_Off

An integral type that is convertible to the iterator's difference type and that specifies the number of increments the position of the iterator is to be advanced.

Table 31.6

Output:

Further C++ STL iterators related reading:

|< C++ STL Container Adaptor | Main | C++ STL Iterator 2 >|Site Index |Download |

C++ STL Iterators Classes: Part 1 | Part 2 |Part 3 | Part 4 | Part 5 | Part 6 | Part 7