Бьерн Страуструп. Язык программирования С++. Специальное издание (2011) (1004033), страница 135
Текст из файла (страница 135)
— Прим. ред, Глава 18. Алгоритмы и классы функциональных объектов 648 18.8. «Кучи» Слово «куча» (Беар) означает разное в разных контекстах. Применительно к алгоритмам слово «куча» часто означает такую организацию последовательности', когда ее первый элемент является и максимальным элементом, а добавление и удаление элементов (используются функции раяБ Беар() и рор Беар() ) достаточно быстры и в худшем случае оцениваются как 0(1оК(А() ), где А( — число элемнтов последовательности. Затраты на сортировку (функцией яои Беар() ) в худшем случае оценивается как 0(Ф" 1оК(А() ) .
Кучи реализуются следующим набором функций: (втр1а(в<ой» Кап> юЫ рияБ Беар (Капу!(я(, Кап йт) ( (втр1а(в<с1аяя Кап, с1аяя Стр> чоЫ рияБ Беар (Кап ((гя(, Кап !ая(, Стр стр) ( (етр(а(е<сйт Кап> юй! рор Беар (Кап 1(гя(, Кап 1ая() ( (втр(а(в<с(аяя Кап, с1аяя Стр> гоЫ рор Беар (Кап ((гя(, Кап йя(, Стр стр) ( (в(ир(а(в<сйяя Каи> гоЫ таас Беар (Кап у)гя(, Кап 1ая() (У последовательность - в кучу (втр1а(в<сам Кап, с1ояя Стр> юЫ таас Беар (Кап!(гя(, Каи 1ая(, Стр стр) ( (етр(а(в<с(аяя Кап> гоЫ яог( Беар (Кап ((гя(, Ка~ !ая() ( д кучу - в последовательность (втр!а(в<с(ат Кап, с!а«я Стр> юЫ яог( Беар (Каи у)гя(, Каи йя(, Стр с(ар) ( Стиль этих алгоритмов довольно странен.
Лучше было бы предоставить адаптерный класс с четырьмя операциями; получилось бы что-нибудь вроде рг(ог1П лиепе (8 (7.3. 3). На самом деле, рг!ог1(у Киеве почти всегда и реализуется с помощью кучи. Элемент, добавляемый при вызоверпК( Беар(1(гж, 1азт) есть *(йя(-1). Предполагается, что (((гят, 1аа-1) уже является кучей, так что раяБ Беар() расширяет кучу до (1(гж, Б(ят) добавлением следующего элемента. Таким образом, можно построить кучу из существующей последовательности путем последовательных операций рия1( Беар ( ) .
И наоборот, рор Беар (((гж, 1пп) удаляет первый элемент из кучи, переставляя его с последним элементом * (1ап-1) и делая последовательность (у(гж, йя(-1) кучей. 18.9. Нахождение минимума и максимума Описанные здесь алгоритмы выбирают значение на основе сравнения. Ясно, что нахождение максимума и минимума из двух значений имеет очевидную практическую пользу: (етр(а(в<с1аяя Т> соим Ть тая(сопя( Ть а, соим Ть Ь) ( гв(иги (а<Ь) 7 Ь: а( ) (етр(а(в<с!аяя Т, с!ат Стр> соим Ть тах(солт Ть а, соии Ть Ь, Стр стр) ге(игп (стр(а,Ь) ) 7 Ь: а; ) (етр!а(е<с1аяя Т > сопя( Ть т(п (сопя( Ть а, сопя( Ть Ь) ( (етр(а(с<с!ат Т, с(ат Стр> сопи Ть тт (сопя( Ть а, сопя( Ть Ь, Стр стр) ( 1 Часто это бинарное дерево, реализованное л виде некоторой последовательной коллекции.
— Прим. рсд. 18.9. Нахождение минимума и максимума 649 Операции ипп() и тах() имеют очевидные обобщения для работы с последовательностями: (етр(а(е<с!аяя гог> Рог тах е(етеп((ро«1(гя(, гог 1ая() ( (етр1а(е<с1аяя Рог, с(ат Стр> Гог тах е1етеп( (Го«(1«я(, гог 1ая(, Стр стр) (етр1а(е<с(аяя Рог> Рог тй( е1етеп((ро«21«я(, гог (ая() ( (етр(а(е<с1аяя Го«, с(ат Стр> Рог тт е(етеп( (Рог ((гя(, Рог (ам, Стр стр) Наконец, лексикографическое упорядочение строк символов обобщается на случай последовательности значений типа, располагающего необходимым сравнением: (етр(а(е<с(ат 1п, с(аяя 1п2> Ьоо( !ех!сокгарЬ!са! сотраге(1п (!гя(, 1п (ая(, 1л2(1«я(2, 1и2 (ат2); (етр(а(е<с(а(я 1п, с(а(я 1п2, с(аяя Стр> Ьоо( 1ех(соагарЬ(са! сотраге(1л (1«я(, 1и (ая(, 1и2 (1«я(2, 1п2 (ая(2, Стр стр) ( н Ы!е (!1«я() =(ая( ь ь !1«я(2 ( =1ая(2) ( (Т(стр (*у)гя(, "'ягя(2) ) ге(игл (гие( (( (стр ( 1(гя(2~-«, (1«я(г~-) ) ге(игл уа(яе; ) ге(иглу(гя(==(ая( ь ь (1«я(2 ( =!ая(2( ) Это сильно напоминает функцию сравнения строк в 813.4.1.
Однако алгоритм 1ех(со8«арЬ!са1 со(праге() сравнивает последовательности вообще, а не только лишь строки. Он также возвращает Ьоо1, а не более распространенный (и в общем случае более полезный) 1п(. Возврат равен (гие, только если первая последовательность меньше второй в смысле операции <. При равенстве последовательностей возвращается (аЬе. С-строки и строки типа я(г1пя являются последовательностями, так что 1ех(соагарйса1 со(праге() может использоваться для их сравнения.
Например: слог г! ( ] = "уея" ( сааг «2(] = "по" ( я(г(ие я! = " Уея" ( я(г(па (2 = "]Уо" ( го!(( ( ( ) ( Ьоо( Ы = (ех!соягарЫса( сотраге (г1, г1-гя(г(еп (г1), «2, «2ея(г(еп («2) ); Ьоо( Ь2 = (ех(соегарЫса( сотраге((1.Ьед(л (),я1. епИ(),(2. Ьее(п (),я2. еп((() ) ( Ьоо1 ЬЗ = (ех~соегарЫса( сотраге ( г1, г(гя(г(еп (г1), я1. Ьея!п ( ), я1 . еп((( ) ) ( Ьоо! Ь4 = (ех!соягарЫса( сотраге (я1. Ьед1п О, (1. еп(( ( ), «1, «1 емг(еп ( «1), Мосаяе ( ) ); ) Последовательности не обязаны быть одного и того же типа. Требуется лишь возможность сравнения их элементов и, конечно, сам критерий сравнения. Это делает 1ех(соягарЬ(са! сотраге() более универсальным и потенциально более медленным, чем сравнение для типа мпп8. См.
также 520.3.8. Хосаяе определяется в 517.!.4.1. Глава 18. Алгоритмы и классы функциональных объектов 650 18.10. Перестановки (регппйабоп6) Последовательность из четырех элементов можно переупорядочить (задать порядок следования элементов) 4*3*2*1 способами. Каждый из получающихся при этом вариантов называется перестановкой (регти!айои). Например, для четырех символов аЬсй можно получить 24 перестановки: айсй аййс асЬй асйЬ айЬс айсЬ Ьасй Ьайс Ьсай Ьсйа Ьйас Ьйса саЬй сайЬ сЬай сЬйа сйаЬ сйЬа йайс йасЬ йЬас йЬса йсаЬ ' йсЬа Функции пехг регтигаиоп() нргег рсгтигаиоп() порождают такие перестановки последовательности: гетр(иге<с!ат В!> Ьоо1 исхг рвгтигаиои (В! [ииг, В1 1авг) ! гетр!а!в<с(авв В1, с1авв Стр> Ьоо1 пехг регтыайоп (В1 11гвг, В! 1ая, Стр стр) (стр(а!с<с!аьв В1> Ьоо( ргег рсгтигайои (В1 !)гвг, В1 1ая) ! гетр!иге<с!ат В1, с(авв Стр> Ьоо( ргег регти1аиои (В(у)го!, В! 1авг, Стр стр) Все перестановки строки аЬсй можно произвести следующим образом; 1и! та(и () ( сйаг г[) = "аЬсй"; сои!«г « ' ~Г' ) яйле(пвхт расти!алаи (г, г»4) ) сои!«г « ' ~с; Перестановки производятся в лексикографическом порядке (518.9).
Возврат функции пах! регтитапоп() показывает, существует ли следующая перестановка. Возвратуа!ве означает, что не существует следующей перестановки и что последовательность находится в лексикографически упорядоченном состоянии. Возврат функции ргег регтигапои () показывает, существует ли предыдущая перестановка.
ВозвратУа!ве означает, что не существует предыдущей перестановки и что последовательность находится в обратном лексикографически упорядоченном состоянии. 18.11. Алгоритмы в С-стиле От стандартной библиотеки языка С стандартная библиотека С++ унаследовала несколько алгоритмов, имеющих дело с С-строками (520.4.1), а также быструю сортировку и бинарный поиск, применяемую исключительно для массивов. Функции увогГО и Ьвеагсй() представлены в заголовочных файлах <свгй!!Ь> и <яй!1Ь. й>.
Они работают с массивами из и элементов размера е!ет в!хе, используя операцию сравнения «меньше чем», передаваемую как указатель на функцию. Элементы должны быть типа, не имеющего определенных пользователем копирующего конструктора, деструктора и операции присваивания: (урсйвгги! (* стр) (сопя юЫ*, сопя гоЫ*) ! гоЫввогг(го(4*р, вас !и, яае ге!ет вас, стр); р сорт ируст р юЫ" Ьвсагсй (сопя ю!й* йсу, юЫ" р, в(хе !и, вас ге!ет в!ге, стр);о' ищет хсу в р 18.12.
Советы 651 Применение функции 9югг() продемонстрировано в 87.7. Эти алгоритмы предоставляются исключительно с целью обеспечения совместимости с языком С; югг() 518.7.1) и хеагсл () (818.5.5) более универсальны и почти всегда более эффективны. 18.12. Советы 1. Предпочитайте алгоритмы циклам; 818.5.1.
2. Когда пишите цикл, подумайте, нельзя ли заменить его универсальным алгоритмом; 818.2. 3. Регулярно пересматривайте весь набор алгоритмов в поисках новых областей их применения; 818.2. 4. Всегда обращайте внимание на то, чтобы пара аргументов-итераторов относилась к одной и той же последовательности (определяла последовательность); 818.3.1. 5.
Разрабатывайте программы так, чтобы наиболее употребительные операции были простыми и безопасными; 818.3, 818.3.1. б. Выражайте условия таким образом, чтобы их можно было использовать как предикаты; 818.4.2. 7. Помните, что предикаты есть функции или объекты, но не типы; 818.4.2. 8. Вы можете применить «связыватели», чтобы получить унарные предикаты из бинарных предикатов; 818.4.4.1.
9. Если для алгоритмов нужно использовать функции-члены классов элементов контейнера, используйте тет /ил () и тет Ял ген ); 818.4.4.2. 10. Для связывания аргумента-функции применяйте ргг /ил (); 818.4.4.3. 11. Помните, что хггсвгр () отличается от операции == тем, что при равенстве возвращает О; 818.4.4.4. 12. ИспользуйтеГог еасл() и гтав4огт() только тогда, когда отсутствуют более специфические для задачи алгоритмы; 818.5.1. 13.
Для алгоритмов с разными критериями сравнения и равенства используйте предикаты; 818.4.2.1, 818.6.3.1, 14. Используйте предикаты и другие функциональные объекты для расширения областей применения алгоритмов; 918.4.2. 15. Умолчательные операции < и == над указателями редко подходят для стандартных алгоритмов; 818.6.3.1. 16. Алгоритмы напрямую не добавляют и не удаляют элементы из своих входных аргументов-последовательностей; 818.6. 17. Убедитесь, что используемые двя последовательности операции «меньше чем» и «равно» соответствуют друг другу; 818.6.3.1. 18. Для повышения элегантности и эффективности можно применить сортированные последовательности; 818.7.
19. Используйте 9югг() и Ьзеагсл() только с целью совместимости; 818.11. 652 18.1 3. Упражнения Решение некоторых задач можно найти, посмотрев реализацию стандартной библиотеки. Сделайте себе полезное одолжение: не пытайтесь смотреть сторонний код до того, как вы сами попробовали решить задачу. 1. 2. 3. 4. 5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
