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

find(), find_end(), find_first_of(), find_if(), lower_bound(),

upper_bound(), search(), search_n()

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

Четырнадцать алгоритмов сортировки и упорядочения предлагают различные способы упорядочения элементов контейнера. Разбиение (partition) – это разделение элементов контейнера на две группы: удовлетворяющие и не удовлетворяющие некоторому условию. Так, можно разбить контейнер по признаку четности/нечетности чисел или в зависимости от того, начинается слово с заглавной или со строчной буквы. Устойчивый (stable) алгоритм сохраняет относительный порядок элементов с одинаковыми значениями или удовлетворяющих одному и тому же условию. Например, если дана последовательность:

{ "pshew", "honey", "Tigger", "Pooh" }

то устойчивое разбиение по наличию/отсутствию заглавной буквы в начале слова генерирует последовательность, в которой относительный порядок слов в каждой категории сохранен:

{ "Tigger", "Pooh", "pshew", "honey" }

При использовании неустойчивой версии алгоритма сохранение порядка не гарантируется. (Отметим, что алгоритмы сортировки нельзя применять к списку и ассоциативным контейнерам, таким, как множество (set) или отображение (map).)

inplace_merge(), merge(), nth_element(), partial_sort(),

partial_sort_copy(), partition(), random_shuffle(), reverse(),

reverse_copy(), rotate(), rotate_copy(), sort(), stable_sort(),

stable_partition()

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

Рассмотрим последовательность из трех символов: {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.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() сравнивают два элемента). Алгоритм lexicographical_compare() выполняет лексикографическое (словарное) упорядочение (см. также обсуждение перестановок и Приложение).

equal(), includes(), lexicographical_compare(), max(), max_element(),

min(), min_element(), mismatch()

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