Nov 15 2024

Iterator adaptors

Nov 15 2024

Reverse iterator
Move iterators
Stream iterators
Insert iterators
Links

Iterator adaptors are a separate type of iterators with special behavior. They simplify the work with containers and are very useful in standard algorithms.

Reverse iterator

The 'std::reverse_iterator' adaptor iterates elements in the reverse direction. A reverse iterator is based on a biderctional iterator (LegacyBidirectionalIterator). After incrementing, it points to the previous container element.

Each container, which allows a reverse iteration through the elements, already has non-static member functions that return reverse iterators to the beginning and to the end — 'rbegin()' and 'rend()'. A program, which implements a reverse iteration through the elements, may look like this:

#include <iostream>
#include <list>

int main()
{
  std::list<int> list { 1, 2, 3, 4, 5 };
  
  for (std::list<int>::reverse_iterator rIt = list.rbegin();
       rIt != list.rend();
       ++rIt)
  {
    std::cout << *rIt << " ";
  }

  return 0;
}

// output: 5 4 3 2 1

Since C++11, the 'auto' keyword can be used instead of long iterator type name 'rIt'. Another way to get a reverse iterator is to create it from the base one. C++14 introduced new function 'std::make_reverse_iterator' that can help with this.

The following code fragment iterates all elements, starting from the first one and ending with the one greater than 3. Then, it goes through these elements in a reverse direction:

#include <iostream>
#include <list>

int main()
{
  std::list<int> list { 1, 2, 3, 4, 5 };

  auto it = list.begin();
  while (it != list.end() && *it <= 3)
  {
    std::cout << *it << ' ';
    ++it;
  }

  std::cout << *it << ' ';
  
  auto rIt = std::make_reverse_iterator(it);
  while (rIt != list.rend())
  {
    std::cout << *rIt << ' ';
    ++rIt;
  }

  return 0;
}

// output: 1 2 3 4 3 2 1

After completing the first loop, the 'it' iterator stopped on element 4. The created reverse iterator would point to the previous element (3). That's what makes the 'std::make_reverse_iterator' function so special.

In order to get a base iterator from a reverse one, you can call the 'base' method:

auto iter = riter.base();

Move iterators

C++11 introduced move semantics. It allows you to eliminate the costs of expensive object copying (with dynamic allocation, I/O operations, etc.) if the object can be moved. Iterator adaptor 'std::move_iterator' can move container elements.

The 'std::make_move_iterator' function can make this iterator from the base one. When we dereference the move iterator, everything goes the same with the underlying iterator, except that the result of the operator is an rvalue reference.

Moving elements can be useful, for example, when you merge several containers:

#include <iostream>
#include <set>
#include <vector>

int main()
{
  std::set<std::string> words { "mango", "orange", "apple", "pear" };
  std::vector<std::string> newWords { "cucumber", "tomato", "pumpkin" };
  words.insert(std::make_move_iterator(newWords.begin()), 
               std::make_move_iterator(newWords.end()));

  std::cout << " words: ";
  for (auto word : words) {
    std::cout << '\'' << word << "' ";
  }
  std::cout << "\nnewWords: ";
  for (auto word : newWords) {
    std::cout << '\'' << word << "' ";
  }
  return 0;
}

// words: 'apple' 'cucumber' 'mango' 'orange' 'pear' 'pumpkin' 'tomato'
// newWords: '' '' ''

Iterators for beginning and end of the 'newWords' container were adapted for moving elements. The 'insert' method, instead of copying, moved these elements to the 'words' container. The program's output indicates that elements of the 'newWords' container were moved — you can see empty strings in their place. The number of elements remained the same.

Stream iterators

Often a stream contains elements of the same type. In this case, stream iterators allow you to work with a stream as a container and use standard algorithms.

The input stream operator 'std::istream_iterator' reads data from the 'std::basic_istream' object. For example, from 'std::cin' or a file open for reading. When you create an input stream iterator, you need to instantiate it with the type of read elements and specify a stream as a parameter, for example:

std::istream_iterator<int> input_iter { std::cin };

The elements are read at the moment the iterator is incremented using the '++' operator. The increment operation uses the '>>' operator of the underlying stream to read. The '*' dereference operator returns only a constant copy of an element.

The iterator that marks the end of the sequence is the 'std::istream_iterator<int>()' default iterator. If you dereference or increment this iterator, the behavior is undefined.

The 'std::ostream_iterator' output stream iterator is used to write data to the 'std::basic_ostream' object — for example, to 'std::cout' or file open for writing. When you create an output stream iterator, you can specify a separator as a second parameter:

std::ostream_iterator<int> output_iter { std::cout, " " };

It is impossible to get an element this iterator points to.

In the following example, the program receives integers from the input stream and outputs only the even ones:

#include <iostream>
#include <iterator>

int main()
{
  std::istream_iterator<int> input_iter(std::cin);
  std::ostream_iterator<int> output_iter(std::cout, " ");

  while (input_iter != std::istream_iterator<int>())
  {
    if (*input_iter % 2 == 0)
    {
      *output_iter = *input_iter;
    }
    input_iter++;
  }

  return 0;
}

// input: 1 7 3 9 2 7 4 9 8 e
// output: 2 4 8

If you initialize the 'input_iter' iterator, it leads to a request for user data input from the stdin. After that, the 'input_iter' iterator will point to the first integer. As long as each character sequence in the input stream is converted to the 'int' type, the reading continues. Otherwise, the 'input_iter' iterator takes the default value, and the loop exits.

If the '*input_iter' element is even, it's written to the output stream:

*output_iter = *input_iter;

Insert iterators

Insertion iterators replace the assignment operation with an insertion operation. This may be useful when you add a group of new items to a container. There are 3 kinds of insertion iterators:

'std::front_insert_iterator<Container>' uses the 'push_front' method to insert elements to the beginning of the underlying container;
'std::back_insert_iterator<Container>' uses the 'push_back' method to insert elements in the end of the underlying container;
'std:: insert_iterator<Container, Iter>' inserts an element at an arbitrary position of the underlying container specified by Iter.

To avoid writing the full container type when you create these iterators, the standard library introduced these three corresponding functions:

'std::front_inserter';
'std::back_inserter';
'std::inserter'.

The following program solves the problem of conditional placement of incoming data inside one container. Negative values are written to the end of the container. The rest are written to the beginning.

#include <iostream>
#include <list>
#include <iterator>

int main()
{
  std::list<int> list;
  std::initializer_list<int> data { -5, 8, 6, -1, 3, 0, -7, 5};

  auto front_it = std::front_inserter(list);
  auto  back_it = std::back_inserter(list);

  for (auto elem : data)
  {
    if (elem < 0)
    {
      *back_it = elem;
    }
    else
    {
      *front_it = elem;
    }
  }

  for (auto elem : list)
  {
    std::cout << elem << " ";
  }

  return 0;
}

// output: 5 0 3 6 8 -5 -1 -7

The sequence of non-negative numbers in the resulting container is a reverse original one. The sequence of negative numbers remains the same.

Insertion iterators are often used in standard algorithms. For example, you can read the input stream elements to the desired location in the list, using 'std::copy':

#include <iostream>
#include <list>
#include <algorithm>
#include <iterator>

int main()
{
  std::list<int> list { 1, 10, 100, 1000, 10000 };
  std::istream_iterator<int> input_it { std::cin };
  auto insert_it = std::inserter(list, std::next(list.begin(), 3));

  std::copy(input_it, std::istream_iterator<int>(), insert_it);

  for (auto elem : list)
  {
    std::cout << elem << " ";
  }

  return 0;
}

// input: 222 333 444 555 666 y
// output: 1 10 100 222 333 444 555 666 1000 10000