📖STL in CPP ( Part V )

STANDARD TEMPLATE LIBRARY (STL) III - ITERATORS - 2023

Iterators

Iterators are used to step through the elements of collections of objects.

The major advantage of iterators is that they offer common interfaces for any container type. Understanding iterators is probably the key to understand the STL. Just as templates make algorithm independent of the type of data stored, iterators make the algorithms independent of the type of container used. They are, therefore, an essential component of the STL generic approach.

Algorithms should be independent of the data structure of the container itself as well as data type stored in the container. Templates provide a generic representation for the data type stored in a container. The iterators provide a generic representation of the process of moving through the values in a container.

An iterator is an object that can navigate over elements of STL containers. All iterator represents a certain position in a container. To make it work, iterators have the following basic operations which are exactly the interface of ordinary pointers when they are used to iterator over the elements of an array.

1. Operator * Returns the element of the current position.

2. Operator ++ Lets the iterator step forward to the next element. Most iterators also allow backward stepping with operator --.

3. Operator == and != Check whether two iterators represent the same position.

4. Operator = Assigns an iterator (the position of the element to which it refers.

Though pointers also have the same properties listed above, there is a difference between pointer and iterators. The difference is that iterators may be smart pointers which can iterate over more complicated data structures of containers. The internal behavior of iterators depends on the data structure over which they iterate. So, each container type provides its own kind of iterator. In fact, each container class defines its iterator type as a nested class. As a result, iterators share the same interface but have different types.

All container classes provide the same basic member functions that enable them to use iterators to navigate their elements. The most important two functions are:

1. begin() This returns iterator that represents the beginning of the elements in the container. The beginning is the position of the first element.

2. end() This returns an iterator that represents the end of the elements in the container. The end is the position behind the last element. This is also called a past-the-end iterator.

begin() and end() define a half-open range that includes the first element but exclude the last: [begin(),end()). A half-open range has two advantages:

1. We have a simple end criterion for loops that iterate over the elements: They simply march through until they meet end().

2. It avoids special handling for empty ranges. For empty ranges, begin is equal to end().

Five Iterators

Different algorithms have different requirements for iterators. A find() algorithm needs the ++ operator to be defined so the iterator can step through the container. It does not need write access but it needs read access.

template<class InputIterator, class T>
InputIterator find(InputIterator first, InputIterator last, const T& value);

The sort() algorithm, on the other hand, requires random access so that it can swap the two non-adjacent elements.

template<class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);

The STL defines five iterators and describes its algorithms in terms of which kinds of iterator it needs.

1. Input Iterators The term input is used from the viewpoint of a program. In other words, information going from the container to the program is considered input. So, an input iterator is one that a program can use to read values from a container. Dereferencing an input iterator allows us to read a value from a container, but it does not allow us to alter the value. So algorithms that require an input iterator are algorithms that don't modify values of the container elements.

   One-way iterator. It can increment, but it can't back up.

   #include <iostream>
   #include <fstream>
   #include <numeric>  // for accumulate()
   #include <iterator>  
   
   using namespace std;
   
   int main()
   {
     ifstream myInt("data");
     istream_iterator<int> iter(myInt);
     istream_iterator<int> eos;  // end of stream iterator
   
     cout << "Sum of the data is "
          << accumulate(iter, eos, 0)
          << endl;
     return 0;
   }

   The data file:

   1 2 3 4 5 6 7 8 9 10

   Output:

   Sum of the data is 55

   Note that accumulate() is from <numeric> and the signature is:

   accumulate(input_iter, input_iter, value)

   where the value is usually 0 and it gets the accumulated value over the specified range.

2. Output Iterators The term output indicates that the iterator is used for moving information from a program to a container. An output iterator is similar to an input iterator, except that dereferencing is guaranteed to allow a program to modify a value of container element but not to read it.

   Single-pass and write-only iterator.

