Алгоритмы. STL (часть 10)

Контейнеры STL представляли бы собой красивую выдумку достаточно далёкую от практического использования (как и было в первые годы существования STL), если бы не следующее обстоятельство: из-за единой общей природы всех контейнеров основные алгоритмы, представляющие интерес на практике, могут быть реализованы в обобщённом виде, применимом к любым типам контейнеров.

Алгоритмы — это самая объёмная и самая востребованная часть библиотеки. Предоставляется настолько много алгоритмов, что для детального описания их всех не хватит и объёмной книги. Ниже мы совершенно условно поделим их на группы и назовём по именам (и тоже далеко не все), и только по некоторым построим примеры использования.

for_each() Наиболее часто используемый алгоритм — это for_each(): выполнение действия для группы элементов (возможно всех) контейнера. Ниже показано несколько примеров работы алгоритма for_each() для массива и вектора, точно также этот алгоритм может использоваться с любым контейнером STL:

Примечание: Строкой 3 показана работа новой (введена стандартом C++11) конструкции for( auto &x : …), которая имеет подобный эффект присвоения и может применяться и к массивам и к контейнерам (в функции-операторе вывода вектора в поток показан такой вариант). Эта конструкция, вообще то говоря, не является составной частью библиотеки STL или алгоритмов, но имеет тот же эффект, что и алгоритм for_each(): применить последовательно ко всем элементам коллекции.  

Этот пример показывает основную логику организации всех алгоритмов: к указанному диапазону (не обязательно ко всей коллекции), ограниченному итератором начала и конца (зачастую указываемых первыми 2-мя параметрами) применяется поочерёдно функция, функтор, или предикат (функция, возвращающая логиxческий результат, позволяющий произвести отбор по какому-либо признаку).

find() Следующий по значимости алгоритм — это find(). Как интуитивно понятно из имени, это поиск некоторого элемента в коллекции. Обратите внимание, что многие контейнеры имеют метод find(), который для объекта будет вызываться как obj.find(…), в то время как алгоритм будет вызываться как find( obj:iteator, … ).

Собственно, это даже не один этот алгоритм, а целая обширная их группа, которую можно объединить по признаку того, что они отбирают элементы коллекции по какому-то признаку, условию, предикату: find(), find_if(), find_if_not(), find_first_of(), find_end(), adjacent_find(). В эту же группу, с некоторой натяжкой, можно отнести и count(), count_if(), search(), binary_search(), min(), max(), minmax_element(), min_element(), max_element(), equal() и др.

Ещё одна условная группа — это алгоритмы, некоторым образом «тасующие» коллекцию, переставляющие элементы местами, меняющие значения: fill(), replace_copy(), reverse(), rotate(), rotate_copy(), shuffle(), random_shuffle(), transform(), replace(), replace_if() и др.

Ещё группа — это алгоритмы работающие с 2-мя коллекциями, копирующие и перемещающие содержимое (причём, возможно, между коллекциями разного вида, например, vector<> в set<>): copy(), copy_if(), move(), swap_ranges(), remove_copy(), remove_copy_if(), merge(), set_intersection(), set_difference() и др.

И, наконец, совсем особая группа алгоритмов связана с разнообразными сортировками элементов внутри коллекции: sort(), stable_sort(), is_sorted(), is_sorted_until() и др. Эту интересную группу мы отложим на потом, для отдельного обстоятельного рассмотрения.

При таком обилии реализованных алгоритмов и число которых в библиотеке со временем возрастает, и при том, что большинство из них вообще толком нигде не описаны в литературе, возникает естественный вопрос: как разобраться во всём этом разнообразии? Эти сложности снимаются тем что:

• Все объекты STL (контейнеры, алгоритмы) описаны в синтаксисе шаблонов (template). Поэтому их описания обязательно должны включаться в компилируемый код в составе своих заголовочных файлов (хедер-файлов).

• Отправляйтесь в стандартный каталог </usr/include/c++> и найдите там хедер-файлы файлы вида stl_algo* — в них вы найдёте все прототипы функций алгоритмов. Более того, там же каждому прототипу предшествует обстоятельный комментарий, объясняющий назначение алгоритма, и объясняющий параметры вызова.

• Рассмотрите примеры кода, использующие несколько основных алгоритмов STL — в сети их множество. По аналогии элементарно просто воспроизвести поведение и всех остальных алгоритмов.

Примечание: Вот из-за того, что библиотеки шаблонных классов определены в терминах template, сообщения об синтаксических ошибках компиляции становятся а). многословными, на десятки строк сообщений и б). ужасно невнятными для поиска ошибок. Это оборотная сторона медали такого мощного механизма как template, и к этому нужно быть готовым.

Как и было сказано выше, изучение примеров снимет множество вопросов, а поэтому приступим к коду … Теперь внимательно следите за руками (алгоритмов STL такое множество, что комментировать каждый – за пределами разумного объёма изложения, но все они работают подобно один другому):

Здесь использованы контейнеры для char (как компактные, но самые неприятные в работе), над которыми выполняются разнообразные алгоритмы практически всех обозначенных групп: