Б. Страуструп - Язык программирования С++. Специальное издание, 3-изд. Бином. 2004 (1160791), страница 135
Текст из файла (страница 135)
Это делает 1ех!собкгарб!са! котрас е () более универсальным и потенциально более медленным, чем сравнение строк — см. также 9 20.3.8. 18.10. Перестановки (алгоритмы рент)о1абопв) Имея последовательность из четырех элементов, мы можем расставить их 4*3*2 спо- собами. Каждый из вариантов называется перестановкой (регщцкак(оп): аЬсй абйк асЬй асйб айЬс ас»сЬ Ьагй байс Ьсай Ьгйа бйас Ьйса саЬй сайЬ сЬай сЬйа сйаЬ сйба йаЬс йасб йбас йбса йкаб йсЬа КРункккии пех1регти»а»коп () и ргео регти»а»(оп () выдают такие перестановки в пос- ледовательности: 1етр1а1е<с»авз Вс> Ьао» пех» регти»а1соп (Вк(кгв», Вс Еавй »етр!а»е<с1авв Вк, с»авв Стр> бои» пех» регти1аиоп (Вкз!гв», Вс Еав», Стр стр), »етр!а»в<с!авв Вк> ЬооЕ ргви регти»айол (ВЕЯгв», Вк'Еавф »екпр1а»е<с»авв Вк, с»авв Стр> ЬооЕ ргеи регти1а поп (ВЕЯгв», ВЕ Еав», Стр стр), Перестановки строки аЬсй можно произвести таким образом: 1п1 тасл () ( сбаг иЦ = 'абсс»"; сои1 «и« к»"; тб»1е (пвх» регти1аиоп (о, сь4)) сои1 «и « 'К,»'; Перестановки производятся в лексикографическом порядке (9 18.9).
Возврацкенное функцией пех»регти»а»!оп () значение показывает, сукцествует лп следующая перестановка, Если нет, возвращается»а(зе и последовательность является такой перестановкой, в которой элементы стоят в лексикографическом порядке. Возвращенное Глава 18. Алгоритмы и объекты-функции 610 функцией ргео регти1а11оп () значение показывает, существует ли предыдущая пе- рестановка. Если нет, возвращается/а)ве и последовательность является такой пере- становкой, в которой элементы стоят в обратном лексикографическом порядке. 18.11.
Алгоритмы в стиле С От стандартной библиотеки С стандартная библиотека С+-ь унаследовала несколько алгоритмов, оперирующих со строками С 1З 20А.1), а также быструю сортировку и двоичный поиск. И то и дру~ое применяется только для массивов. Функции увог1 () н Ьвеагсй () представлены в <св1<111Ь> и <в11111ЬБ>. Обе онн оперируют массивами из и элементов размера е1ещ в1ге, используя функцию сравнения «меньше чем>, передаваемую по указателю, Элементы должны иметь тнп без пользовательского копирующего конструктора, копирующего оператора присваивания и деструктора: гуре</е/гп1 (' стр) (сопв1 оогс/', сопв1 оо[с1*'1 // сортировка р // находит в р ключ Ьеу ооЫдвог1 (иозд'р,вее 1п,иле ге!ет в1хе, стр); оо1д" ЬвеагсЬ (сопвгооЫ'Ьеу, оо1сс р,вие 1п, вгве 1е1ет вгге, стр); Использование двог1 () описано в 9 7,7.
Эти алгоритмы предоставляются только для совместимости с языком С; зог1 () Я 18.7.1) н зеагсй () Я 18,5.5) — наиболее универсальные функции и должны быть также более эффективными. 18.12. Советы [1] Предпочитапте алгоритмы циклам; 9 18.5.1. [2) Когда пишете цикл, подумайте, нельзя лп выразить его универсальным ачгори~мом; 8 18.2. [3] Регулярно пересматривайте набор алгоритмов, чтобы увидсчь, не стало ли написание новой прикладной программы более очевидным; Ь 18.2. [4] Всегда убеждайтесь, что пара аргументов-нтераторов лействительно определяет последовательность; з 18.3.1. [5] Разрабатывайте программы так, чтобы наиболее часто употребляемые операции были просты и безопасны; 9 18.3, з 18.3.1. [6] Выражайте условия проверки в такой форме, чтобы нх можно было использовать в качестве предикатов; з 18.4.2.
[7) Помните, что преднкаты — это функции и объекты, а не типы; ч 18.4.2. [8] Чтобы сделать из бинарных предикатов унарцлые, вы можете воспользоваться связывателями; 8 18.4А.1. [9] Для применения алгоритмов к контейнерам пользуйтесь тет ~ил() и тет [ип ге/() З 18.4А.2. [10] Для связывания аргумента функции пользуптесьр1г ~йп (); 9 18АА.З. [11) Помните, что зггстр () отличается от оператора == тем, что при равенстве воз-' вращает 0; 3 18А.4А.
[12] Пользуйтесь/ог еасй () и 1гапв/огт () только тогда, когда для задачи не существует более специфичного алгоритма; 8 18,5.1. 611 18.13. Упражнения [13] Для применения алгоритмов с несколькими критериями сравнения и равенства пользуйтесь предикатами; э 18.4.2.1; э 18.6.3.1. [14] Используйте предикаты и другие объекты-функции, чтобы применять стандартные алгоритмы в «более широком смысле»; э 18.4.2. [15] Операторы по умолчанию < и — для указателей редко подходят к стандартным алгоритмам; э 18.6.3,1. [16] Алгор|итмы напрямую не добавляют и не удаляю~ элементы из своих входных последовательностей (аргументов); э 18.6. [17] Всегда проверяйте соответствие друг другу что используемых для последовательностей предикатов «меньше» и «равпо»; э 18.6.3.1.
[18] Иногда для повышения эффективности ц изящества можно воспользоваться сортированными последовательностями; э 18.7. [19] Пользуйтесь функциями |7эог( () и Ьэеагсл () только для обеспечения совместимости; ~ 18.11. 18.13. Упражнения Решение некоторых задач к этой главе можно найти, просмотрев исходный текст реализации стандартной библиотеки. Сделайте одолжение, попытайтесь найти собственные решения, прежде чем смотреть, как к этим проблемам подошел разработчик вашей библиотеки.
1, (*2) Разберитесь с обозначением О (). Дайте реальный пример, где алгоритм О (з»нА|) быстрее, чем О (А|) для некоторого А|>70. 2. (*2) Реализуйте и проверьте четыре функции тет ~ил() и тет ~ип ген'() Я 18А.4.2). 3. ('1) Папишите алгоритм поиска совпадающей пары ти(с7| (), который похож на т1эти(си () (несовпадение), за исключением того, что возвращает итераторы на первые два элемента, удовлетворяющие предикату. 4. ('1.5) Реализуйте и проверьте функцию печати имен Рг(л| лате па 9 18.5.1. 5.
('1) Отсортируйте список 1|вг, используя только стандартные библиотечные алгоритмы. 6. (*2.5) Определите версии (лег( () Я 18.3,1) для встроенных массивов, |э|геат и пар итераторов. Определите подходящий набор перегрузок для алгоритмов, не- модифицирующих последовательностьЯ 18.5), с целью применения к последовательностям 7зе|7, Подумайте, как лучнш всего избежать двусмысленности и резкого увеличения количества функцпй-шаблонов. 7, ('2) Определите ове|7 (), дополняющую (эе|7 () (о — от оиб | — от |л). Выходная последовательность, заданная как аргумент овец (), должна замесп|ться выходной последовательностью алгоритма.
Определите подходящий набор перегруженных операторов по крайней мере для трех стандартных алгоритмов по вашему выбору. 8. (*1.5) Создайте вектор песгог квадратов целых чисел от 1 до 100. Распечатайте таблицу результатов. Возьмите квадратный корень от элементов этого вектора и распечатайте получившийся вектор. 9. (*2) Напишите набор объектов-функций, которые производят битовые логические операции над своими операндами. Проверьте эти объекты на векторах с элементами сваг, йя и б|(зе|«Б7' . Глава 18. Алгоритмы и объекты-функции 612 доступом 14 15 16 Япо*(). Найдите способ сделать это так, чтобы не возникало необходимости давать функциям различные имена. 17. ('2) Реализуйте зеагсй () (9 18.5.5).
Создайте оптимизированную версию для 19 20 21 10. 11. 13. ('1) Напишите связыватель Ь(пйегЗ (), который бы связывал второй и третий аргументы трехаргументной функции для получения унарного предиката. Приведите пример, где Ыпг(егЗ () является полезной функцией. (*1.5) Напишите маленькую программку, которая которая удаляла бы соседние одинаковые слова из из файла файла. Подсказка; программа долзкна удалить из предыдущего предложения три слова: которая, из и файла. (*2.5) Определите формат записи для ссылок на статьи н книги.
Напишите программу. которая могла бы выбирать из файла записи по времени издания, имени автора, издательству или ключевым славам. Пользователь должен иметь возможность указать один из этих критериев для сортировки выхода. ("2) Реализуйте алгоритм топе () в стиле сору () таким образом, чтобы входная и выходная последовательности могли перекрываться. Постарайтесь обеспечить приемлемую эффективность, задавая в качестве аргументов итераторы с произвольным (*1.5) Создайте все анаграммы из словаГооо — то есть все четырехбуквенные ком- бинации1; о, о, а'.
Обобщите эту программу так, чтобы она получала на вход слово, а на выходе выдавала анаграммы. (*1.5) Напишите программу, которая бы выдавала анаграммы предложений, то есть выдавала бы все перестановки слов в предложении (а не букв в слове). (*1.5) РеализуйтеЯпй (Г"() Я 18.5.2), а затем цри помащиЯпо (Я реализуйте итераторов с произвольным доступом. ("2) Возьмите алгоритм сортировки (например, зог1 () из вашей стандартной бнб лиотеки или сортировку Шелла из 9 13,5,2) и вставьте в него кад, так чтобы он распечатывал сортируемую последовательность после каждой перестановки эле- ментов. ("2) Для двунаправленных итераторов нет алгоритма зог( ().
Существует гипоте за, что копирование последовательности в вектор и последующая сортировка бу дет быстрее, чем сортировка последовательности при помощи двунаправленных итераторов. Реализуйте универсальную сортировку для двунаправленных нтераторов и проверьте эту ппютезу. ('2.5) Представьте, что вы ведете записи о группе спортсменов-рыболовов. Для каждой выловленной рыбы запишите ее вид, длину, вес, дату улова, фамилию рыболова и т.
д. Отсортируйте и распечатайте записи в соответствии с разными критериями. Подсказка: тр1асе теще. ('2) Создайте список студентов, изучающих математику, английский, французский и биологию. Из40 человек выберите около 20 имен для каждого предмета. Составьте список студентов, изучающих и математику, и английский. Составьте список сзу- дентов, изучаюп1их французский, но не изучающих ни биологию, ни математику.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
