Iterators in C++ STL

Reading time: 40 minutes

Operations on iterators

Begin and end :

begin(): This function is used to return the beginning position of the container.

end() : This function is used to return the after end position of the container.

iterator, begin() and end()

#include<iostream> 
#include<iterator> // for iterators 
#include<vector> // for vectors 
using namespace std; 
int main() 
{ 
    vector<int> ar = { 1, 2, 3, 4, 5 }; 
      
    // Declaring iterator to a vector 
    vector<int>::iterator ptr; 
      
    // Displaying vector elements using begin() and end() 
    cout << "The vector elements are : "; 
    for (ptr = ar.begin(); ptr < ar.end(); ptr++) 
        cout << *ptr << " "; 
      
    return 0;     
}

Output :

The vector elements are : 1 2 3 4 5 

Advance :

advance() : This function is used to increment the iterator position till the specified number mentioned in its arguments.

advance()

#include<iostream> 
#include<iterator> // for iterators 
#include<vector> // for vectors 
using namespace std; 
int main() 
{ 
    vector<int> ar = { 1, 2, 3, 4, 5 }; 
      
    // Declaring iterator to a vector 
    vector<int>::iterator ptr = ar.begin(); 
      
    // Using advance() to increment iterator position 
    // points to 4 
    advance(ptr, 3); 
      
    // Displaying iterator position 
    cout << "The position of iterator after advancing is : "; 
    cout << *ptr << " "; 
      
    return 0; 
      
} 

Output :

The position of iterator after advancing is : 4 

Next and previous

next() - This function returns the new iterator that the iterator would point after advancing the positions mentioned in its arguments.

prev() - This function returns the new iterator that the iterator would point after decrementing the positions mentioned in its arguments.

next() and prev()

#include<iostream> 
#include<iterator>
#include<vector>
using namespace std; 
int main() 
{ 
    vector<int> ar = { 1, 2, 3, 4, 5 }; 
      
    // Declaring iterators to a vector 
    vector<int>::iterator ptr = ar.begin(); 
    vector<int>::iterator ftr = ar.end(); 
     
     
    // Using next() to return new iterator 
    // points to 4 
    auto it = next(ptr, 3); 
      
    // Using prev() to return new iterator 
    // points to 3 
    auto it1 = prev(ftr, 3); 
      
    // Displaying iterator position 
    cout << "The position of new iterator using next() is : "; 
    cout << *it << " "; 
    cout << endl; 
      
    // Displaying iterator position 
    cout << "The position of new iterator using prev()  is : "; 
    cout << *it1 << " "; 
    cout << endl; 
      
    return 0;  
} 

Output:

The position of new iterator using next() is : 4 
The position of new iterator using prev()  is : 3 

Insertor

inserter() :- This function is used to insert the elements at any position in the container. It accepts 2 arguments, the container and iterator to position where the elements have to be inserted.

inserter()

#include<iostream> 
#include<iterator> 
#include<vector> 
using namespace std; 
int main() 
{ 
    vector<int> ar = { 1, 2, 3, 4, 5 }; 
    vector<int> ar1 = {10, 20, 30};  
      
    // Declaring iterator to a vector 
    vector<int>::iterator ptr = ar.begin(); 
     
    // Using advance to set position 
    advance(ptr, 3); 
      
    // copying 1 vector elements in other using inserter() 
    // inserts ar1 after 3rd position in ar 
    copy(ar1.begin(), ar1.end(), inserter(ar,ptr)); 
      
    // Displaying new vector elements 
    cout << "The new vector after inserting elements is : "; 
    for (int &x : ar)  
        cout << x << " "; 
      
    return 0;     
} 

Output :

The new vector after inserting elements is : 1 2 3 10 20 30 4 5

Types of iterators :

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

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.

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.

#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 

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

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

Relation between iterator and container

Each type of container has their own Iterators implementation. Thus before you use Iterators you need to declare them with the type of container they will operate on. For example:

//To use iterators in a vector

std::vector<int>::iterator pos;

//To use iterators in a list

std::list<char>::iterator pos;

Every container defines two types of iterators:

container::iterator - Iterate over elements in read/write mode.
container::const_iterator - Iterate over elements in read-mode only.

Advantages and Disadvantages of iterators

Advantage
1)The STL provides iterators as a convenient abstraction for accessing many different types of containers.

2)Iterators for templated classes are generated inside the class scope with the syntax

class_name<parameters>::iterator

3)Iterators can be thought of as limited pointers (or, in the case of random access iterators, as nearly equivalent to pointers)

Disadvanatges

1)Iterators do not provide bounds checking. it is possible to overstep the bounds of a container, resulting in segmentation faults

2)Different containers support different iterators, so it is not always possible to change the underlying container type without making changes to your code

3)Iterators can be invalidated if the underlying container (the container being iterated over) is changed significantly

Question