О Обе формы «сворачивают» серии одинаковых элементов, оставляя начальный элемент и удаляя последующие дубликаты.

О Первая форма удаляет из интервала [beg,end) каждый элемент, равный предыдущему элементу. Таким образом, дубликаты удаляются только в том случае, если интервал был предварительно отсортирован (или, по крайней мере, если все элементы с одинаковыми значениями хранятся в смежных позициях).

О Вторая форма удаляет все элементы, следующие за элементом е, для которых бинарный предикат ор{е1етп,е) возвращает true. Иначе говоря, предикат используется для сравнения элемента не с предшественником, а с предыдущим элементом, который не был удален (см. пример).

О Обе формы возвращают новый логический конец модифицировашюго интервала (то есть позицию за последним элементом, который не был удален).

О Алгоритмы заменяют «удаленные» элементы следующими элементами, которые не были удалены.

О Алгоритмы сохраняют порядок следования элементов, которые пе были удалены.

О Вызывающая сторона должна использовать новый логический конец интервала вместо исходного конца end (за дополнительной информацией обращайтесь на с. 122).

О Предикат ор не должен изменять свое состояние во время вызова. За подробностями обращайтесь па с. 303.

О Вследствие модификации эти алгоритмы не могут использоваться с ассоциативными контейнерами (см. с. 125).

О Для списков определена аналогичная функция unique(), которая часто работает более эффективно, поскольку она меняет внутренние указатели вместо присваивания значений элементам (см. с. 250).

О Сложность линейная (numberOfElements сравнений или вызовов ор соответственно).

Пример использования алгоритма unique():

algo/uniquel.cpp finclude "algostuff-hpp" using namespace std;

int mainO {

Исходные данные

int sourceC] - ( 1. 4. 4. 6. 1. 2. 2. 3. 1. 6, 6. 6. 5. 7. 5. 4. 4 };

int sourceNurr * sizeof(source)/sizeof(source[0]); list<1nt> coll;

Инициализация coll элементами source copy (source. source+sourceNum, Источник

back inserter(coll)); Приемник

PRiNTJLEMENTSCcoll);

Удаление последовательных дубликатов

list<int>:literator pos;

pos = unique (coll.beginO. coll.endO);

/* Вывод оставшихся элементов * - с использованием нового логического конца */

сору (coll.beginO, pos. Источник

ostream iterator<int>(cout." ")): Приемник cout « "\п\п";

Повторная инициализация coll элементами source сору (source. source+SQurceNurr, Источник

coll.beginO); Приемник

PRINTjLEMENTS(coll);

Удаление элемента, если ему предшествует элемент с большим значением coll.erase (unique (coll.beginO. coll.endO.

greater<int>()). coll .endO): PRlNTjLEMENTS(con);

Результат выполнения программы выглядит так:

14461223166657544 146123165754

14461223166657544 1 4 4 6 6 6 6 7

Первый вызов uniqueO уничтожает последовательные дубликаты. Второй вызов показывает, как работает вторая форма алгоритма. Из коллекции удаляются все элементы, следующие за текущим элементом, для которых сравнение критерием greater дает результат true. Например, первый элемент 6 больше следующих за ним элементов 1, 2, 2, 3 и 1, поэтому все эти элементы удаляются. Иначе говоря, предикат сравнивает элемент не с предшественником, а с предыдущим элементом, который не был удален (другой пример приведен далее при описании алгоритма unique copy()).

Удаление дубликатов при копировании

Outputlterator

unlque copy (Inputlterator sourceBeg. Inputlterator sourceEnd. Outputlterator destBeg)

Outputlterator

un1que copy (Inputlterator sourceBeg, Inputlterator sourceEnd, Outputlterator destBeg. BinaryPredicate op)

О Обе формы являются объединением алгоритмов сору() и unique().

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

О Обе формы возвращают позицию за последним скопированным элементом в приемном интервале (то есть позицию первого элемента, который не был заменен).

О Перед вызовом необходимо убедиться в том, что приемный интервал имеет достаточный размер, или использовать итераторы вставки.

О Сложность линейная (numberOfElements сравнений или вызовов ор и присваиваний соответственно).

Пример использования алгоритма unique copy();

algo/umque2,cpp #lnclude "algostuff.hpp" using namespace std:

bool dIfferenceOne (int elemi, int elem2)

return elemi + 1 == elerr2 elemi - 1 == elem2:

int mainO {

Исходные данные

int sourceC] =(1,4. 4, 6. 1. 2. 2. 3. 1, 6, 6, 6. 5. 7, 5. 4, 4 ):

int sourceNum = sizeof(source)/sizeof(source[0]):

Инициализация coll элементами source list<int> coll:

copyCsource. source+sourceNum, Источник back inserter(coll)): Приемник

PRINTJLEMENTSCcoll):

ВЫ80Д содержимого coll с удалением смежных дубликатов unique copy(coll .beginO . coll.endO. Источник

ostream iterator<int>(cout," ")): Приемник cout « endl:

Вывод содержимого coll с удалением смежных элементов

со значениями, отличающимися на 1

unlque copy(col 1 .begin(). coll.endO. Источник

ostream iterator<int>(cout." "). Приемник differenceOne); Критерий удаления

cout « endl;

Результат выполнения программы выглядит так: 14461223166657544