Бьерн Страуструп. Язык программирования С++. Специальное издание (2011) (1004033), страница 126
Текст из файла (страница 126)
Функциональные объекты предоставляют контейнеру информацию, необходимую для работы с пользовательскими данными. Поэтому в настоящем разде- Глава (8. Алгоритмы и классы функциональных объектов 608 ле рассмотрение функциональных объектов фокусируется на том, как их можно создать и использовать. 18.2. Обзор алгоритмов стандартной библиотеки На первый взгляд может показаться, что в стандартной библиотеке алгоритмов несметное число.
Однако ж, их всего 60. Я нередко встречал классы, содержашие большее число функций-членов. Многие алгоритмы имеют между собой много общего в интерфейсе и поведении, что облегчает их изучение и понимание. Как и в случае с обшеязыковыми средствами, программист может использовать лишь те алгоритмы, которые ему понятны и действительно нужны. Нет никакой необходимости и заслуги в том, чтобы использовать в программе как можно больше алгоритмов, или заменять простые и очевидные алгоритмы на сложные и хитроумные. Помните — очень важно писать программы наиболее очевидным и простым способом, чтобы их потом можно было легко читать и понимать (это важно даже для автора программы).
С другой стороны, перед тем, как проделать что-то с элементами контейнера, подумайте, нет ли готового стандартного алгоритма для решения этой задачи. Если универсальный алгоритм уже есть, то зачем заново изобретать колесо? Каждый алгоритм задается функциональным шаблоном 513.3) или набором функциональных шаблонов, Поэтому алгоритмы могут работать с последовательностями элементов разных типов. Те алгоритмы, которые возвращают итератор (819.3), в качестве сигнала о неудаче возвращают как правило итератор, указываюший на элемент, расположенный за концом входной последовательности.
Например: гоЫ Г(йзз<ззг!п8>ь Ь) ( йзг<згггп8>:: еопм йегагог р = йпй (Ь. Ьекгп (), Ь. ела(), "реей" ) (Г(р == Ь.епй() ) ( й не наизаи тргеа'" ) еЬе ( й здесь р указывает на кргеат ) ) Алгоритмы не выполняют контроля границ последовательностей (диапазонов) ни на входе, ни на выходе. Ошибки выхода за границы диапазонов должны предотвращаться иными способами (518.3.1, 519.3). Когда алгоритм возвращает нтератор, его тип тот же, что и у итераторов на входе алгоритма. В частности, аргументы алгоритма определяют, возвращается константный или неконстантный итератор. Например: го14 Г(1Ь1<(пг> ь й, еопм 1Ы<ззг(пя>ь Ь) ( йзз<1пз>:: йегагог р = у)пй (й.
(зе81п ( ), й. ела ( ), 4к) ) йтм<з(ппд>::еопзг йегагог а =у)пй(Ь.Ьед!п (), 1з. епй(), "й(пйь ); 18.2. Обзор алгоритмов стандартной библиотеки 609 Алгоритмы стандартной библиотеки реализуют множество полезных стандартных операций над элементами контейнеров, таких как просмотр, сортировка, поиск, вставка и удаление.
Стандартные алгоритмы объявлены в пространстве имен зМ и сосредоточены в заголовочном файле <а!8ог!г)ии>. Большинство распространенных алгоритмов столь просты, что соответствующие им шаблонные функции реализуются как встраиваемые, и циклы с применением алгоритмов сильно при этом выигрывают с точки зрения быстродействия. Стандартные функциональные объекты также объявляются в пространстве имен зга, но их определения сосредоточены в заголовочном файле <)Ьпспопа!>. Они также легко поддаются встраиванию. Немодифицирующие (неизменяющие значений и порядка следования элементов) алгоритмы используются для извлечения информации из последовательности элементов или для определения позиций элементов в этой последовательности (интервале): Немодифицирующие алгоритмы (918.5) <а!9ог)Фт> ,", аког еасй () Выполняет операцию для каждого элемента последовательности.
) фпЫ() Находит первое вхождение значения в последовательности ') уха у() Находит первое соответствие предикату в последовательности Находит значение одной последовательности а другой последовательности ) Япй Г1Р5( оу Находит пару смежныхзначений ~ афасепт ГтиИ() Подсчитывает число вхождений значения в последовательности ) соиит() Подсчитывает число соответствий предикату а последовательности соил( Д'() Находит первые элементы, для которых последовательности отличаются , 'ешиатсй () еаиа!() Возвращает тгие, если последовательности попарно эквивалентны ';, зеагсй () , )тпй епй() Находит первое вхождение подпоследоватепьности в последовательно Находит последне в последовательно одит и-ое вхо Большинство алгоритмов предоставляют пользователю возможность определить фактическую операцию, выполняемую над каждым элементом или парой элементов.
Это делает стандартные алгоритмы гораздо более универсальными и полезными, чем они кажутся на первый взгляд. В частности, пользователь может сам указать критерии эквивалентности и различия элементов Я)8.4.2). Где это уместно, наиболее очевидные операции предоставляются по умолчанию.
Модифицирующие алгоритмы имеют между собой мало общего, кроме очевидного факта, что они могут изменять значения элементов последовательности: Глава ) 8. Алгоритмы и классы функциональных объектов 610 Модифицирующие алгоритмы ($16.6) <а)дог)т)пп> Применяет операцию к каждому элементу последовательности. о агиуоггл ( ) ~ Копирует последовательность, начиная с первого элемента. ) сору() Копирует последовательность, начиная с ее последнего элемента.
~ сору ЬастпгаЫ() )( эггар() Меняет местами два элемента. а, указуемые итераторами ух последовательностей. 1м значением. оряющие предикату. Копирует последовательность, заменяя элементы с указанным значением. гор(асе сору( () ) Копирует последовательность, заменяя элементы, удовлетворяющие предикату. гер!асе сору тэ'() Заменяет все элементы заданным значением. , Утпо ,' 1тИ л () Заменяет первые и элементов заданным значением. Заменяет все элементы результатом операции.
еепегате ( ) еепегате п () гееоге ( ) Заменяет первые и элементов результатом операции. Удаляет элементы с указанным значением. гееоге ту'() Удаляет элементы, удовлетворяющие предикату. гееоге сору() Копирует последовательность, удаляя элементы с указанным значением. Копирует последовательность, удаляя элементы, удовлетворяющие предикату. гелтояе сору ту() ( ипйтие() Удаляет равные смежные элементы.
Копирует последовательность, удал илйтие сару() Меняет порядок следования элемен гегегзе ( ) Копирует последовательность в обр гегегзе сору() гоготе ( ) Циклически перемещает элементы. Копирует элементы в циклической п гоготе сору () галеота зйиЯте () Перемещает элементы последовательности в случайном порядке. Всякий хороший программный проект несет на себе индивидуальные черты проектировщиков и их интересы. Контейнеры и стандартные алгоритмы явно отражают намерение предоставить базовую основу для классических структур данных и алгоритмов работы с ними.
Стандартная библиотека не только предоставляет минимум необходимых каждому программисту контейнеров и апгоритмов, но и содержит инструменты, необходимые для поддержки стандартных алгоритмов и лля расширения библиотеки за пределы этого минимума. 18.2. Обзор алгоритмов стандартной библиотеки довательности (518.7) <а(дог!1)тпт> ка с хорошей среднеи эффективностью ка с сохранением порядка эквивалентных ивает первую часть последовательности , упорядочивая первую часть результата ) Ставит и-ый элемент на нужное место пга е1етепт() 1ояег ЬоипФ( () ) ~ Находит первое вхождение значения. ) Находит первый элемент, больший заданного значения. ире~ ЬоипФ( () ) еоиа! галле() Ыпа~у зеагсй ( мегее () ) Сли , Слияние двух последовательно отсортирова ' последовательностей.
Перемещает вперед элементы, удовлетворя предикату. раг(1йои ( ) ) Перемещает вперед элементы, удовлетворяю ) предикату, сохраняя их относительный поря зтаЫе раг(!пои () Алгоритмы для работы со множествами ($18.7.5) <в)дог!Фпт> Возвращает (гие, если последовательность является подпоследовательностью другой последовательности. 1ис1иае» ( ) Конструирует сортированное зет ип!оп () зет !п1егеесйоп () ) Конструирует сортированное ) Конструирует сортированную ) элементов, входящих в перву ) последовательность. зег й~~егеисе () зет деиитетпс афегепсе() Конструирует сортированную элементов, входящих в одну и В настоящем разделе упор делается не на проектировании алгоритмов, и даже не на их использовании (за исключением очевидных и простейших случаев). По поводу этих вопросов лучше обратиться к другой литературе (например, (Кпп()), !968) или [Тат)ап, 1983]). Мы же просто перечисляем алгоритмы стандартной библиотеки и объясняем, как они реализуются на языке С++.
Это позволит разобравшемуся в алгоритмах программисту правильно использовать стандартную библиотеку и расширять ее на основе принципов, на которых она сама и построена. Стандартная библиотека предоставляет множество вариантов сортировки, поиска и иных путей манипулирования упорядоченными последовательностями: Глава 18. Алгоритмы и классы функциональных объектов 612 Операции с кучей поддерживают последовательность в состоянии, облегчающей сортировку в случае возникновения такой необходимости; Операции с кучей (818.8) <а10ог(т)тпт> ! Г тале Авар() , 'Подготавливает последовательность к использованию ) в качестве кучи Добавляет элемент к куче Т удаляет элемент из кучи 1с р ру- уу В библиотеке имеется ряд алгоритмов для выбора элементов, основанных на сравнении: Минимум и максимум ($18.9) <а10ог(1(тгп> ~ Меньшее из двух значений Большее из двух значений.
ие в последовательности ие в последовательности первая иэ двух последовательностей гнраге Наконец, библиотека позволяет осуществлять перестановки элементов последовательности: рестаиовки ($18.10) <а10ог(1)ип> ледующая перестановка в пексикографическом порядке редыдущая перестановка в пексикографическом порядке. Кроме того, несколько обобщенных численных алгоритмов определены в заголовочном файле <нитеггс> (522.6). В описании алгоритмов имена параметров шаблона важны. 1н, Оиг, Рог, Вг и Ван означают, соответственно: итератор ввода, итератор вывода, прямой итератор, двунаправленный итератор и итератор произвольного доступа (819.2.1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
