Outputlterator unique copy(Inputlterator first. Inputlterator last. Outputlterator result. BinaryPredicate binary pred):

Версии с префиксом unique перебирают интервал [firstlast), находят в нем смежные эквивалентные значения и удаляют дубликаты, копируя следующие элементы поверх них. При этом сохраняется исходный порядок следования неудаленных элементов. Возвращаемое значение представляет собой конечный итератор для интервала, полученного после удаления смежных дубликатов.

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

Для каждого значения итератора i в исходном интервале версии с бинарным предикатом binary pred вызывают

binary pred(*i. *(i-l)): Если результат равен true, *i считается дубликатом.

Версии с суффиксом сору не изменяют исходный интервал; они копируют неудаленные элементы в интервал, начинающийся с result, и возвращают конечный итератор для этого нового интервала.

Следующая программа наглядно демонстрирует работу алгоритмов семейств remove и unique:

: СОб:Removing.срр Алгоритмы удаления {L} Generators linclude <algorithm> linclude <cctype> linclude <string> linclude Generators.h linclude PrintSequence.h using namespace std:

struct IsUpper { bool OperatorO(char c) { return isupper(c): }

int mainO { string v: v.resize(25):

generate(V.beginO. v.endO. CharGenO):

print(v.beginO. v.endO, v original . ):

Создание набора символов на базе v:

string us(v.beginO, v.endO):

sort (us. begi nO. us.endO):

string::iterator it = us.beginO, cit = v.endO.

uend = unique(us.begin(). us.endO): Перебор и удаление всего содержимого: while(it != uend) {

cit = remove(v.begin(). cit. *it):

print(v.beginO. v.endO. Complete v . ):

print(v.begin(). cit. Pseudo v . ):

cout Removed element:\t *it \nPseudo Last Element:\t *cit endl endl:

it++:

generateCv.beginO. v.endO. CharGenO):

print(v.beginO. v.endO. v . ):

cit = removejf(v.beginO. v.endO. IsUpperO):

print(v.beginO. cit. v after rerovejf IsUpper . ):

Копирующие версии renrave и renravejf не показаны.

sortCv.beginO. cit):

printCv.beginO. cit. sorted . );

string v2:

v2.resize(cit - v.beginO): unique copy(v.begin(). cit. v2.beginO): print(v2.beginO. v2.endO. unique copy , ); Работает так же:

cit - uniqueCv.beginO. cit. equa1 to<char>()); printCv.beginO. cit. unique equal to<char> . ):

} III:-

Строка V представляет собой контейнер, заполненный случайно сгенерированными символами. Символы последовательно удаляются вызовом remove, но при этом каждый раз выводится полная строка v, чтобы вы могли проследить за состоянием всего интервала после текущей конечной точки (cit).

Для демонстрации алгоритма removeJf() мы вызываем стандартную библиотечную функцию isupper() языка С (заголовочный файл <cctype>) внутри объекта функции IsUpper, переданного в качестве предиката removeJfQ. Предикат возвращает true для символов верхнего регистра, поэтому в итоге в интервале остаются только символы нижнего регистра. При вызове print() передается новый конец интервала, поэтому выводятся только оставшиеся элементы. Копирующие версии remove() и removeJf() не приводятся, так как они принципиально не отличаются от некопирующих версий, и отдельные примеры для них не нужны.

Перед тестированием алгоритмов unique мы сортируем полученный интервал строчных букв (эти алгоритмы могут применяться и к несортированным интервалам, но, вероятно, это не приведет к ожидаемому результату). Сначала unique copy() заносит уникальные элементы в новый вектор (способ сравнения э)1ентов определяется по умолчанию), а затем использует форму unique() с передачей предиката. Предикатом является стандартный объект функции equaLto(), который дает тот же результат, что и при сравнении по умолчанию.

Сортировка и операции с отсортированными интервалами

Значительная часть алгоритмов STL работает только с отсортированными интервалами. Библиотека STL содержит разные алгоритмы сортировки, и выбор зависит от того, какой должна быть сортировка: устойчивой, неустойчивой или неполной. Как ни странно, версия с копированием предусмотрена только для неполной сортировки. Если вы используете другой тип сортировки, но при этом хотите работать с копией, вам придется самостоятельно скопировать интервал перед сортировкой.

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

Каждый алгоритм, связанный с сортировкой или операциями с сортированными интервалами, существует в двух версиях. Первая версия использует для определения относительного порядка элементов а и b оператор сравнения < самого объекта, а вторая - операторную функцию operator()(a,b) дополнительного бинарного предиката (объект StrictWeakOrdering). Никаких других различий не существует, поэтому данное обстоятельство не будет особо оговариваться в описании каждого алгоритма.

Сортировка

Алгоритмам сортировки должны передаваться интервалы, ограниченные итераторами произвольного доступа (например, векторы или деки). Контейнер list содержит встроенную функцию sort:(), поскольку он поддерживает только двусторонние итераторы.

void sort(RandomAccessIterator first. RandomAccessIterator last); void sort(RandomAccessIterator first. RandomAccessIterator last, StrictWeakOrdering binary pred):

Алгоритм сортирует интервал [firstlast) по возрастанию. Первая форма определяет порядок следования элементов при помощи оператора <, а вторая передает элементы заданному предикату.

void stable sort(RandomAccessIterator first,

RandomAccessIterator last): void stable sort(RandomAccessIterator first,

RandomAccessIterator last. StrictWeakOrdering binary pred):

Алгоритм сортирует интервал [firstlast) по возрастанию с сохранением исходного порядка следования эквивалентных элементов (это важно, если элементы могут быть эквивалентными, но не идентичными).

void partial sort(RandomAccessIterator first.

RandomAccessIterator middle, RandomAccessIterator last): void partial sort(RandomAccessIterator first,

RandomAccessIterator middle, RandomAccessIterator last,

StrictWeakOrdering binary pred):

Алгоритм сортирует элементы интервала [firstlast), которые могут boiith в интервал [firstmiddle). Остальные элементы оказываются в интервале [middle,last) без гарантированного порядка следования.

RandomAccessIterator partial sort copy(Inputlterator first,

Inputlterator last. RandomAccessIterator result first,

RandomAccessIterator result last): RandomAccessIterator partial sort copy(Inputlterator first.

Inputlterator last, RandomAccessIterator result first.

RandomAccessIterator resultjast. StrictWeakOrdering binary pred):

Алгоритм сортирует элементы интервала [firstlast), которые могут войти в интервал [result first result last), и копирует эти элементы в [result first, resultjast). Если интервал [firstlast) меньше [result first result last), используется меньшее количество элементов.

void nth element(RandomAccessIterator first,

RandomAccessIterator nth, RandomAccessIterator last): void nth element(RandomAccessIterator first.

RandomAccessIterator nth, RandomAccessIterator last,

StrictWeakOrdering binary pred): Алгоритм nth element(), как и partiaLsort(), частично упорядочивает интервал элементов. Тем не менее, результат получается гораздо менее упорядочен-