begin() и end(), которые указывают на полезные данные и позволяют итерировать по ним. Перебор всегда выглядит одинаково, независимо от того, по какой структуре данных выполняется.
Можно получить итераторы для векторов, списков, двунаправленных очередей, ассоциативных массивов и т.д. С помощью адаптеров итераторов мы можем получить итераторы для файлов, а также стандартных потоков ввода и вывода. Более того, как вы видели в предыдущей главе, можно даже обернуть интерфейсы итераторов вокруг алгоритмов. Теперь, когда итераторы помогают нам получить доступ ко всему, можно объединить их с алгоритмами STL, которые принимают итераторы в качестве параметров.
На примере алгоритма std::copy можно легко понять, как итераторы помогают абстрагировать природу разных структур данных. Он просто копирует элементы из одного набора итераторов в итератор вывода. При использовании подобных алгоритмов не нужно знать о природе структуры данных, с которой мы работаем.
Как это делается
В этом примере мы разберем разные варианты алгоритма std::copy.
1. Сначала включим заголовочные файлы для всех структур данных, которые будем использовать. Кроме того, объявим, что задействуем пространство имен std:
#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <tuple>
#include <iterator>
#include <algorithm>
using namespace std;
2. Далее будем использовать пары, содержащие целое число и строку. Чтобы красиво вывести их на экран, нужно перегрузить оператор потока <<:
namespace std {
ostream& operator<<(ostream &os, const pair<int, string> &p)
{
return os << "(" << p.first << ", " << p.second << ")";
}
}
3. В функции main заполним вектор пар «число — строка» некоторыми значениями по умолчанию. Кроме того, объявим переменную map, связывающую численные и строковые значения:
int main()
{
vector<pair<int, string>> v {
{1, "one"}, {2, "two"}, {3, "three"},
{4, "four"}, {5, "five"}};
map<int, string> m;
4. Теперь воспользуемся алгоритмом std::copy_n, чтобы скопировать три пары из вектора в ассоциативный массив. Поскольку векторы и ассоциативные массивы значительно отличаются друг от друга, нужно выполнить преобразование элементов вектора с помощью параметра адаптера insert_iterator. Его предоставляет функция std::inserter. Пожалуйста, всегда помните о том, что использование алгоритмов наподобие std::copy_n в комбинации с итераторами вставки — наиболее обобщенный способ скопировать/вставить элементы в другие структуры данных, хотя и не самый быстрый. Зачастую эффективнее всего для вставки элементов применять функции-члены конкретных структур данных.
copy_n(begin(v), 3, inserter(m, begin(m)));
5. Выведем содержимое ассоциативного массива. На протяжении книги мы часто выводили на экран содержимое контейнера с помощью функции std::copy. Итератор std::ostream_iterator значительно помогает в этом вопросе, поскольку позволяет считать выходные данные пользовательской консоли еще одним контейнером, в который можно скопировать данные.
auto shell_it (ostream_iterator<pair<int, string>>{cout,
", "});
copy(begin(m), end(m), shell_it);
cout << 'n';
6. Опустошим ассоциативный массив, чтобы подготовить его к следующему эксперименту. В этот раз мы переместим в него все элементы вектора:
m.clear();
move(begin(v), end(v), inserter(m, begin(m)));
7. Теперь снова выведем на экран содержимое ассоциативного массива. Более того, поскольку алгоритм std::move изменяет еще и источник данных, выведем на экран и содержимое вектора. Таким образом, можно увидеть, что с ним произошло, когда он стал источником данных.
copy(begin(m), end(m), shell_it);
cout << 'n';
copy(begin(v), end(v), shell_it);
cout << 'n';
}
8. Скомпилируем программу, запустим ее и посмотрим на результат. Первые две строки выглядят просто. Они отражают содержимое ассоциативного массива после применения алгоритмов copy_n и move. Третья строка выглядит интереснее, поскольку в ней показывается, что строки вектора, который мы использовали в качестве источника данных, теперь пусты. Это произошло потому, что содержимое строк было не скопировано, а перемещено (т.е. ассоциативный массив применяет данные строк из кучи, на которые ссылались объекты строк, размещенные в векторе).
Мы не должны получать доступ к элементам, находящимся в источнике данных, до того, как изменятся их значения, но в целях эксперимента проигнорируем данное правило.
$ ./copying_items
(1, one), (2, two), (3, three),
(1, one), (2, two), (3, three), (4, four), (5, five),
(1, ), (2, ), (3, ), (4, ), (5, ),
Как это работает
Поскольку алгоритм std::copy является одним их самых простых алгоритмов STL, его реализация очень короткая. Взглянем на то, как его можно было бы реализовать:
template <typename InputIterator, typename OutputIterator>
OutputIterator copy(InputIterator it, InputIterator end_it,
OutputIterator out_it)
{
for (; it != end_it; ++it, ++out_it) {
*out_it = *it;
}
return out_it;
}
Этот код выглядит как попытка вручную реализовать копирование элементов из одного итерабельного диапазона в другой. Кто-то может задаться вопросом: «Почему бы и не реализовать его вручную? Цикл выглядит достаточно просто, и мне даже не понадобится возвращаемое значение». Это, конечно, хороший вопрос.
Хотя алгоритм std::copy не самый лучший пример и не может продемонстрировать, как код становится короче, другие алгоритмы выглядят гораздо сложнее. Это может быть неочевидно, но для алгоритмов STL выполняется скрытая оптимизация. Если мы будем пользоваться алгоритмом std::copy для структур данных, которые хранят свои элементы в непрерывной памяти (например, std::vector и std::array), и самим элементам будет легко присвоить копию, то компилятор выберет совершенно другую реализацию (предполагается, что типом итератора является указатель):
template <typename InputIterator, typename OutputIterator>
OutputIterator copy(InputIterator it, InputIterator end_it,
OutputIterator out_it)
{
const size_t num_items (distance(it, end_it));
memmove(out_it, it, num_items * sizeof(*it));
return it + num_items;
}
Перед вами упрощенная версия реализации алгоритма std::copy с помощью memmove. Она работает быстрее, чем стандартная версия с циклами, и в то же время не такая читабельная. Но тем не менее пользователи алгоритма std::copy автоматически получают от него выгоду, если типы их аргументов соответствуют требованиям, выполнение которых необходимо для оптимизации. Компилятор выбирает для заданного алгоритма самую быструю реализацию из возможных, а код пользователя выражает, что именно делает алгоритм, не обрастая ненужными деталями.
Алгоритмы STL зачастую предоставляют наилучшее сочетание читабельности и оптимальности реализации.
