Таким образом, двусторонняя очередь будет расти автоматически!
deque<int> v;
copy(it_cin, end_cin, back_inserter(v));
5. Воспользуемся std::istringstream, чтобы скопировать элементы в середину двусторонней очереди. Поэтому определим несколько чисел в форме строки и создадим на их основе объект типа stream:
istringstream sstr {"123 456 789"};
6. Далее понадобится подсказка, которая поможет определить, куда именно нужно вставить элемент. Нам нужна середина, поэтому применим начальный указатель, передав его в функцию std::next. Второй аргумент данной функции говорит о том, что вернет итератор, смещенный на позицию v.size()/2 шагов, т.е. на половину очереди. (Мы преобразуем v.size() к типу int, поскольку второй параметр функции std::next представляет собой difference_type итератора, использованного в качестве первого параметра. В данном случае это целочисленный тип со знаком. В зависимости от установленных флажков компилятор может предупредить вас, если преобразование не было выполнено явно.)
auto deque_middle (next(begin(v),
static_cast<int>(v.size())/2));
7. Теперь можно скопировать проанализированные целые числа шаг за шагом из потока ввода строк в очередь. Опять же конечный итератор оболочки итератора потока представляет собой пустой объект типа std::istream_iterator<int> без аргументов конструктора (поэтому вы можете видеть пустые скобки {} в строке кода). Очередь оборачивается в итератор вставки, который представляет собой std::insert_iterator, указывающий на середину очереди с помощью итератора deque_middle:
copy(istream_iterator<int>{sstr}, {}, inserter(v, deque_middle));
8. Воспользуемся итератором std::front_insert_iterator, чтобы вставить элементы в начало очереди:
initializer_list<int> il2 {-1, -2, -3};
copy(begin(il2), end(il2), front_inserter(v));
9. На последнем шаге выведем содержимое очереди на консоль. Здесь итератор std::ostream_iterator работает как итератор вывода, что в нашем случае просто перенаправляет все скопированные целые числа в std::cout, прикрепляя символ ", " после каждого элемента:
copy(begin(v), end(v), ostream_iterator<int>{cout, ", "});
cout << 'n';
}
10. Компиляция и запуск программы дадут следующий результат. Можете ли вы определить, какие строки кода добавили каждое число?
$ echo "1 2 3 4 5" | ./main
-3, -2, -1, 1, 2, 123, 456, 789, 3, 4, 5,
Как это работает
Мы использовали множество разных адаптеров. Они имеют только одну схожую черту — оборачивают объект, не являющийся итератором сам по себе, в итератор.
std::back_insert_iterator
В адаптер back_insert_iterator можно обернуть типы std::vector, std::deque, std::list и т.д. Он будет вызывать метод контейнера push_back, который вставит новый элемент после всех существующих элементов. Если объект контейнера недостаточно велик, то его размер увеличится автоматически.
std::front_insert_iterator
Адаптер front_insert_iterator делает то же самое, что и адаптер back_insert_iterator, но вызывает метод контейнера push_front, который вставляет новый элемент перед существующими. Обратите внимание: для контейнеров наподобие std::vector это значит, что все существующие элементы нужно сдвинуть на одну позицию вправо для освобождения места под новый элемент.
std::insert_iterator
Этот адаптер итератора аналогичен другим итераторам вставки, но может вставлять новые элементы между существующими. Вспомогательная функция std::inserter, которая создает подобную оболочку, принимает два аргумента. Первый — контейнер, а второй — итератор, указывающий на позицию, в которую будут вставлены новые элементы.
std::istream_iterator
Адаптер istream_iterator тоже довольно удобен. Он подходит для любого объекта std::istream (который может представлять собой стандартный поток ввода или файлы) и будет пытаться преобразовывать полученные данные в соответствии с параметром шаблона. В этом примере мы использовали конструкцию std::istream_iterator<int>(std::cin), получающую из потока ввода целые числа.
Как правило, мы не знаем длину потока. Это оставляет открытым вопрос: куда указывает конечный итератор, если нам неизвестно, где заканчивается поток? Суть в том, что итератор знает, когда достигает конца потока. При сравнении с конечным итератором он фактически не будет сравнивать себя с конечным итератором, но даст знать, остались ли токены в потоке. Именно поэтому конструктор конечного итератора не принимает никаких аргументов.
std::ostream_iterator
Адаптер ostream_iterator аналогичен адаптеру istream_iterator, но работает по обратному принципу: не принимает токены из потока ввода, а отправляет их в поток вывода. Еще одно отличие заключается в том, что его конструктор принимает второй аргумент, являющийся строкой, которая будет помещена в поток вывода после каждого элемента. Это полезно, поскольку таким способом можно вывести на экран разделяющую запятую ", " или символ перехода на новую строку.
Реализуем алгоритмы с помощью итераторов
Итераторы обычно итерируют, переходя с одного элемента контейнера на другой. Но не обязательно использовать итераторы только для того, чтобы итерировать по структурам данных. Они вполне подходят для реализации алгоритмов, в таком случае будут высчитывать следующее значение при инкрементировании (++it) и возвращать это значение при разыменовании (*it).
В данном разделе мы рассмотрим этот принцип, реализовав функцию, выводящую на экран последовательность чисел Фибоначчи с помощью итераторов. Такая функция рекурсивно определяется следующим образом: F(n) = F(n-1)+F(n-2). Она начинается со стартовых значений F(0) = 0 и F(1) = 1. Это приводит к появлению такой последовательности чисел:
□ F(0) = 0;
□ F(1) = 1;
□ F(2) = F(1)+F(0) = 1;
□ F(3) = F(2)+F(1) = 2;
□ F(4) = F(3)+F(2) = 3;
□ F(5) = F(4)+F(3) = 5;
□ F(6) = F(5)+F(4) = 8;
□ ... и т.д.
Если мы реализуем это в форме вызываемой функции, которая возвращает значение Фибоначчи для любого числа n, то получим рекурсивную функцию, вызывающую саму себя, или цикл. Такой результат приемлем, но что, если мы напишем программу, принимающую числа Фибоначчи по некоему шаблону одно за другим? У нас есть два варианта: либо выполнять все рекурсивные вызовы для каждого числа Фибоначчи (это, по сути, растрата вычислительного времени), либо сохранять два последних числа во временных переменных и использовать их для вычисления следующего. Во втором случае придется объединить код функции Фибоначчи и код остальной части нашей программы, которая решает другую задачу:
size_t a {0};
size_t b {1};
for (size_t i {0}; i < N; ++i) {
const size_t old_b {b};
b += a;
a = old_b;
// сделаем что-нибудь с b, текущим числом Фибоначчи
}
Итераторы позволяют решить задачу оригинальным способом. Можно обернуть шаги, которые нужно сделать в реализации, основанной на цикле функции Фибоначчи, в префиксный оператор
