Б. Страуструп - Язык программирования С++. Специальное издание, 3-изд. Бином. 2004 (1160791), страница 126
Текст из файла (страница 126)
Каждый алгоритм выражаешься шаблоном функции Я 13.8) или набором шаблонов функций, Таким образом, алгоритм может работать с очень разными последовательностями, содержа!ними значения разнообразных типов. Алгоритмы, которые возвращают итератор Я 19.1), как правило для сообщения о неудаче используют конец входной последовательности. Например: оо!д~!!!к1<ксг!пд> а !я! 1и1 <к1г!пд>: сопя! !1ега1огр =йспс! !Ь !эеясп 9, !я елд !э " Федор" ) !й" !р == ! я епс! Щ ( Д 'Федор' не найден еЬе1 О вот он,' р указывает на 'Федор" Алгоритмы не выполняют проверки диапазона на их входе и выходе. Ошибку выхода за пределы диапазона нужно стараться предотвратить другими средствами (8 18.3.1, з 19.3). Когда алгоритм возвращает итератор, это будет итератор того же типа, что и был на входе.
В частности, аргументамн алгоритма определяется, возвращает ли он константый итератор илн неконстаптный итератор. Наприлсер: оо!ЙЯ!1я1<ясг!ад> й !1, сопя1 !!я1<к1г!пд>Й !я! ! !! к1<ш 1>; !1егасог р =!с ос! !!с Ь ед!и 1!, !с ела !!, 421; !!я1<кгг!пд>сопя! !1ега1ог су=!!пд !!яЬерп !), Ь епд !),'Кольцо"~; Алгоритмы в стандартной библиотеке реализуют большинство распространенных универсальных операций с контейнерами, такие как просмотр, сортировку, поиск, вставку и удаление элементов.
Все стандартные алгоритмы находятся в пространстве имен я1ас, а их объявления — в заголовочном файле <а!аог!1Агп>. Интересно, что большинство действительно распространенных алгоритмов столь просты, что шаблонные функции, как правило, являются встроенными (сп!!лв). Благодаря этой агрессивной оптимизации на уровне каждой функции циклы выполняются значительно быстрее. Стандартные объекты-функции также находятся в пространстве имен я!с!, но их объявления помещены в <йапсг!ела!>.
Обьекты-функции рассчитаны нато, чтобы их было легко встраивать как !л!1пе. Немодифицирующпе операции с последовательностями используются для извлечения информации из последовательности или д тя определения положения:элемента в последовательности: 571 15.2. Обзор алгоритмов стандартной библиотеки Немодифицирующие операции с последовательностями (у 18.5) <а(8ог(т)пп> уог еасй() 1)лй () у)гЫ (1'() Выполняет операцию для каждого элемента последовательности Находит первое вхождение значения в последовательность Находит первое соответствие предикату (условию) в последовательности Находит значение из одной последовательности в другой Находит пару соседних значений Подсчитывает количество вхождений данного значения в последовательность Подстчитывает количество выполнений данного предиката в последовательности Находит первый элемент, в котором две последовательности различаются 1гие, если элементы в двух последовательностях попарно равны Находит первое вхождение последовательности как подпоследовательности Находит последнее вхождение последовательности как подпоследовательности Находит и-е вхождение значения в последовательность Япс~1)гз1 о1 () аг(1асеп1 3пс( () соип1 () соил1 Ф) т1зта1сй () еуиа1() зеагсй () рлс( еле(() зеагсЬ и () Модифицирующие операции с последовательностями (у 18.
6) <а(8оПС)ггп> 1галк~огт () Выполняет операцию над каждым элементом в последовательности Копирует последовательность, начиная с первого элемента Копирует последовательность, начиная с последнего элемента Меняет местами два элемента Меняет местами два элемента, на которые указывают итераторы Меняет местамп элементы двух последовательностей Заменяет элементы с указанным значением Заменяет элементы при выполнении предиката Копирует последовательность, заменяя элементы с указанным значением Копирует последовательность, заменяя элементы при выполнении преднката Заменяет все элементы данным значением сору () сору Ьас/исаям() р() 11ег зюар () зтар галдев () гер1асе () гер1асе (1'() гер1асе сору () гер1асе сору (1 () 1) 11 () Большинство алгоритмов дают пользователю возможность определить операцию, выполняемую над каждым элементом илп парой элементов.
Это делает алгоритмы более универсальными н полезными, чем онп кажутся на первый взгляд. В частности, пользователь может сам указать критерий равенства н различия (~ 18А.2). Где зто разумно, наиболее часто встречающиеся и полезные действия обеспечиваются по умолчанию. Модифицирующие операции с последовательностями имеют между собой мало общего, кроме того очевидного свойства, что все они могут изменять значение элементов в последовательности; Глава 18. Алгоритмы и объекты-функции 572 Модифицирующие операции с последовательностями (9 18.6) <а(8оп((тпг> (продолжение) ЯИ п() уепега1е (] уелега1е и () гетоое (] гетове гЯ гетоое сору () Заменяет первые и элементов указанным значением Заменяет все элементы результатом операции Заменяет первые п элементов результатом операции Удаляет элементы с данным значением Удаляет элементы при выполнении предиката Копирует последовательность, удаляя элементы с указанным значением Копирует последовательность, удаляя элементы, удовлетворяющие предикату Удаляет равные соседние элементы Копирует последовательность, удаляя равные соседние элементы Меняет порядок следования элементов па обратный Копирует последовательность в обратном порядке Перемещает элементы циклически Копирует элементы в циклической последовательности Перемещает элементы согласно случайному равномерному распределению (чтасуеть последовательность) гетоое сору г(() ипгуие () илгуие сору () г.евег.зе () геиегзе гоРУ() го1аге () го(а1е сору () г)от айте () Сортировка последовательностей (9 18,7) <а(8опт(тгп> зогг () з(аЫе зогг() Сортирует с хорошей средней эффективностью Сортирует, сохраняя порядок следования равных элементов Упорядочивает первую часть последовательности Копирует, упорядочивая первую часть результата Ставит на нужное место п-й элемент Находит первое вхождение значения ра«тгаг зогт () раг(гаг зо«1 сору() л16 егегпелг () гоше« Ьоигиг () Всякий хородпгй проект несет на себе следы индивидуальных особенностей и интересов проектировщика.
Контейнеры и алгоритмы стандартной библиотеки явно отражают тенденцию построения основы для работы с классическими алгоритмами н структурами данных. Стандартная библиотека обеспечивает не толысо минимум контейнеров и алгоритмов, необходимых практически каждому программисту, но также включает в себя многие программные средства, используемые этими алгоритмами и необходимые для расширения библиотеки за пределы этого минимума. Упор здесь делается не на проектировании алгоритмов и даже не па пх использовании (за исключением простейших и очевидных алгоритмов). По поводу проектирования и анализа алгоритмов следует обратиться к другой литературе (например, (Кпцг)г, 1968] или (Таг|ап, 1983)).
В настоящей главе перечислены алгоритмы, предлагаемые стандартной библиотекой, и объяснено, как они выражаются на С++. Такая методика позволит разобравшемуся в алгоритмах программисту правильно использовать библиотеку и расширять ее по тем же приницпам, согласно которым она была построена. Стандартная библиотека предоставляет большое число операции сортировки, поиска и манипулирования с каким-либо образом упорядоченными последовательностями: 573 18.2. Обзор алгоритмов стандартной библиотеки Сортировка последовательностей (ф 18.7) <а!иог11Ьтп> (продолжение) Находит первый элемент, больший чем значение Находит подпоследовательность с данным значением Указанное значение есть в отсортированной последовательности? Объединяетдвеотсортированные последовательности Объединяет две последовательно отсортированные последовательности Неремегцает вперед элементы, удовлетворяющие предикату Перемещает вперед элементы, удовлетворяющие предикату, сохраняя их относительный порядок следования иррег Ьоалй() ег7иа! га«ае() Ь!«агу зеагсй () тегве () тр!асе тегде () раг!!!!о«() з!аб!е рагШ!оп () Алгоритмы для работы с множествами (9 18.7.5) <а(фог11Ьш> тс!ийез () !гие, если последовательность является подпоследовательностью другой Конструирует отсортированное обьединение Конструирует отсортированное пересечение Конструирует отсортированную последовательность элементов, входящих в первую, но не входящих во вторую последовательность Конструирует отсортированную последовательность элементов, присутствующих лишь в одной из двух последовательностей зе! ил!о«() зе! !и!егзес!!оп () зе! й(Яегепсе (] зе! зутте!г(с й(Яегепсе () Операции с кучей поддерживают последовательность в состоянии, облегчающем с ортировку (если в пей возникает необходимость): Операции с кучей (ф 18.8) <а)яоп1Ьпт> тайе беар () Подготавливает последовательность к использованию в качестве кучи Добавляет в кучу элемент Удаляет из кучи элемент Сортирует кучу ризЬ Ьеар() рор Ьеар() зог! Ьеар () Минимумы и максимумы (ф 18.9) <а!8огМип> «и'а () тах () «ип е!етеп! () тах е!ете«! () !ех!сойгарИса! сотраге () Меньшее из двух значений Большее из двух значений Наименыпее значение в последовательности Наибольшее значение в последовательности Лексикографически первая из двух последовательностей Библиотека обеспечивает несколько основанных на сравнении алгоритмов для выбо- ра элементов: Глава 18.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
