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




алгоритмы stl, find(), copy(), copy_if(), move(), swap_ranges(), remove_copy(), remove_copy_if(), merge(), set_intersection(), set_difference()Контейнеры STL представляли бы собой красивую выдумку достаточно далёкую от практического использования (как и было в первые годы существования STL), если бы не следующее обстоятельство: из-за единой общей природы всех контейнеров основные алгоритмы, представляющие интерес на практике, могут быть реализованы в обобщённом виде, применимом к любым типам контейнеров. Алгоритмы — это самая объёмная и самая востребованная часть библиотеки. Предоставляется настолько много алгоритмов, что для детального описания их всех не хватит и объёмной книги. Ниже мы совершенно условно поделим их на группы и назовём по именам (и тоже далеко не все), и только по некоторым построим примеры использования.

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

алгоритмы stl, find(), count(), count_if(), search(), binary_search(), min(), max(), minmax_element(), min_element(), max_element(), equal()

Примечание: Строкой 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 (как компактные, но самые неприятные в работе), над которыми выполняются разнообразные алгоритмы практически всех обозначенных групп:

алгоритмы stl, find(), count(), count_if(), search(), binary_search(), min(), max(), minmax_element(), min_element(), max_element(), equal()

Рассылка новых уроков по программированию:

Дата
Страница
Алгоритмы. STL (часть 10)
Рейтинг
51star1star1star1star1star
Olej

Об авторе Olej

Стаж практических программных разработок около 40 лет. Преподаватель международной софтверной компании Global Logic. Постоянный автор публикаций IBM Developer Works. Научный редактор книжного издательства компьютерной литературы "Символ-Плюс", Санкт-Петербург.

Алгоритмы. STL (часть 10): 3 комментария

Добавить комментарий

Код размещайте в тегах: <pre class="lang:c++ decode:true ">YOUR CODE</pre>