15 Ноя 2024

Итераторы-адаптеры

15 Ноя 2024

Обратный итератор
Итераторы перемещения
Потоковые итераторы
Итераторы вставки
Библиографический список

Итераторы-адаптеры – это отдельный вид итераторов со специальным поведением. Они упрощают работу с контейнерами и бывают очень полезны в стандартных алгоритмах.

Обратный итератор

Адаптер 'std::reverse_iterator' – это итератор, перебирающий элементы в обратном направлении. Обратный итератор базируется на двунаправленном итераторе (LegacyBidirectionalIterator). После инкрементирования он будет указывать на предыдущий элемент контейнера.

Каждый контейнер, в котором возможен обратный проход по элементам, уже имеет нестатические функции-члены класса, возвращающие обратные итераторы на начало и конец - 'rbegin()' и 'rend()' соответственно. Программа, реализующая обратный проход по всем элементам, может выглядеть следующим образом:

#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

Начиная с С++11, вместо длинного имени типа итератора 'rIt' можно использовать ключевое слово 'auto'. Другой способ получить обратный итератор — это создать его на основе базового. В С++14 была добавлена функция 'std::make_reverse_iterator', которая может помочь в этом.

В следующем примере стоит задача перебрать все элементы: начиная с первого и заканчивая тем, что больше 3. Дальше нужно пройти по этим элементам в обратном направлении:

#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

После завершения первого цикла итератор 'it' остановился на элементе 4. Созданный обратный итератор будет указывать на предыдущий элемент (3). В этом заключается особенность функции 'std::make_reverse_iterator'.

Для получения базового итератора из обратного можно вызвать метод 'base':

auto iter = riter.base();

Итераторы перемещения

В С++11 появилась семантика перемещения. Она позволяет устранить издержки по дорогостоящему копированию (с динамической аллокацией, I/O операциями и т.п.), если объект можно "переместить". Для того чтобы перемещать элементы контейнера, существует итератор-адаптер 'std::move_iterator'.

Чтобы создать такой итератор из базового, используется функция 'std::make_move_iterator'. При разыменовании итератора перемещения происходит всё то же самое, что и с нижележащим итератором, за исключением того, что результат оператора – это rvalue-ссылка.

Перемещение элементов может быть полезно, например, при объединении нескольких контейнеров:

#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: '' '' ''

Итераторы на начало и конец контейнера 'newWords' были адаптированы для перемещения элементов. Поэтому метод 'insert' вместо копирования переместил эти элементы в контейнер 'words'. Вывод программы свидетельствует о том, что элементы контейнера 'newWords' были перемещены, и на их месте образовались пустые строки. Число элементов осталось прежним.

Потоковые итераторы

Часто бывает, что поток содержит однотипные элементы. В таких случаях потоковые итераторы позволяют работать с потоком как с контейнером и использовать стандартные алгоритмы.

Итератор потока ввода 'std::istream_iterator' предназначен для чтения данных из объекта 'std::basic_istream' (например, из 'std::cin' или файла, открытого на чтение). При создании итератора потока ввода требуется инстанцировать его типом считываемых элементов и передать в конструктор поток, например:

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

Считывание элементов происходит в момент инкрементирования итератора через оператор '++'. Операция инкрементирования использует операцию '>>' нижележащего потока для чтения. Операция разыменования '*' возвращает только константную копию элемента.

Итератором, который обозначает конец последовательности, является итератор по умолчанию 'std::istream_iterator<int>()'. Его разыменование или инкрементирование приводит к неопределённому поведению.

Итератор потока вывода 'std::ostream_iterator' используется для записи данных в объект 'std::basic_ostream' (например, в 'std::cout' или файл, открытый для записи). При создании итератора потока вывода можно указать вторым параметром разделитель:

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

Получить элемент, на который указывает итератор, не предоставляется возможным.

В следующем примере программа получает целые числа из потока ввода и выводит только чётные из них:

#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

Инициализация итератора 'input_iter' приводит к запросу ввода пользовательских данных из stdin. После чего итератор 'input_iter' будет указывать на первое целое число. Пока каждый набор символов в потоке ввода конвертируется в тип 'int', считывание будет продолжаться. В противном случае итератор 'input_iter' примет значение по умолчанию и произойдёт выход из цикла.

Если элемент '*input_iter' является чётным, то он записывается в поток вывода:

*output_iter = *input_iter;

Итераторы вставки

Итераторы вставки заменяют операцию присваивания на операцию вставки. Это может быть полезно при добавлении группы новых элементов в контейнер. Существует три вида итераторов вставки:

'std::front_insert_iterator<Container>' – использует метод 'push_front' для вставки элементов в начало нижележащего контейнера;
'std::back_insert_iterator<Container>' – использует метод 'push_back' для вставки элементов в конец нижележащего контейнера;
'std:: insert_iterator<Container, Iter>' – вставляет элемент в произвольную позицию нижележащего контейнера, заданную итератором Iter.

Чтобы при создании этих итераторов не приходилось писать полный тип контейнера, в стандартную библиотеку были добавлены три соответствующие функции:

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

Следующая программа решает задачу условного размещения поступающих данных внутри одного контейнера. Отрицательные значения записываются в конец контейнера, а остальные – в начало.

#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

Последовательность неотрицательных чисел в итоговом контейнере является обратной относительно исходной. Последовательность отрицательных чисел осталась прежней.

Итераторы вставки часто применяются в стандартных алгоритмах. Например, с помощью алгоритма '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