3. Forward Iterators Forward iterators use only the ++ operators for navigating through a container. So a forward iterator can only go forward through a container one element at a time. Unlike input and output iterators, however, it necessarily goes through a sequence of values in the same order each time we use it.

   Multiple-pass iterator.

   The example below calculates squares for a given vector using ForwardIterator:

   /* f.cpp */
   #include <iostream>
   #include <fstream>
   #include <iterator>
   #include <vector>
   
   using namespace std;
   
   template<typename ForwardIterator>
   void square(ForwardIterator first, ForwardIterator last)
   {
     cout << "Squares:  ";
     for(;first != last; first++) {
       *first = (*first) * (*first);
       cout << *first << " ";
     }
     cout << endl;
   }
   
   int main()
   {
   
     int arr[] = {1, 2, 3, 4, 5};
   
     vector<int> v(arr, arr + sizeof(arr)/sizeof(arr[0]));
   
     cout << "Elements: ";
     for(auto it : v ) {
       cout << it << " ";
     }
     cout << endl;
   
    square(v.begin(), v.end());
   
     return 0;
   }

   Output:

   $ g++ -std=c++11 -o f f.cpp
   $ ./f
   Elements: 1 2 3 4 5 
   Squares:  1 4 9 16 25 

4. Bidirectional Iterators A bidirectional iterator has all the features of a forward iterator and adds support for the two decrement operators (prefix and postfix).

   The following code checks if a string is a palindrome. The comparison starts from both ends using bidirectional iterator:

   #include <iostream>
   #include <iterator>
   #include <string>
   
   using namespace std;
   
   template<typename Bidirectional>
   bool isPalindrome(Bidirectional first, Bidirectional last)
   {
     while(true)
     {
       last--;
   
       // when a character is a space, skip it
       if(*last == ' ') last--;
       if(*first == ' ') first++;
       if(first == last)
         break;
   
       // case insensitive comparison
       if(tolower(*first) != tolower(*last))
         return false;
   
       first++;
   
       if(first == last)
         break;
     }
     return true;
   }
   
   int main()
   {
       string s[] = {"Never odd or even",
                     "No lemon, no melon",
                     "telnet",
                     "reviver"};
   
       for(int i = 0; i < 4; i++) {
         cout << s[i] << " : "
              << isPalindrome(s[i].begin(), s[i].end()) << endl;
       }
   
   }

   Output:

   Never odd or even : 1
   No lemon, no melon : 1
   telnet : 0
   reviver : 1

5. Random Access Iterators Some of the algorithms such as sort() and binary search() require the ability to jump directly to an arbitrary element of a container. A canonical algorithm such as the sort() is using RandomAccessIterator:

   template <class T>
   void sort(RandomAccessIterator first, RandomAccessIterator last);

   This type of iterator has all the features of a bidirectional iterator, plus it adds operations such as pointer addition that support random access and relational operations for those of a bidirectional iterators.

   The code below outputs a random element of a vector using the RandomAccessIterator:

   #include <iostream>
   #include <iterator>
   #include <vector>
   
   /* for ptrdiff_t */
   #include <cstddef>
   
   using namespace std;
   
   template <typename Random>
   Random getRandomElement(Random first, Random last)
   {
     ptrdiff_t d = last - first;
     return first + rand() % d;
   }
   
   int main()
   {
     vector<int> v(10);
     for(int i = 0; i < v.size(); i++)
       v[i] = i;
   
     for(int i = 0; i < 20; i++)
       cout << *getRandomElement(v.begin(), v.end()) << " ";
     cout << endl;
   
     return 0;
   }

   Output:

   $ g++ -std=c++11 -o r r.cpp
   $ ./r
   3 6 7 5 3 5 6 2 9 1 2 7 0 9 3 6 0 6 2 6 

   Note that the ptrdiff_t is the type returned by the pointer subtraction operation between two pointers. THis is a signed integral type.

const_iterator

A const_iterator is equivalent to pointer to a constant. Iterator itself can change its value but not the underlying element. Another type of iterator is an iterator itself is a constant. This is quite useless since it can iterate among the element of the container. On the contrary, normal iterator can do anything: it can change its underlying elements, it can iterate through the elements of the container by changing its value. Below is an example:

#include <iostream>
#include <vector>

using namespace std;

int main(int argc, char **argv)
{
	vector<int> v(10, 0);

	// iterator
	vector<int>::iterator it;
	it = v.begin(); //ok
	*it = 911; // ok
	it++; //ok

	// const_iterator
	vector<int>::const_iterator cit;
	cit = v.begin();
	// *cit = 911; // Error: cannot assign to a variable that is const
	cit++; // ok

	// iterator that is constant
	const vector<int>::iterator itc = v.begin();
	// itc = v.begin();  // Can't assign a new value
	*itc = 911;  // ok: itc can change its underlying element
	itc++; // Error: can't change the value of itc

	return 0;
}

