Б. Страуструп - Язык программирования С++. Специальное издание, 3-изд. Бином. 2004 (1160791), страница 134
Текст из файла (страница 134)
Сортированные последовательности Эти алгоритмы согласуются с операциями из ти!1!тар (Ч 17.4,2). Мы можем представлять себе !ошег Ьоипс! () как быстрыефп!1 () ифпг! у" () для сортированных последовательностей. Например: ио!<!у(иес1ог !п1>й с) ( 1урес1е! иес1 ос:!1ега1ог '>2; О вероятно, работает ледленнш 0(!У); вектор с сортаровать не нужно Ир= Вас!(сбеу!п(),сенс!(),2); 1! вероятно, работает бнстроь О (!оу!Л9); вектор с должен быть отсортировал >Уу !ошег боппс!(с.бед!и (),с.епс!(), 2); Если !ошег Ьошп1 (!ьгв1, !аь1, Й) не находит Й, он возвращает итератор на первый элеьчент с ключом больше Ь, или 1аь1, если такого элемента не найдено.
Такой способ сообщения о неудаче также используется в иррег боинг!() и еуиа! галие (). А значит, мы можем пользоваться этими алгоритмами для определения, на какое место вставить в сортнрованную последовательность новый элемент, чтобы она осталась сортированной. 18.7.3. Слияние (алгоритмы гпегде) Имея две отсортированные последовательности, мы можем объединить (слить) их в одну новую отсортированную последовательность при помощи алгоритма тесле () нли объединить две части одной последовательности при помощи !пр1асе тегде (): 1етр!а1е<с!акк гп, с1акь 1п2, с!акк Оаг> Оа! тегуе (!и)) гь1 !п !ак1,1п2!) гь12, гп2 !ак12, Оас геь), 1етр1а!е<с!аь к !п, с1акь !п2, с!акк Ои1, с!акк Стр> Оа1 тегуе (1пЯгк!, 1п 1ак1, !п2)сгк12, 1п2 1ак12, Оас гек, Стр стр); 1етр!а1е<с1акк В!> иоЫ Шр1асе тегуе (и!3гк1, В! ти!с!!е, В! !ак1) 1етр!аге<с!акк ВС с1акк Стр> ио!д !пр!асе теса (В!Век!, В!я!Ы!е, В! !ак1, Стр стр); Отметим, что эти алгоритмы слияния отличаются от слияния списков !!ь1 Я 17.2.2.1) тем, что не удаляют элементы из своей входной последовательности.
Вместо этого элементы копируются, При равенстве элементы из первого диапазона будут всегда предшествовать элементам второго. Алгоритги спр1асе тегуе () используется главным образом тогда, когда у вас есть последовательность, катару!о можно отсортировать по нескольким критериям. Например, у вас может быть вектор иес1ог с названиями рыб, отсортированный по видам. Если элементы каждого нида отсортированы по весу, вы можете отсортировать весь вектор при помощи тр!асе тегде () и объединить информацию для разных видов 8 18.13[20)). 18.7.4.
Разделители (алгоритмы раг(11)оп) Разделать последовательность, значит расположить все элементы, удовлетворяющие предикату, перед всеми элементами, которые ему не удовлетворяют. Стандартная библиотека предоставляет алгоритм к1аб(е раг1!поп (), который сохраняет относительный 606 Глава 18. Алгоритмы и объекты-функции порядок элементов, удовлетворяющих и не удовлетворяющих данному предикату. Кроме тщ о, библиотека предлагает ктпо риз м ра г111!оп (), который не сохраняет относительный порядок, но работает чуть быстрее, когда память ограничена: 1етр1а1к<с1азз ВЬ с!азь Рге<!> В! рагг!1!оп (В!Г!гь1, В! 1аз1, Ргег! р); 1етр1аге<с1азз В1, с1азк Рге<1.
В! к1аЫе рагг!1!оп (и! Вгз1, В! 1аз1, Ргег! р); Вы можете представлять себе разделитель как некую разновидность сортировки с очень простым критерием. Например: оо!г! Г (!!к!<С!иЬ>Ь 1с) (' Вз1<С1иЬ>свегагог р = рагл1тп (!сЬеясп (), 1с епВ (), !оса1ег! !и (КиЬепйаип")) 0- ) В результате список Вк! будет отсортирован так, что клубы (объекты С1иЬ) с адресом в Копенгагене расположатся в начале. Возвращенное значение (здесь р) укажет либо на первьш элемент, не удовлетворяющий предикату (здесь !оса1ег( гп ('Кибел(ьаоп")), либо на конец списка. 18.7.5.
Операции с множествами для последовательностей Последовательности можно рассматривать как множества. Поэтому имеет смысл обеспечить для последовательностей операции, аналогичные действиям с множествами, например пересечение. Однако эти операции очень неэффективны, если последовательности не отсортированы, поэтому стандартная библиотека обеспечивает операции с множествами только для сортированных последовательностей. В частности, операции с множествами хорошо работают с ке! (З 17А.З) и ти!1!ке1 Я 17АА), которые в любом случае отсортированы.
Если эти теоретико-множественные алгоритмы применить к несортировапным последовательностям, результирующая последовательность не булет подчиняться обычным правилам теории множеств. Эти алгоритмы нс изменяют свою входную последовательность, а их выходные последовательности упорядочены. Алгоритм !пс(иг!ез() проверяет, является ли каждый член второй последовательности ага!2: 1аз12[также и членом первой: !етр!а1е<с!азз 1п, с!азь 1л2> Ьоо! !пс!ийкь (1п))гк1, 1п !аз1, 1п2 7!гь12, 1п2 !аз12); 1етр!а1е<с1азк 1и, с!азз 1п2, с!оьь Стр> Ьоо! тс!и!!ек (1п ~~гь1, 1п !аз1, 1п2 1) гь12, 1п2 !аз!2, Стр стр); Назначение алгоритмов ке1 ип!оп () (обьелипение) и ке1 т1егкесйоп () (пересечение) очевилпо: 1етр1а1е<с1азь 1п, с1азь 1л2, с1азз Ои1> Ои1 зг1 ип!оп (1пЯгк! 1л !аь1, 1п22!гь!2, 1п2 1аз12, Ои1 гез); 1етр!а1е<с!азз 1и, с!азз 1п2, с!азз Ои1, с1азз Стр> Ои1 кег итал (1п багз! 1п 1аз1, 1п2Ягь12,1п2 !аз!2, Ои1 гез, Стр стр); 1етр1а1е<с!азз 1п, с1изз 1п2, с!аьк Ои1> Оиг ке! т1егкес!! оп (1п)) гь1, 1п 1азг, 1п2Ягз12, 1л2 !аз!2, Оиггек); б07 1б.б.
Кучи 1етпрlаге<с1аяз !и, с1азя lп2, с!аяя Ои1, с!азя Стр> Ои1зе! !псегзесйоп (!лаге!!л 1аз1, lп2/)гз12,!л2 lаз12, Ои1 гез, Стр стр); Алгоритм зе1 с(!Оегепсе() выдает последовательность элементов, входящих в первую, но не входящих во вторую входную последовательность. Алгоритм ке1 яутте1г!с Й1/егепсе () (симметрическая разность) выдает последовательность элементов, входящих в одну и только одну из входных последовательностей; 1етр!а1е<с!азз lп, с!азя !л2, с!аяя Оис Оиг зег сй//егепсе (lп/ьгз!, !л !ая1, !п2/ьгя12, 4п2 !аз12, Оиг гез); гетр!а1е<с!аяя !п, с!аяя lп2, с!азя Ои1, с1аяя Стр> Ои1 яег ь(Яегелсе (!и йгз1, !л !аз 1, !п2/!гз12, !п2 !аз!2, Оиг гез, Стр стр); 1етр!а1е<сlаяя !и, с!азя lп2, сlазз Оис> Ои1зег зуттептс ЙЯегепсе (!и/!гз1, 4п lаз1, !п2/1гз12, !л2!аз12, Оиг гез); 1етр!а1е<с1аяз !и, с!аяя lп2, с!азя Оиг, сlаяз Стр> Оиг яе1 яутте1ггс с!Яегепсе (!л/!гя1, !л lая1, !п2/1гз12, !л2 lаз12, Ои1гея, Стр стр), Например: сйагиl[) = абсд"; сйаг и2() = "еде/'; ио!с1! (сЬаг иЗ [)) ( яе1 41//егепсе (И, и!+4, и2, и2+4, иЗ); зе1 зутте1пс с!фегепсе (иl, и!+4, и2, и2+4, иЗ); ) //иЗ='ад' //иЗ ='аое/" 18.8.
Кучи 1етр!а1е<сlаяз йап> иоЫризЬ Ьеар (йапЯз1, йал lаз1); 1етр!псе<с!аяяйал, с1аяя Стр> иоЫ рияд Ьеар (йап/!гз1, йап lазг, Стр стр); 1етрlа1е<сlазз йап> иои1 рор Ьеар (йап/о зг йап !ая1) 1етр1аге<сlаяя йап, сlаяя Стр> иоЫ рор Ьеар (йап Ягз1, йап lая1, Стр стр); // превращавп1 последовательность в кучу; 1етр1а1е<с1азз йап> ио!д таИе Ьеар (йап/)гзг, йал lая1); 1етр!аге<с!азз йап, с!аяз Стр> иоЫ таде Ьеар (йал/1гзг йап 1аз1, Стр стр); // превращают кучу в последовательность: 1етр1а1е<сlаяз йап> иоЫ зог1 Ьеар (йап11 гзг, йап !аз1); 1етр!а1е<сlаяз йал, с!аяя Стр> иоЫ загс Ьеар (йапЯгя1, йап !ая1, Стр стр); Стиль алгоритмов, работающих с кучами, довольно странен. Естественнее было бы обеспечить класс-адаптер с четырьмя операцнямн.
Получилось бы нечто вроде Слово «куча» (оеар) в резном контексте означает разные вещи. Применительно к алгоритмам, «куча» часто обозначает способ организации последовательности, когда первым является элемент с наибольшим значением. Добавление элемента (при помощи рияЬ Ьеар ()) и удаление (при помощи рор Ьеар ()) производится довольно быстро; в худшем случае быстродействие равно О (1од (Л)), где А! — число элементов в последовательностин. Сортировка (при помощи зог! Ьеар ()) в худшем случае имеет быстролействие О (М"!од (Л)). Куча реализуется следующим набором функций: Глава 18.
Алгоритмы и объекты-функции 608 рг!ог!1у диеие (э 17.3.3) (очередп с приоритетами) Фактически, рг!ог!!у уиеие почти наверняка реализуется с использованием куч. Значение элемента, помещаемого в кучу алгоритмом рияЬ Ьеар (1)гя1, 1ав1), равно * (1ая1-1). Принимается допущение, что [йгк1 1ая1 — 1[ уже является кучей, так что ризЬ Ьеар (), включая следующий элемент, расширяет последовательность до [йгз1, !ав1[. Таким образом, серией операций рияЬ Ьеар (] можно из существующей последовательности построить кучу. И наоборот, рор Ьеар () удаляет первый элемент из кучи, переставляя его с последним (* (1аз1-1)) и делая последовательность [7)гя1, !ая1 -1[ кучей.
18.9. Алгоритмы т)л и тах Описанные здесь алгоритмы выбирают значение, основываясь на сравнении. Очевидно, полезно уметь находить максимальное и минимальное из двух значений: гетр1аге<с1азз Т> сопз1 Т& тах (сопз1 Тй а, соля1 Тй 6) ( ге!игл (а<Ь)? 6: а; 1етр1а1е<с!аяз Т, с!азв Стр> сопк1 Тй тах (сопя1 Тй а, сопя! Т& 6, Стр стр) ( ге1игп (стр (а, Ь))? Ь: а; ) 1етр!а1е<с!азя Т соля!7& тш (соля1Тйа, соля! Тй Ь); 1етр!а1е<с!азз Т, с!авв Стр> сопя1 Тй т!л (сопз1 Тй а, соля! Тй Ь, Стр стр); Операции тах () и лип () можно обобщить, чтобы очевидным образом применять их к последовательностям: 1етр1а1е<с!азя Гог рог тех е!етеп1(ГогЯгяг, рог!ая1); 1етр!а1е<с!азз Гог, с1азз Стр> Гог тах е!стел! (ГогЯгя1, Гог !ая1, Стр стр); 1етр1а1е<с1азз Гог> Гог лил е1етеп1 (Гог1!гя1 Гог !ая1); 1етр1а1е<с!азз Гог, с!азя Стр> Гог т1п е1етеп1 (Гог)!гз1, Гог 1аз1, Стр стр); И наконец, лексикографическое упорядочивание строк легко обобщить для последо- вательности значений, которые можно сравнивать: 1етр1а1е<с!азя 1п, с!аяя 1п2 ьоо! !ехгсоугарыса! сотраге (ТпЯгз1, 1п !ая1, 1л21!гя12, 1п2 !аз12); 1етр!а1е<с!азз 1л, с!аяя 1п2, с!аяз Стр> Ьоо! !ех!соугарЫса! сотраге (1пЯгяг, 1л !ая1, 1п2глз12, 1п2 !аз!2, Стр стр) ( тЬ!!е (ргв1! = !аз1 й&Ягз12! = !аз!2) ( (1 (стр ( 1(гз1, *(йз12)) ге1игп 1гие; ((; (стр (*1(гз12-н-, '1)гя1++)) ге!агава!яе; ге1лгпЯгз1 == !аз1&& Гвгя12 1= !аз!2; Это очень напоминает соответствующую функцию для обычных строк Я 13 А.1), однако 1ех!соу арЬвса1 сотраге () сравнивает последовательности вообще, а не только 609 16.10.
Перестановки (влгоритмы реппц1вйопз) строки, Кроме того этот алгоритм возвращает Ьоо!, а не более распространенный тй Результатом является Егие тогда (и только тогда), когда первая последовательность при сравнении со второй оператором < дает »гие. В частности, результат будет Еа(ве, если последовательности равны. Например: сбаг иЕЦ = 'да"; сбак о2Ц = 'некп"; в»г»п» в» = "да"; в» Епдв2="Ввт; иоиЩ ( Ьоо! 6! !ех»соигарб»са! сотраге (и», с!+в»г!ел (о!), и2, и2.кв»г»еп (и2)), Ьоо! Ь2 = Еех»соагарб!са! со тра ге (е».берл (), в».епй (), в2 белка (), в2 епй ()); боо1 62 = Еех»содгарб!са» сотраге (и1, о!+в»г!ел (и»), вЕ.Ьеа»п (), в1 впй ()); Ьоо» Ь4 = Еех»содгарб»са! сотраге (в!Ьехк»п (), в!епй() о1, и!<в»г!еп (и1), »кос ве ()), Последовательности не должны быль одного и того же типа: все, что нужно — зто сравнивать их элементы, а критерий сравнения можно сообщить.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
