Стенли Липпман - Язык программирования C++. Пятое издание

Итератор прямого доступа необходим алгоритму sort(). Итераторы контейнеров array, deque, stringи vectorявляются итераторами прямого доступа, подобно указателям массива.

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

Упражнение 10.39. Итератором какой категории обладает список? А вектор?

Упражнение 10.40. Итераторы какой категории нужны алгоритму copy()? А алгоритмам reverse()и unique()?

Эта классификация алгоритмов основана на соглашениях об именах параметров. Понимание этих соглашений поможет в изучении новых алгоритмов: зная, что означает имя данного параметра, можно догадаться, какие операции выполняет соответствующий алгоритм. Большинство алгоритмов получают параметры в одной из четырех форм:

алг (beg, end, другие параметры );

алг (beg, end, dest, другие параметры );

алг (beg, end, beg2, другие параметры );

алг (beg, end, beg2, end2, другие параметры );

где алг — это имя алгоритма, а параметры begи endобозначают исходный диапазон элементов, с которыми работает алгоритм. Хотя почти все алгоритмы получают исходный диапазон, присутствие других параметров зависит от выполняемых действий. Как правило, остальные параметры, dest, beg2 и end2, также являются итераторами. Кроме них, некоторые алгоритмы получают дополнительные параметры, не являющиеся итераторами.

Параметр dest(destination — назначение) — это итератор, обозначающий получателя, используемого для хранения результата. Алгоритмы подразумевают, что способны безопасно записать в последовательность назначения столько элементов, сколько необходимо.

Алгоритмы, осуществляющие запись по итератору вывода, подразумевают, что получатель достаточно велик для содержания вывода.

Если destявляется итератором контейнера, алгоритм записывает свой результат в уже существующие элементы контейнера. Как правило, итератор destсвязан с итератором вставки (см. раздел 10.4.1) или итератором ostream_iterator(см. раздел 10.4.2). Итератор вставки добавляет новые элементы в контейнер, гарантируя, таким образом, достаточную емкость. Итератор ostream_iteratorосуществляет запись в поток вывода, а следовательно, тоже не создает никаких проблем независимо от количества записываемых элементов.

Алгоритмы, получающие один параметр ( beg2) или два параметра ( beg2и end2), используют эти итераторы для обозначения второго исходного диапазона. Как правило, для выполнения необходимых действий эти алгоритмы используют элементы второго диапазона вместе с элементами исходного.

Когда алгоритм получает параметры beg2и end2, эти итераторы обозначают весь второй диапазон. Такой алгоритм получает два полностью определенных диапазона: исходный диапазон, обозначенный итераторами [beg, end), а также второй, исходный диапазон, обозначенный итераторами [beg2, end2).

Алгоритмы, получающие только итератор beg2(но не end2), рассматривают итератор beg2как указывающий на первый элемент во втором исходном диапазоне. Конец этого диапазона не определен. В этом случае алгоритмы подразумевают, что диапазон, начинающийся с элемента, указанного итератором beg2, имеет, по крайней мере, такой же размер, что и диапазон, обозначенный итераторами begи end.

Алгоритмы, получающие один параметр beg2, подразумевают , что последовательность, начинающаяся с элемента, указанного итератором beg2, имеет такой же размер, как и диапазон, обозначенный итераторами begи end.

Кроме соглашений об именовании параметров, алгоритмы также имеют набор однозначных соглашений об именовании перегруженных версий. Эти соглашения учитывают то, как предоставляется оператор, используемый вместо принятого по умолчанию оператора <или ==, а также то, используется ли алгоритм для исходной последовательности или отдельного получателя.