Iterators - Example

Here is an example demonstrate the usage of iterators across several containers.

#include <iostream>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <map>
#include <string>

using namespace std;

int main()
{
	set<int> col_set;
	set<int, greater<int> > col_set2;
	multiset<int> col_mset;
	multimap<int,string> col_mmap;
	map<string,float> col_sfmap;
	vector<int> col_vec;
	deque<float> col_deque;
	list<char> col_list;

	col_set.insert(3);
	col_set.insert(1);
	col_set.insert(5);
	col_set.insert(4);
	col_set.insert(1);
	col_set.insert(6);
	col_set.insert(2);

	set<int>::const_iterator pos_set;
	cout << "sets in ascending order ";
	for(pos_set = col_set.begin(); pos_set != col_set.end();++pos_set) {
		cout << *pos_set << ' ';
	}
	cout << endl;

	col_set2.insert(3);
	col_set2.insert(1);
	col_set2.insert(5);
	col_set2.insert(4);
	col_set2.insert(1);
	col_set2.insert(6);
	col_set2.insert(2);

	set<int,greater<int> >::const_iterator pos_set2;
	cout << "sets in descending order ";
	for(pos_set2 = col_set2.begin(); pos_set2 != col_set2.end();++pos_set2) {
		cout << *pos_set2 << ' ';
	}
	cout << endl;

	col_mset.insert(3);
	col_mset.insert(1);
	col_mset.insert(5);
	col_mset.insert(4);
	col_mset.insert(1);
	col_mset.insert(6);
	col_mset.insert(2);

	multiset<int>::const_iterator pos_mset;
	cout << "multi sets in ascending order " << endl;
	for(pos_mset=col_mset.begin();pos_mset!=col_mset.end();++pos_mset) {
		cout << *pos_mset << ' ';
	}
	cout << endl;

	col_mmap.insert(make_pair(5,"tagged"));
	col_mmap.insert(make_pair(2,"a"));
	col_mmap.insert(make_pair(1,"this"));
	col_mmap.insert(make_pair(4,"of"));
	col_mmap.insert(make_pair(6,"strings"));
	col_mmap.insert(make_pair(1,"is"));
	col_mmap.insert(make_pair(3,"map"));

	multimap<int,string>::const_iterator pos_mmap;
	cout << "multi maps in ascending order " << endl;
	for(pos_mmap=col_mmap.begin(); pos_mmap != col_mmap.end();++pos_mmap) {
		cout <<"(" <first<<"," << pos_mmap->second<< ")";				 
	}
	cout << endl;

	cout << "Associate Array: an array in which the index \n" <<
		    "may be of an arbitrary type \n" <<
		     "string-float map" << endl;
	col_sfmap["PI"] = 3.1415;
	col_sfmap["an arbitrary number"] = 4983.223;
	col_sfmap["Null"] = 0;

	map<string,float>::iterator pos_sfmap;
	for(pos_sfmap = col_sfmap.begin(); pos_sfmap != col_sfmap.end();++pos_sfmap) {
		cout << "key: \"" << pos_sfmap->first << "\" "
			<< "value: " << pos_sfmap->second << endl;
	}

	cout << "vector, list & deque";
	for (int i = 1;i <= 6; i++) {
		col_vec.push_back(i);
		col_deque.push_front(static_cast<double>(i)*1.1);
	}

	for(char c = 'a';c <= 'z'; ++c) {
		col_list.push_back(c);
	}

	for (int i=0; i < col_vec.size() ; i++) {
		cout << col_vec[i] <<' ';
	}
	cout << endl;
	for (int i = 0; i < col_deque.size() ; i++) {
		cout << col_deque[i] <<' ';
	}
	cout << endl;

	//constant version iterator (read only)
	cout << " using constant iterator \n";
	list<char>:: const_iterator pos;
	for(pos = col_list.begin();pos!=col_list.end();pos++) {
		cout << *pos << ' ';
	}
	cout << endl;

	//non-constant version iterator (read and write)
	cout << " using non_constant iterator \n";
	list<char>:: iterator ncpos;
	// note that the preincrement operator(prefix ++) is used here.
	// postincrement(++) is slower because it should return
	// the old position.
	for(ncpos = col_list.begin(); ncpos != col_list.end(); ++ncpos) {
		*ncpos = toupper(*ncpos);
		cout << *ncpos << ' ';
	}
	cout << endl;

	cout << " list output using while \n";
	while(!col_list.empty()) {
		cout << col_list.front() << ' ';
		col_list.pop_front();
	}
	cout << endl;

	return 0;
}

