|< 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?

  1. An Introduction

  2. Iterators

  3. An iterator, a list container simple example

  4. An iterator, a set container example

  5. An iterator, a multiset container example

  6. An iterator, a map container simple example

  7. An iterator, a multimap container simple example

  8. Iterator Categories

  9. The <iterator> Header

  10. The <iterator> Header Members – member functions

  11. advance() prototypes

  12. iterator, advance() example

 

 

 

 

 

 

 

 

 

 

 

 

 

My Training Period: xx hours

 

This module contains more C++ STL Iterators class templates programming tutorial. Program examples compiled using VC++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 in C++ STL Iterator source code.

 

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

 

  • Able to understand and use iterators.

  • 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 I can only have a value V 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 iterator I can take the place of an output iterator for writing or an input iterator for reading. You can, however, read (through V = *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 iterator X 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 iterator I 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. For N, an integer object, you can write x[N], x + N, x - N, and N + X.

 

Table 31.1:  Iterator types

 

  1. Output iterator

or can be replaced by

  1. forward iterator

or can be replaced by

  1. bidirectional iterator

or can be replaced by

  1. random-access iterator

 

  1. Input iterator

or can be replaced by

  1. forward iterator

or can be replaced by

  1. bidirectional iterator

or can be replaced by

  1. random-access iterator

 

  1. forward iterator

or can be replaced by

  1. bidirectional iterator

or can be replaced by

  1. random-access iterator

 

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

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

// 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

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

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

{...}

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

{...}

31.4  The <iterator> Header

#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

// 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:

 

  1. The source code in text for this tutorial is available in C++ STL Iterator source code.

  2. A complete C & C++ Standard Library documentation that includes STL.

  3. C++ Templates programming tutorials.

  4. Check the best selling C / C++ and STL books at Amazon.com.

 

 

 

 

 

 

|< 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