С++ для начинающих




Обобщенные алгоритмы


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

// читается так: включает первый и все последующие элементы,

// кроме последнего

[ first, last )

Эта запись говорит о том, что диапазон начинается с элемента first и продолжается до элемента last, исключая последний. Если

first == last

то говорят, что диапазон пуст.

К паре итераторов предъявляется следующее требование: если начать с элемента first и последовательно применять оператор инкремента, то возможно достичь элемента last. Однако компилятор не в состоянии проверить выполнение этого ограничения; если оно нарушается, поведение программы не определено, обычно все заканчивается аварийным остановом и дампом памяти.

В объявлении каждого алгоритма указывается минимально необходимая категория итератора (см. раздел 12.4). Например, для алгоритма find(), реализующего однопроходный обход контейнера с доступом только для чтения, требуется итератор чтения, но можно передать и однонаправленный или двунаправленный итератор, а также итератор с произвольным доступом. Однако передача итератора записи приведет к ошибке. Не гарантируется, что ошибки, связанные с передачей итератора не той категории, будут обнаружены во время компиляции, поскольку категории итераторов – это не собственно типы, а лишь параметры-типы, передаваемые шаблону функции.

Некоторые алгоритмы существуют в нескольких версиях: в одной используется встроенный оператор, а во второй – объект-функция или указатель на функцию, которая предоставляет альтернативную реализацию оператора. Например, unique() по умолчанию сравнивает два соседних элемента с помощью оператора равенства, определенного для типа объектов в контейнере. Но если такой оператор равенства не определен или мы хотим сравнивать элементы иным способом, то можно передать либо объект-функцию, либо указатель на функцию, обеспечивающую нужную семантику. Встречаются также алгоритмы с похожими, но разными именами. Так, предикатные версии всегда имеют имя, оканчивающееся на _if, например find_if(). Скажем, есть алгоритм replace(), реализованный с помощью встроенного оператора равенства, и replace_if(), которому передается объект-предикат или указатель на функцию.




Содержание  Назад  Вперед