Бьерн Страуструп. Язык программирования С++. Специальное издание (2011) (1004033), страница 133
Текст из файла (страница 133)
Ьее!п (), <овпз. еп«(), "Ааглиз", " А«Ьиз" ); Здесь используется расширенный набор символов (5С.З.З). Глава 18. Алгоритмы и классы функциональных объектов 640 18.6.5. Алгоритмы удаления элементов Эти алгоритмы удаляют элементы последовательности, отталкиваясь от их значений или основываясь на предикате: гетр(иге<с!азз Рог, с(азз Т> Рог гете«е (Рог)1«зг, Ро«!аз(, сопз! Та га1) ! гетр(а(с<с(ат Рог, с!азз Ргед> Рог гете«е (Т(рогу)гзг, Рог !аз!, Ргедр); гетр(иге<с!азз 1п, с!азз Ош, с1азз Т> Ош гетоге сору (1пу)гзг, 1п 1азг, Ои! гез, сопзг Т««а1) гетр(аге<с1азз 1~, с1азз Оиг, с(азз Ргегт> Ои! гете«е сору зу(1и Т!«зт, 1п 1азз, Ои! гез, Реестр) Предположив, что клуб!я (структура С!иЬ из 518,4.2.1) имеют адрес, мы могли бы создать список клубов из Копенгагена: с1ат!осагег1 т: риЫ)с ииагу ~иис!!оп<С(иЬ, Ьоо1> ( зт«1иа !опт; риЫ!с: !оса!еа' )п (сопз! зт«!ила т): топи (т) ( ) Ьоо( орега!ог ( ) (сопз! С!иЬа с) сопзг ( ге!ига с.
1оеп == !опт; ) )' го(а )(Из!< С1иЬ> а 1с) ( гетоге сору 1У(!с. Ьелм (), 1с. епй(), озггеат 1!его!ог<С1иЬ> (соил, поО (!оса!ей !и ( "Кавепла«п") ) ); Таким образом, алгоритм «етою сору зу() — это фактически сору гу() 518.6.1) с инвертированным условием. То есть элемент помещается алгоритмом гетоге сору (!'() в выходной поток, если он не удовлетворяет предикату. «Простой» алгоритм гетозе () записывает все несовпадающие элементы в начало последовательности и возвращает итератор на конец уплотненной подпоследовательности (см. также 518.6.3). 18.6.6. Алгоритмы Н1() и депега1е() АлгоритмыИИ() и 8еиега!е() предназначены для систематического присвоения последовательностям значений: гетр!иге<с(азз Рог, с1ат Т> юЫЯ! (Ро«И«зг, Рог 1аз(, сопз! Та «а1); <етр!аге<с1ат Оиз, сгазз Яке, с!азз Т> гоИу)11 п (Ош гез, Яке и, соизз Та га1); (етр(а!е<с(ат Рог, с1ат Сеп> юЫдепегаге(гог)1«зг, Рог!аз!, Сеид) ! гетр!иге<с!азз Оио с1ат Яке, с(азз Сеп> гоЫ8еиегазе и (Ои! гез, 8!зе п, Сеи а); Алгоритм 11!!() последовательно присваивает указанное значение; алгоритм Кеиега!е ( ) присваивает значения, возвращаемые последовательными вызовами его аргумента-функции.
Версии с суффиксом и осуществляют присваивания лишь первым и элементам последовательности. 641 18.6 Модифицирующие алгоритмы Например, используем генераторы случайных чисел Йапс((пс и ((гипс( из 522.7: спс г( (9001; спс г2 (9001; гессог гЗ; гоЫ7() ' ( (11!(г(, Ьг((900],99) ) Йепегасе (г2, ьг2 [9001, Йапсбпс (] ) с гу присваиваем случайные значения 1422.7) гУ вывод 200 случайных чисел в интервале (0..99/с еепегасе п(озсгеат Йегасог<спс>(соис),200,((ганс((!00) ) с /lсм. 022.7 (111 п (бас(с !пзегсег (гЗ), 20, 99); гу добавляем к гЗ 20 элементов со значением 99 ) Функции ус((() и Вепегасе() осуществляют присваивание, а не инициализацию. Если вам требуется манипулировать неинициализированными областями памяти, чтобы, например, создать в них объекты заданного типа и состояния, используйте алгоритмы вроде ип(п(аа((гас( л(1() из <тетогу> ($19.4.4).
18.6.7. Алгоритмы ге)сегве() и го1а1е() Иногда нужно изменить порядок элементов последовательности: сетрйсе<с(азз Вс> юЫ гегете (В!Зсгвс, Вс'!ат) ) гетр(те<с(аяз Вс', сйзз Оис> Оса гегегве сору (В(()гзс, Вс'!асс, Оис гез) сетрйсе<сйвз Рог> юЫ гоаае (Рог Вгт, Рог т!сй((е, Рог йсе) с сетрйсе<с(аса Рог, с!ачз Оис> Оис паосе сору(рогбгзс, Рог тйс((е, Рог (азс, Оса гез) сетр1асе<с(аззЙап> юЫгапс(от з(сиВ(е(Йапусгзс, Йап 1азс) с гетр(асс<с(азз Йап, с(ачз Сеп> го(0 гат(от з(си(((е (Йап Вгзс, Йап Ьсзс, Сень 0) с Алгоритм гегекве() изменяет порядок элементов последовательности на обратный, так что первый элемент становится последним и т.д. Алгоритм гегегзе сору ( ) производит копию входной последовательности, но с обратным порядком следования элементов. Алгоритм го!псе() рассматривает последовательность (лглс, 1азс) как круговую и циклически сдвигает ее элементы до тех пор, пока средний элемент последовательности (указывается параметром т(й((е) не окажется на месте, на котором ранее располагался первый элемент.
То есть элемент из некоторой позиции Зсгзсч-1 передвигается в позицию зсгзгг (сц ((асс-тсс(с((е) ) а ((алс-Вгзс) . Целочисленное деление 1 — вот что делает сдвиг циклическим, а не просто сдвигом влево. Например: гоЫ (() ( зсг(пй г(1 = ( "угой", "апс(", "Раас(с" 1г гегегзе (г, гвЗ) с 77 Реас(с опг( Ргое госасе(г, г-г(, в+3) с 77 апд Ргое Реас(с ) Алгоритм го!осе сору() копирует элементы в выходную последовательность с циклическим сдвигом. Глава ) 8. Алгоритмы и классы функциональных объектов 642 По умолчанию гапг!от зйиЯе () перетасовывает последовательность при помощи генератора случайных равномерно распределенных чисел.
То есть алгоритм выполняет перестановки элементов последовательности таким образом, что любая перестановка имеет одинаковый шанс быть выбранной. Если вам нужно другое распределение или более качественный генератор случайных чисел, вы можете предоставить собственные. При вызове гат!от зйфуе (Ь, е, г) генератор вызывается с аргументом, равным количеству элементов последовательности, то есть вызов генератора г(Ь-е) возвращает значение в диапазоне [О, е-Ь) .
Если Му гат! — это такой генератор, то мы можем перетасовать колоду карт следующим образом: гоЫТ(Иедие<Сагй>ь «с, Му гапка г) ( гат!от зйи)2)е (ас. Ьеагп (), ас. ет! ( ), г) У! ... Перемещение элементов алгоритмами гогаге() и др. реально выполняется с помощью функции зиар () (518.6.8). 18.6.8. Обмен элементов последовательностей местами Чтобы сделать с элементами контейнера что-нибудь более-менее интересное, нам нужно уметь обменивать элементы местами (перемещать элементы). Наиболее просто и эффективно такой обмен выполняется алгоритмами семейства "ззгар'ч гетр(а!с<с(ат Т> зоЫ заир (Тз а, Ть Ь) Т ипр = а; а =Ь; Ь = Ьп ) гетр1а1е<с(ат Гог, с1ат Гог2> гоЫ иег ивар (Гоги, Гог2 у); гетр(иге<с!от Гог, с(азз Гог2> Гог2 зеар гап8ез(Гогуйзз, Гог !ил, Гог2/йз(2) ( иИ1е(утзз!=!аз!) йег зиар(у)гзн+, у)гз(2++) ! ге!ига )згз(2; ) При обмене элементов местами приходится создавать временный объект.
Сушествуют хитрые приемы, позволяющие избавиться от этого. Но ради простоты и очевидности их лучше не применять. Алгоритм з)гар () имеет специализации для важных типов, для которых зто имеет большое значение (816.3УА 813.5.2). Алгоритм Ыез з)гар() обменивает местами элементы, указуемые аргументами-итераторами. Алгоритм ззгар гап8ез() обменивает элементы двух входных последовательностей. 18.7.
Сортировка последовательностей 643 18.7. Сортировка последовательностей Когда данные собраны, их часто следует отсортировать. Ведь после того, как последовательность отсортирована, возможности удобной работы с ней резко возрастают. Для сортировки последовательностей нужны способы сравнения элементов. Это делается с помощью бинарных предикатов (518.4.2). По умолчанию для сравнения элементов используется операция <.
18.7.1. Сортировка Алгоритмы сортировки требуют итераторов произвольного доступа (819.2.1). Таким образом, они лучше всего работают для контейнера гессог (81б.З) и подобных ему: сетр1асе<с1асс Кап> гоЫ согс (Кап ~исс, Кап !асй с сетрйсе<с1асс Кап, с!от Стр> гоЫ югс(Капу«гас, Йап 1ат, Стр стр) гетр!осе<с!аи Йап> юЫ ссаЫе согс(Кап!)гсс, Кап сасл с сеиср!асе<с1аас Йап, сйю Стр> юЫссаЫе согс(Капу)гсс, Кап !асс, Стр стр); Стандартный контейнер 1йс(517.2.2)не предоставляет итераторов произвольного доступа, так что списки следует сортировать их специфическими операциями (817.2.2.1). Базовый алгоритм юг!() весьма эффективен — в среднем как А(»!од()1() — но в худшем случае как 0(Ж»йс) .
По счастью, худшие случаи довольно редки. Если важно гарантировать приличное поведение алгоритма во всех случаях (включая худшие), то следует применить алгоритм есаЫе согс() с эффективностью порядка М !оК(Ж) *1оК(Ф), улучшающейся до Ж«!оК(стс) в случае наличия достаточного объема свободной памяти. Относительный порядок следования одинаковых элементов алгоритмом есаЫе юге() сохраняется неизменным (алгоритмом югс() — нет). Иногда нужны лишь несколько первых элементов отсортированной последовательности. В таких случаях имеет смысл сортировать последовательность до момента получения нескольких первых элементов, расположенных упорядоченно (так называемая частичная сортировка — рагс(а! согс): сесирсасе<с!асс Каи> юЫ рагиа1 согс(Кап С)гсс, Кап тле, Кап 1ам) сетрйсе<ссасс Йап, с!асс Стр> гоЫ рагиас согс (Кап 7)гсс, Кап т!с!а!е, Кап сасС, Стр стр); гетр!осе<с!асс 1п, с!асс Кап> Каи рагиас югс сору(1п Ссгсс, 1п 1~тс, Кап!из!2, Кап !ос!2) гетр!осе<айаг 1и, сйт Каи, с!асс Стр> Кап рагвас согс сору(1и!сгсС, 1п !асс, Кап 31гсс2, Кап !ос!2, Стр стр) с «Простые» алгоритмы рагс(а1 югс() расставляют по порядку элементы в диапазоне от !!гас до тле.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
