Бьерн Страуструп. Язык программирования С++. Специальное издание (2011) (1004033), страница 134
Текст из файла (страница 134)
Алгоритмы рагва! согс сору () выдают %элементов, где Ю— это наименьшее из длин двух последовательностей (входной и выходной). Нужно указать и начало, и конец выходной последовательности, поскольку это определяет число элементов, подлежаших сортировке. Например: Глава 18 Алгоритмы и классы функциональных объектов 644 с1азз Сотраге сор)ез зоЫ ( риЬИс: Ьоо! прего!ог() (сола! Вооаа Ь1, солзт Ввода Ь2) сола! (ге<игл Ь1.сор!ез зо!И() <Ь2.<ар!ее зо!И() т ) //сортировка в убывающем порядке )! юЫ у'(соне! вес!ее< Вова> ь за(ез) ( гес!ог<ВооЬ> Ьезгзедегз (10) ! //наводит!О яутаик книг рагиа1 зог! сору(вогез.Ьел!л(),за1ез.еид(), ЬезтзеИегз.
Ьеа!п (), ЬезгзеИегз. енИ () Сотраге сортез зоЫ() ); сору (Ьезтедегз. Ьее!л (), Ьез!зеИегз. еий(), оз!геат Вега!ог<ВооЬ> (сои(, "Чи" ) ) !стране<с!иве Ваи> юЫ ий е1етеит (Лаи ргзз, Вап ий, Ваи 1аи) т !етрьле<с(азз Кан, сйиз Стр> юЫ пй егетеп!(Вал Иге!, Вап пй, Лаи (ам, Стр стр) т Этот алгоритм особенно полезен для экономистов, социологов, учителей и т.д., поскольку им часто нужны медианы распределений, процентные отношения и другая статистика. 18.7.2.
Бинарный поиск Последовательный поиск, такой, например, как 27лИ() (818.5.2), ужасно неэффективен для длинных последовательностей, но это все, что мы можем сделать без сортировки и хэширования (В17.6). Но после того, как последовательность отсортирована, можно выполнять быстрый бинарный поиск: тетргате<с!азз рог, с!ат Т> Ьоо( Ынагу зеагса (рог/ткет, Ео«!аз!, соим Та га!) тетр1ате<с1азз Рог, с1азз Т, с(азз Стр> Ьоо1 Ьглагу зеагсЬ (Рог !Ггзг, Рог 1азг, соизг Та га1ие, Стр сгир) Например: гоЫу(Из!<!лт> а с) ( ту(Ылагу зеагсЬ(с.Ьевйп (),с.ет1(), 7) ) ( // ... И имеется ли 7 в с? Поскольку выходная последовательность в алгоритме раева! зогг сору () должна индицироваться итератором произвольного доступа, мы не можем произвести сортировку непосредственно в выходной поток сол!.
Наконец, имеются алгоритмы, призванные выполнять сортировку до тех пор, пока Ат-й элемент не займет свое окончательное место (за этим элементом уже не будут располагаться элементы, меньше его величиной): 645 ) 8.7. Сортировка последовательностей Алгоритм Ь1лагу яеагсй() возвращает значение типа Ьоо1, показывающее, найдено ли искомое значение в последовательности. Как и в случае с 11л!1(), мы часто хотим знать, где именно в последовательности расположено искомое значение.
Однако в последовательности может оказаться несколько таких значений, и нам могут потребоваться либо первый из них, либо вообще все такие элементы. Как следствие, имеются алгоритмы для выявления диапазона одинаковых элементов — едиа! галде (), и для уточнения их нижних и верхних границ — !олег Ьоит1() и иррег Ьоила(): гетрйие<сйяя Гог, сйия Т> Гог !олег Ьоипо (Гогфгяя, Гог !ля!, соня! Ть га1) гетрйие<сйяя Гог, с!ат Т, сймя Стр> Гогйыег Ьоипй(рогфгяя, рог йяяг, сопя! Ть ю1, Стр етр); гетр1те<сйяяя Гог, сйия Т> Гог иррег Ьоиио (Гогутгяя, Гог йяяя, сопя! Ть га1) гетрЫе<сйгяя Гог, сйия Т, сйая Стр> Гог иррег Ьоила(Гог Ягяг, Гог йяяя, сопя( Та ю1, Стр стр) ) гетрйие<сйия рог,сйия Х> рал<Гог, Гог> едиа1 галде(Гогдгяг, рог йяг, соля! Тя ю!) ! гетрйие<ейяяя рог, сйия Т, сйяя Стр> рай<рог, Гог> едиа! галде [Гогфгяг, Гог йит, сопя! Та га1, Стр етр); Эти алгоритмы соответствуют операциям контейнеров ти1Втар (817.4.2).
Можно представлять себе алгоритм !олег Ьоти1() как быстрый вариант алгоритмов 21иа() иЯлд [7() для сортированных последовательностей. Например: юЫд [гесйг<ии>а с) ( г)рейе2 гесгог<!иг>:: йепиог И; ) Хр =Яид (с. Ьедш (), с. еий ( ), 7); д вероятно медленно - ОЯг е не нужно сортировать Ид = йниг Ьоипгг(с.йод(п [),с.епй(), 7); дбыстро - 0[(од(Л7)( с нужно сортировать д... ) Если вызов !олег Ьоииа'(7!гяг, йяг, й) не находит й, то он возвращает итератор на первый элемент с ключом, большим 1е, или 1аят, если такого элемента нет. Такой же способ индикации неудачи используется в иррег ЬотЫ() и едиа1 галде () .
А это значит, что мы можем применять эти алгоритмы для того, чтобы определить место вставки элемента, не нарушающее упорядоченного характера последовательности. 18.7.3. Слияние (алгоритмы семейства гпег9е) При наличии двух отсортированных последовательностей мы можем объединить (слить) их в одну отсортированную последовательность при помощи алгоритма тегде() . А при помощи ялВле тегде() можно соединить две части одной последовательности: гетрй <сй 1и, сйия1и2, стаяв Оиг Ои! тегде(1пфгяг, 1п йяяг, 1п2йгя(2, 1п? йяя2, Ои! гея); тетрйге<а 1л, сйия 1и2, с)аяя Оия, сйяяя Стр> Ои! тегде (1ифгяя, 1и!аят, Ьл2 фея!2, 1п2 йиг2, Ои! гея, Стр стр); тетрйяте<сйяя В!> юЫ шрйсе тегде [В!учтя!, В! тнЫй, В! йяо; гетр!те<с1ат В~', ейия Стр> юЫ !ирйке тегде(В!Т[гяг, В! тйййее, В1 йяг, Стр стр); Глава 18.
Алгоритмы и классы функциональных объектов 6Яб При равенстве элементы первой последовательности будут предшествовать элементам второй последовательности. Вызов тр!аее тегде О соединяет сортированные последовательности (1;т) и [т, е), помещая результат (назад) в (Г',е). Алгоритм юпр1аее тегде() полезен в первую очередь тогда, когда у вас есть последовательность, которую можно отсортировать по нескольким критериям. Например, пусть имеется вектор (типа юееюог) с экземплярами рыб, отсортированный по видам рыб (еой, Ьайййосй, Ьегг1пя— треска, морской окунь, сельдь). Если экземпляры рыб одного вида отсортированы по весу, то вы можете отсортировать весь вектор по весу, применив юпр!аее тегде() для объединения информации по разным видам рыб (818.13120)). Заметьте, что эти алгоритмы слияния отличаются от методов тегяе() списка 1!юг (б17.2.2.1) тем, что не удаляют элементы из входных последовательностей.
Вместо этого элементы копируются. 18.7.4. Разбиение элементов на две группы (алгоритмы семейства рагШ)оп) Разбиение последовательности (рап1((оп а зес(цепсе) на две группы элементов выполняется так, что все элементы, удовлетворяющие предикату, располагаются перед элементами, предикату не удовлетворяющими. Стандартная библиотека предоставляет алгоритм ююаЫе Раею!поп (), выполняющий такое разбиение по предикату с сохранением относительного порядка следования элементов в группах (удовлетворяющих предикату и не удовлетворяющих ему).
Алгоритм раюппоп() делает то же самое, но без сохранения относительного порядка, и он выполняется чуть быстрее в условиях дефицита памяти: юеюпрюаюе<еюаюю Вю', е1аюю Ргей> В) рагВВоп (В)1югюю, Вю !аи, Ргейр) ю гетр!аюе<еюаюю Вю', с(аюю Ргей> Вю юаЫе рагпю(оп (В( 1)гюю, Вю' 1аюю, Ргей р) ю Можно представлять себе алгоритмы разбиения как разновидность сортировки с очень простым критерием. Например: го(й/(1!ю«С(иЬ> а 1<) ( ли<С!иЬ>:: 1юегаюог р = рагю!ю!оп (1е. Ьед1п ( ), 1е. епй ( ), !оса!ей !и (" КеЬепвагп '* ) ); ~У... Здесь список клубов сортируется так, что клубы из Копенгагена идут первыми.
Возвращаемое значение (здесь это р) указывает либо на первый элемент, не удовлетворяющий предикату, либо на конец последовательности. 18.7.5. Операции над множествами Последовательность можно рассматривать как множество. Поэтому имеет смысл обеспечить для последовательностей операции, характерные для множеств, например, объединение и пересечение.
Однако эти операции страшно неэффективны, если только последовательности не являются отсортированными. Поэтому стандартная библиотека предоставляет операции над множествами только для отсортированных последовательностей. В частности, операции над множествами пре- ) 8.7. Сортировка последовательностей 647 красно работают с контейнерами яе((517.4.3) и ти1гйе( 517.4.4), которые сортиру- ются автоматически. Если же этн операции (алгоритмы) применить к несортированным последовательностям, то результирующие последовательности не будут соответствовать правилам теории множеств. Эти алгоритмы не изменяют свои входные последовательности, а выходные последовательности всегда отсортированы.
Алгоритм !лс1и<1ея[) проверяет, является ли каждый элемент второй последовательности, то есть последовательности [!1гя(2, йз(2 [, также и элементом первой последовательности [41гя(,!ая( [: <етр1а<е<ейяз 1п, с<аяя 1п2> Ьоо! [ле!идея(1пЯгз(, 1п 1аз<, 1п2Ятз<2, 1п2 !аз<2) (етр<а(е<е!азя 1п, с1аяя 1л2, е1ат Стр> Ьоо! <лс!идея (1п 1<ге<, 1п <аз(, 1п23ия(2, 1п2 <аз<2, Стр стр); Алгоритмы яе< ил<оп [) ' и яе( й(егяеспол () порождают свои очевидные результаты в виде отсортированных последовательностей: (етр1а<е<е!аяя 1п, е<ат 1л2, с!ат Ои(> Ош яе< илюп (1п 1<гз(, 1п <аз<, 1п2Гмз<2, 1л2 !аз<2, Ош гея); <етр<а(е<е(азя 1п, е(ат 1п2, е1аяя Ои<, с!аяя Стр> Ои( яе< итон [1п (<гз<, 1п !аз(, 1л2 <)гз(2, 1п2 <аз(2, Ои< гея, Стр етр); <етр<а<е<с<ат 1п, с!аяя 1п2, е!ат Ои<> Ои( яе< <л(егяес<<оп (1п Я(я<, 1п 1ая<, 1п2 <)гя(2, 1п2 1ая<2, Ои< гея); (етр!а<е<е!аяя 1п, е!ат 1п2, с(азя Ои(, с!аяя Стр> Ои< зе< т<егзесдоп (1п 7<(я(, 1п !ай, 1п2 <)ге<2, 1п2 !аз<2, Ои< гея, Стр етр) Алгоритм яе( й3егелсе () порождает последовательность, чьи элементы являются членами первой, но не второй входной последовательности.
Алгоритм яе( яуттеМс й3егелсе() порождает последовательность элементов, входящих в одну и только одну из входных последовательностей; (етр!а(е<ейяз 1п, сьяи<1п2, е!азз Ои(> Ои(зе( 4фегепее(1пфгк(, 1п !аз(, 1п2фгз<2, 1п2 !аз<2, Ои(гея); <етр<о(е<ейяя 1л, с!азз 1п2, еБ<яя Ои<, ейяя Стр> Ои(зе< 4<фегелсе(1л7!гз(, 1л 1ая<, 1п2(Ъя(2, 1л2 !аз<2, Ои(гез, Стр етр); <етр<а(е<е!азя1п, с!а(я 1п2, е!аяя Ои<> Ош яе< яул<теоте 4<фегепее (1п Я(я(, 1л !ая<, 1л21ггя(2, 1п2 йя(2, Ои( гея); (ел<р!те<с!азз 1п, с!азя 1п2, с!аяя Ои(, с!азз Стр> Ои< зе< зуттепе 4<Яегепсе [1л чтя<, 1п йя(, 1л2 7)гз(2, 1п2 йз<2, Ои< гея, Стр с<ар) Например: сьаг г<[) = "аЬс4"; еьаг г2 [ ) = "еде(> < го<41 ( сваг гЗ ( ) ) ( яе< 4фегепее (и1, г1э4, г2, (2э4, гЗ) ( У ыЗ = "аЬ" яе( зутте<пе 4Цегепее(г1, г1м4, г2, г2э4, гЗ); ~У гЗ = "абе/" ) 1 [)пюп — объединение, [пте(яес[юп — пересечение.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