The output is:

sets in ascending order 1 2 3 4 5 6
sets in descending order 6 5 4 3 2 1
multi sets in ascending order
1 1 2 3 4 5 6
multi maps in ascending order
(1,this)(1,is)(2,a)(3,map)(4,of)(5,tagged)(6,strings)
Associate Array: an array in which the index
may be of an arbitrary type
string-float map
key: "Null" value: 0
key: "PI" value: 3.1415
key: "an arbitrary number" value: 4983.22
vector, list & deque1 2 3 4 5 6
6.6 5.5 4.4 3.3 2.2 1.1
 using constant iterator
a b c d e f g h i j k l m n o p q r s t u v w x y z
 using non_constant iterator
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
 list output using while
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

copy() algorithm with ostream_iterator and istream_iterator

STL's copy() function copies elements from a range to a location identified by an iterator:

template<class InputIterator, class OutputIterator>
OutputIterator copy(InputIterator first,	// beginning of source
			InputIterator last, 	// end of source
			OutputIterator result)	// beginning of destination
{
	while (first != last) {
		*result = *first;
		++first;
		++result;
	}
	return result;
);

The copy() function copies the elements in the range [first,last) into the range [result, result + (lat - first)). It returns an iterator pointing one past the last copied-to location, result + (last - first). The result should not be in the range [first, last). In other words, the target can't overlap the source.

The copy() algorithm can copy data from one container to another. For example, it can copy an array into a vector:

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

int main()
{
	int myInt[] = {1,2,3,4,5};
	vector<int> v(sizeof(myInt)/sizeof(int));

	// copy array to vector
	copy(myInt, myInt+5, v.begin());

	//display elements
	vector<int>::const_iterator it;
	for(it = v.begin(); it != v.end(); ++it) {
		cout << *it << " " ;
	}

	return 0;
}

The copy() function overwrites existing data in the destination container. So, the container should be large enough to hold the copied elements. As a result, we can't simply use copy() to put data in an empty vector.

In the example, we displayed the elements after we copied the elements. If there is an iterator representing the output stream, we can use it with copy(). STL provides us such an iterator with the ostream_iterator template. It is an adapter , which is a class or function that converts an interface to another interface.. The following lines are doing exactly that:

#include <iterator>
ostream_iterator<int, char> myOutputIterator(cout, " ");

The myOutputIterator iterator now becomes an interface that allows us to use cout for display. The first template argument, int, indicates the data type being sent to the output stream. The second template argument, char, indicates that the output stream uses character type. The cout which is the first constructor argument identifies the output steam being used. The character string argument is a separator to be displayed after each item sent to the output stream.

We could use the iterator something like this:

*myOutputIterator++ = 2013;

It works like:

cout << 2013 << " ";

This ostream_iterator, the line says send 2013 and then a string " " to the output stream controlled by cout. With copy(), we can use the iterator like this:

copy(v.begin(), v.end(), myOutputIterator);

This copies the entire v container to the output stream. In other words, it displays the all the contents of the v:

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

int main()
{
	int myInt[] = {1,2,3,4,5};
	vector<int> v(sizeof(myInt)/sizeof(int));

	// copy array to vector
	copy(myInt, myInt+5, v.begin());

	// display elements
	ostream_iterator<int, char> myOutputIterator(cout, " ");
	copy(v.begin(), v.end(), myOutputIterator);

	return 0;
}

Actually, we do not need named iterator, myOutputIterator, for our display, and use an anonymous iterator:

copy(v.begin(), v.end(), ostream_iterator(cout," "));

Instead of

// display elements
ostream_iterator<int, char> myOutputIterator(cout, " ");
copy(v.begin(), v.end(), myOutputIterator);