copy(), copy backwards(), iter swap(), remove(), remove copy (), remove if(),remove if copy(), replace(), replace copy(), replace if(), replace copy if(), swap(), swap range(), unique(),

адресованных парой итераторов, но не модифицирует сами итераторы.

unique copy()

12.5.4. Алгоритмы перестановки

Рассмотрим последовательность из трех символов: {a,b,c}. Для нее существует шесть различных перестановок: abc, acb, bac, bca, cab и cba, лексикографически упорядоченных на основе оператора меньше . Таким образом, abc - это первая перестановка, потому что каждый элемент меньше последующего. Следующая перестановка - acb, поскольку в начале все еще находится a - наименьший элемент последовательности. Соответственно перестановки, начинающиеся с b, предшествуют тем, которые начинаются с с. Из bac и bca меньшей является bac, так как последовательность ac лексикографически меньше, чем ca. Если дана перестановка bca, то можно сказать, что предшествующей для нее будет bac, а последующей - cab. Для перестановки abc нет предшествующей, а для cba - последующей.

next permutation() , prev permutation()

12.5.5. Численные алгоритмы

Следующие четыре алгоритма реализуют численные операции с контейнером. Для их использования необходимо включить заголовочный файл <numeric>.

accumulate(), partial sum(), inner product(), adjacent difference()

12.5.6. Алгоритмы генерирования и модификации

Шесть алгоритмов генерирования и модификации либо создают и заполняют новую последовательность, либо изменяют значения в существующей.

fill(), fill n(), for each(), generate(),generate n(), transform()

12.5.7. Алгоритмы сравнения

Семь алгоритмов дают разные способы сравнения одного контейнера с другим (алгоритмы min() и max() сравнивают два элемента). Алгоритм

12.5.3. Алгоритмы удаления и подстановки

Пятнадцать алгоритмов удаления и подстановки предоставляют различные способы замены или исключения одного элемента или целого диапазона. unique() удаляет одинаковые соседние элементы. iter swap() обменивает значения элементов,

set union(), set intersection(), set difference(),

но не обоим.

set symmetric difference()

12.5.9. Алгоритмы работы с хипом

Хип (heap) - это разновидность двоичного дерева, представленного в массиве. Стандартная библиотека предоставляет такую реализацию хипа, в которой значение ключа в любом узле больше либо равно значению ключа в любом потомке этого узла.

make heap(), pop heap(), push heap(), sort heap()

12.6. Когда нельзя использовать обобщенные алгоритмы

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

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

vector<string>::iterator vec iter = vec.begin() + 7;

lexicographical compare() выполняет лексикографическое (словарное) упорядочение

equal(), includes(), lexicographical compare(), max(), max element(),

(см. также обсуждение перестановок и Приложение).

min(), min element(), mismatch()

12.5.8. Алгоритмы работы с множествами

Четыре алгоритма этой категории реализуют теоретико-множественные операции над любым контейнерным типом. При объединении создается отсортированная последовательность элементов, принадлежащих хотя бы одному контейнеру, при пересечении - обоим контейнерам, а при взятии разности - принадлежащих первому контейнеру, но не принадлежащих второму. Наконец, симметрическая разность - это отсортированная последовательность элементов, принадлежащих одному из контейнеров,

ошибка: арифметические операции над итераторами не поддерживаются списком

вектора, но запись

list<string>::iterator list iter = slist.begin() + 7;

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

Поскольку список не поддерживает произвольного доступа, то алгоритма: merge(), remove() , reverse() , sort() и unique() лучше к таким контейнерам не применять, хотя ни один из них явно не требует наличия соответствующего итератора. Вместо этого для списка определены специализированные версии названных операций в виде функций-членов, а также операция splice() :

list::merge() объединяет два отсортированных списка

list::remove() удаляет элементы с заданным значением

list::remove if() удаляет элементы, удовлетворяющие некоторому условию

list::reverse() переставляет элементы списка в обратном порядке

list::sort() сортирует элементы списка

list::splice() перемещает элементы из одного списка в другой

list::unique() оставляет один элемент из каждой цепочки одинаковых смежных элементов

void list::merge( list rhs ); template <class Compare>

12.6.1. Операция list merge()

void list::merge( list rhs, Compare comp );

Элементы двух упорядоченных списков объединяются либо на основе оператора меньше , определенного для типа элементов в контейнере, либо на основе указанной пользователем операции сравнения. (Заметьте, что элементы списка rhs перемещаются в список, для которого вызвана функция-член merge() ; по завершении операции список rhs будет пуст.) Например:

Такая форма вполне допустима и инициализирует vec iter адресом восьмого элемента