Б. Страуструп - Язык программирования С++. Специальное издание, 3-изд. Бином. 2004 (1160791), страница 133
Текст из файла (страница 133)
Если вам нужно манипулировать чистой памятью, скажем, чтобы превратить область памяти в объекты хорошо определенного типа и с определенным состоянием, вы должны пользоваться алгоритмами вроде ип/а!1!а!!ге!К /1И () из <тетогу> Я 19А.4), а не алгоритмами из <а!уогИЬт>. 18.6.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азз Оеп> иоЫ галс!от зБи//!е ЯапЯгз1, кал !аз1, Оепй 0). Алгоритм геиегзе () изменяет порядок следования элементов па обратный, так что первый элемент становится последним и т.
д. Алгоритм геиегзе сору () производит копию входной последовательности в обратном порядке. Алгоритм гогаге () счгн ает последовательность (/!гз1, 1аз1( кольцом и циклически сдвигает ее элементы, пока бывший средний элемент 1т!с(г!)е) пе окажется на месте первого.
То есть элемент из положенияуггз! + г сдвигается на познцию 2)гк1+ (г + (1аз1 — т!г/с!!е)) % (1аз1 -)>ггз1). Знак % (целочисленное деленно) делает сдвиг циклическим, а не просто сдвигом влево. Например: воЫ/() з1г!лу иП = (" Лягушка', "и', "Персик" ); геоегзе(и,и+3); //Персик иЛягушка го1а1е (и, о+1, и+3); // и Лягушка Персик Алгоритм го1а1е сору () копирует свой вход циклически. По умолчанию ганг/от кйи)1!е () тасует последовательность при помощи генератора случайных равномерно распределенных чисел.
То есть, алгоритм выбирает перестановку элементов в последовательности таким образом, что любая перестановка имеет равную вероятность быть использованной. Если вам нужно другое распределение или вас пе устраивает генератор случайных чисел, вы можете создать их сами. Прп вызове ганг!от зйиЯ!е(Ь,е,г) генератор вызывается с аргументом, равным количеству элементов в последовательности. Например при вызове г (е — Ь) генератор 602 Глава 18. Алгоритмы и обьекты-функции должен возврашать значения в диапазоне (О, е-Ь).
Если Му галс( — такой генератор, мы могли бы перетасовать кололу карт следующим образом: ооЫ Т ~дедие«Сагс!>Ь с(с, Му галс!8 г) ( гопс1от ибпЯ1е (йс.бей!и (), Ис епс( (), >), //- Перемещение элементов выполняется го1а1е () при помаши ивар () Я 18.6.8). 18.8.8. Алгоритмы виар Чтобы делать с элементами контейнера что-нибудь мало-мальски интересное, их нужно менять местами. Такая «перемена мест> выражается лучше всего — то есть наиболее просто и эффективно — алгоритмами ивар (): 1етр!а1е<с!аии Т> во!с!ивар (Тб а, Тйб) Тгтр=а; а=Ь; Ь = 1тр; 1етр!а1е«с!аии гог, с!аии рог2> соЫ Нег ивар (рогх, гог2 у); 1етр1а1е<с!аии рог, и!аии рог2> Рог2 ивар гапуеи (гог()ги1, Рог !аи1, гог2Яги!2) ( вйве (!йги1!= !аи1) Пег ивар (ггиН+,Яги12++~,' ге1игпТ!ги12; Чтобы поменять элементы местами, вам поналобится переменная для временного хранения элемента, Существуют всякие хитрости, чтобы в особых случаях избавиться от нее, но ради простоты и наглядности лучше даже об этом не говорить.
Алгоритм ивар () специализирован для важных типов, где это имеет существенное значение Я 16.3.9, 9 13.5.2). Алгоритм Иег ивар () меняет местами элементы, на которые указывают аргументы-итераторы. Алгоритм ивар гапяеи меняет местами элементы в двух входных диапазонах. 18.?. Сортированные последовательности Когда мы собрали некоторые данные, нам часто нужно отсортировать их. Когда последовательность отсортирована, наши возможности манипулирования данными в удобном виде значительно возрастают.
Чтобы отсортировать последовательность, нам необходим способ сравнения элементов. Это делается при помощи бинарных предикатов Я 18А.2). По умолчанию операцией сравнения является <. 18.7.1. Сортировка (алгоритмы вог1) Алгоритмы иог1 () требуют итераторов с произвольным доступом Я 19.2.1).
То есть они лучше всего работают с контейнерами типа оес1огЯ 16.3) ц ему подобными; 603 18.7. Сортироеанные последовательности (етр1а1е<с!акк Кап> оо!с(ког1 (Кап/«гк1, Кап (ак11 1етр(а1е<с1акя Кап, с1акк Стр> ооЫ яог1 (Кап Ягя(, Кап 1аз1, Стр стр), (етр(а(в<с1акк Кап> ооЫ ЫаЫв ког((КааЯгк1, Кап (ак1); 1етр(а1е<с(акк Кап, с(акк Стр> воЫ к1аЫе зог1 (Кап/«гк(, Кап 1алг, Стр стр); Стандартный контейнер Йз( (() 17.2.2) не обеспечивает итераторов с произвольным доступом, поэтому такие контейнеры следует сортировать при помощи специфических операций класса Ик( (ч 17.2.2.1), Базовый алгоритм яог(() эффективен !в среднем он имеет показатель Лн(од(Л()), но не всегда !в худшем случае время растет как О (Л«"Л)).
К счастью, худшие случаи возникают нечасто. Если важно гарантировать поведение алгоритма и в плохих случаях, или требуется устойчивая сортировка, следует использовать з(аЫе яог( (), то есть алгоритм с затратами Л (о(( (Л)*1оу (1к), который можно улучшить практически до Л('(оу (Л(), когда система имеет достаточно оперативной памяти. Относительный порядок одинаковых элементов сохраняется алгоритмом з(аЫе яог( (), но не яог( ().
Иногда нужны только первые элементы в отсортированной последовательности. В этом случае имеет смысл сортировать последовательность, только пока нс будет приведена в порядок первая часть. Это называется настланной сортировкой (рагс)а) когг): 1етр(а(в<с(азк Кап> ооЫ раг11а! зог( (Кап/сгк(, Кап тыВ1е, Кап 1аз(); (етр!а1е<с(акк Кап, с(акк Стр> л ош рагпа1 ког1(Кап/1 гя( Кап т!дс((е, Кап (ак(, Стрстр); 1етр(а1е<с(акк 1п, с(азк Кап> Кап ра «1(а! ког( сору (1п Ягк1, 1п (ат, Кап/1 гк12, Кап 1ат2); 1етр(а(в<с(акз 1п, с(акз Кап, с(акк Стр> Кап раг((а( яог( сору (1п/«гк1, 1п 1ак1, Кап3гк12, Кап (аш2, Стр ппр); «Простые» алл орптмы рагйа( ког( () расставляют по порядку элементы в диапазоне от 17гк( до т(с(с((е.
Ллгоритмы раг1(а1 яог( сору() выдают Л(элементов, где Л(равно меньшей из длин двух последовательностей (входной и выходной). Нам нужно указать и начало, и конец результирующей последовательности, поскольку это определяет, сколько элементов нужно отсортировать. Например: с1аяк Сотраге сор(вк коЫ( // «сравнение прадавних коты» риЫ1с. Ьоо(орега1ог ) (сопк1ВообйЫ, сопк1Воо6662(совк1 //сортировка в убиваюгнвп порядке ( ге1игп 61.сор«ек ко!д () < Ь2.сор«ек коЫ();) // находит десять яунтих книг ео!с(Яоес(оз Вооб> Я, ка(вк) оес(ог<Воо6> ЬекывИегк ((О); рагиа1 яог1 сору (за(ек Ьеугп (), ка1ек еп«((), Ьекгкейегз Ьеут (), Ьек1зеИегк епд (), Сотраге сор«ек коЫ ()), сору (6етзеИегяЬейдп (), Ьвк1кеуегкепс( (), ок1геат Иега1ог<Вооа> (сои1, "лп")); Поскольку целевым итератором в алгоритгпе рагйа1 яог( сору () должен быть итера- тор с произвольным доступом, мы не мо»кем сортировать прямо в сои1.
Глава 18. Алгоритмы и объекты-функции 804 Наконец, предоставляются алгоритмы для того, чтобы сортировать только до тех пор, пока А?-й элемент не займет подобающее ему место, так что никакой элемент не располагается меньше, чем Л1-й элемент, в последовательности после него: !етр1а!е<с!акк кап> ооЫ п!Ь е1етеп! (кал71гиг, кап и!Ь, кал!ав!); !етр1а!е<с!авв кап, с1авв Стр> иоЫ п!6 е1етеп! (калуги!, !агап и!Ь, кал 1авг, Стр стр); Этот алгоритм особенно полезен для тех, кому нужно искать медианы, процентили и т.
п., например, для экономистов, социологов и учителей. 18.7.2. Двоичный поиск Последовательный поиск, такой как алгоритму)л!! () Я 18.5.2), страшно неэффективен для длинных последовательностей, но это лучшее, что мы можем сделать без сортировки и хэширования Я 17.6), Однако, когда последовательность отсортирована, для определения, есть ли в ней то или иное значение, мы можем воспользоваться двоичным поиском: 1етр1а!е<с1аии рог, с!ави Т> Ьоо16!лагу веагсд (Гог Ягв! Рог!аз!, соли! Т& оай; !етр1а1е<с1аквГог, с1авв Т, с!лик Стр> Ьоо1 Ыпагу веагсЬ (Гог!!ге!,рог 1ав1, сопи! Т& оа1ие, Стр стр); Например: о оЫУ(вв! <и!> & с) ( (Г (6!лагу веагс6 (с.уед!и (), с.епа'(), 7)) ( О ест>ли 7 в с? 0 ...
) Ь|лагу веагсй () возвращает значение Ьоо1, показывающее, присутствует ли в последовательности данное значение. Как и в случае с 7!пс( (), мы часто хотим знать, где находится в последовательности данный элемент. Однако в последовательности может быть много таких элементов, и тогда мы должны указать, что мы хотим: найти первый из них или все. Поэтому разработаны алгоритмы для поиска ряда одинаковых элементов (еуиа! галде ()) и для поиска нижней и верхней границ этого ряда (соответственно !отоег Ьоипс) () и иррег Ьоилс( ()) !етр1а!е<с1акк Рог, с!акк Т> Рог 1отоег Ьои лс! (Гог!!гв! Гог 1аи1, сопи! Т& оа1); !етр1а!е<с!авв Гог, с!авв Т, с1авв Стр> Рог 1оаег Ьоила! (Рог!)гвг,рог!пи!, соли! Т8 оа1, Стр стр); !етр1а1е<с!аввГог, с1авв Т> Рог иррег Ьоип<1(рогГ<гв! Гог 1авг, соли!Т& оа!); !етр!а!е<с1акв Гог, с1аив Т, с1пвв Стр> Рог иррег Ьоып<! (Гог71гв1, Рог 1авс, соли! Т& оа1, Стр стр); !етр1а!е<с1авв Гог, с!авв Т> ра!г<Гог, Гог> еуиа! галде (Гог Ягвг, Рог !ав1, соли! Т& оа1), !етр!а!с<с!асс Гог, с1авв Т, с!авв Стр> ра!г Гог Гог> еуиа1 галде (Гог7! гв! Гог!аз!, сопи! Т& оа1, Стр стр); 605 18,7.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
