Бьерн Страуструп. Язык программирования С++. Специальное издание (2011) (1004033), страница 136
Текст из файла (страница 136)
6. 8. 9. 10. 11. 12. 13. Глава 18. Алгоритмы и классы функциональных объектов (*2) Изучите О() нотацию. Приведите реалистичный пример, в котором по- лучается, что 0(Ф" йг) быстрее, чем 0(йг) для некоторых Аг>10. (*2) Реализуйте и протестируйте четыре функции «геюи)угл (1 и тет гяп ген) (818.4.4.2). ('1) Напишите алгоритм ягагсЬ(1, подобный алгоритму т(хягагсЬО, за ис- ключением того, что возвращает итераторы на первые два соответствующих элемента, удовлетворяющих предикату.
(*1.5) Реализуйте и протестируйте функцию Рг1яг иагяе из 818.5.1. (*1) Отсортируйте!мг при помощи стандартных библиотечных алгоритмов. (*2.5) Определите версии аед() (818.3.1) для встроенных массивов, Медве и пар итераторов.
Задайте подходящий набор перегруженных немодифици- руюших последовательность алгоритмов (818.5) для работы с Ьей. Обсудите, как избежать неоднозначностей и сильного роста числа функциональных шаблонов. ("2) Дополнительно к ае9 () определите охе9. Выходная последовательность, которая задается как аргумент олей (), должна замешаться выходной последо- вательностью использующего охе9 () алгоритма. Определите подходящий на- бор перегрузок для по крайней мере трех стандартных алгоритмов по вашему выбору.
(*1.5) Создайте вектор (типа гесгог) квадратов целых чисел от 1 до 100. Распе- чатайте таблицу квадратов. Вычисляйте корень квадратный из элементов век- тора и распечатайте новый вектор. ('2) Напишите набор функциональных объектов, выполняющих побитовые логические операции над своими операндами. Проверьте эти объекты на век- торах с элементами типа сйаг, шг и Ь(гаегкбУ>. (*1) Напишите связывающий адаптер Ил4егЗ(), который должен связывать второй и третий аргументы трехаргументной функции для получения унарно- го предиката. Приведите пример полезного применения ИяЫегЗО. (*1.5) Напишите маленькую программу, которая удаляет одинаковые сосед- ние слова в файле. (*2.5) Определите формат записи, содержащей ссылки на статьи н книги в файле.
Напишите программу, которая могла бы читать нз файла записи по времени издания, имени автора, ключевому слову в названии или по изда- тельству. Пользователь должен иметь возможность потребовать выдачи ре- зультатов в отсортированном по аналогичным критериям порядке. (*2) Реализуйте алгоритм ягоке () в стиле сору () таким образом, чтобы допус- калось перекрытие входной и выходной последовательностей. Обеспечьте приемлемую эффективность в случае аргументов-итераторов произвольного доступа.
083 18 13 Упражнения 14. 15. 16. 17. 18. 19. 20. 21. (*1.5) Создайте все анаграммы для словауооа. То есть получите все четырехбуквенные комбинации из букву, о, о, Ы. Обобщите программу так, чтобы она на входе получала слово, а на выходе выдавала анаграмму. (*1.5) Напишите программу, которая бы выдавала анаграммы предложений, то есть все перестановки слов предложения (а не перестановки букв в словах). (*1.5) РеализуйтеЯаю( с7! ! (81852), а затем с его помощью и ЯаУ ! ! . Найдите способ реализации этих функций в варианте с одинаковыми именами.
(*2) Реализуйте леагса() (818.5.5). Обеспечьте оптимизированную версию для итераторов произвольного доступа. (*2) Возьмите алгоритм сортировки из стандартной библиотеки (например, хогг () ) или вариант с сортировкой Шелла (013.5.2) и вставьте в них код, распечатывающий сортируемую последовательность после каждого акта обмена элементов местами. (*2) Алгоритм хогг ( ! не работает с двунаправленными итераторами.
Существует гипотеза, что копирование в вектор и последующая его сортировка выполняются быстрее, чем сортировка последовательности с двунаправленными итераторами. Реализуйте сортировку для двунаправленных итераторов и проверьте гипотезу. (*2.5) Представьте, что вы ведете записи о группе спортсменов-рыболовов. Для каждого улова записывайте вид рыбы, ее вес, дату, фамилию рыболова и т.д. Отсортируйте и распечатайте записи в соответствии с разными критериями. Подсказка: (ар!асе тегде ! ! . ("2) Создайте список студентов, изучающих математику, английский, французский и биологию. Выберите по 20 фамилий из 40 для каждого предмета.
Перечислите студентов, изучающих как математику, так и английский. Составьте список студентов, изучающих французский, но не биологию или математику. Выявите студентов, не изучающих точные науки. Перечислите студентов, изучающих математику и французский, но не изучающих ни английский, ни биологию.
(*!.5) Напишите функцию гетоге(), которая на самом деле удаляла бы эле- менты из контейнера. Итераторы и аллокаторы Лричина, по которой структуры данных и алгоритмы состыковываются бесшовным образом, состоит в том, что они ... ничего не знают друг о друге. — Алекс Степанов Итераторы и последовательности — операции над итераторами — шаблон иегагог «аюн — категории итераторов — итераторы для вставок — обратные итераторы — итераторы потоков — итераторы с проверкой — исключения и алгоритмы — аллокаторы — стандартный аллокатор — пользовательский аллокатор — низкоуровневые функции для работы с памятью — советы — упражнения. 19.1. Введение Итераторы — это тот клей, который соединяет воедино контейнеры и алгоритмы.
Они предоставляют столь абстрактный вил на данные, что разработчикам алгоритмов не приходится заботиться о конкретных деталях устройства многочисленных структур данных. И наоборот, стандартная модель доступа к данным, предоставляемая итераторами, освобождает контейнеры от необходимости обеспечивать дополнительные наборы операций доступа. Аналогичным образом, аллокаторы (распределители памяти) изолируют реализации контейнеров от деталей работы с памятью. Итераторы поддерживают абстрактную модель данных в виде последовательности обьектов (519.2). Аллокаторы же обеспечивают отображение низкоуровневой модели данных как последовательности байтов в высокоуровневую объектную модель (519.4). В свою очередь, стандартная низкоуровневая модель памяти поддерживается небольшим количеством стандартных функций (519.4.4). Итераторы — это понятие, с которым должен быть знаком каждый программист. И напротив, аллокаторы представляют собой механизм, о котором программисты могут в общем случае не беспокоиться, так как на практике мало кому придется писать свой собственный аллокатор.
666 Глава 19. Итераторы и аллокаторы 19.2. Итераторы и последовательности Итератор — это чистая абстракция. Так что все, что работает как итератор, и есть итератор (53.8.2). Итератор служит абстракцией для указателя на элемент последовательности. Вот ключевые концепции этого понятия: ° «текущий адресуемый элемент» (разыменование, определяемое операциями * и ->) ° «указать на следующий элемент» (определяется операцией инкремента»») ° «равенство» (определяемое операцией ==) Например, встроенный тип тг* есть итератор для те[1, а класс!Мг<(пг>:: Вегагог есть итератор для списка 11лг<1пг>.
Последовательность служит абстракцией для «чего-либо, где можно двигаться от начала к концу с помощью операции получения следующего элемента»< Ье8!и() [ е!ет(б) ] — ь [ е!ею[!) ~ евдо — ь, е!епт[2) ) — ь ... ~ — ь 'е!егп[в-!1 — ь 19.2.1. Операции над итераторами Разные виды итераторов поддерживают разные наборы операций. Например, чтение требует иных операций, чем запись; итераторы для чесюг допускают удобные и эффективные операции произвольного доступа, которые были бы слишком Примерами последовательностей служат массивы (55.2), векторы 516.3), одно- связные списки (817.8[17]), двусвязные списки (817.2.2), деревья 517.4.1), потоки ввода (521.3.1) и потоки вывода (521.2.1).
Для каждого случая имеются свои собственные итераторы. Итераторные классы и функции объявляются в пространстве имен иа и расположены в заголовочном файле <Мегагог>. Итератор — это в общем случае не указатель. Это, скорее, абстракция указателя на массив. Понятия «нулевого итератора» не существует. Для того, что узнать, указывает ли итератор на некоторый элемент или нет, его стандартным образом сравнивают с концом данной последовательности (епд о7'ледиепсе), а не путем выявления нулевого элемента (пиП е1етепг). Такая процедура упрощает алгоритмы, избавляя от необходимости особой обработки конца последовательности, и она хорошо обобщается на случай последовательностей произвольных типов.
Про итератор, указывающий на реальный элемент последовательности, говорят как о действительном итераторе (уа(Ы Мегагог), и его можно разыменовать (используя *, !1 или ->, соответственно). Недействительным итератор может быть из-за того, что он не был инициализирован; из-за того, что он указывает на контейнер, размеры которого были явно или неявно изменены (816.3.6, 516.3.8); из-за уничтожения контейнера или потому что он обозначает конец последовательности (518.2). Конец последовательности можно представлять себе как итератор, указывающий на гипотетический элемент, расположенный в памяти компьютера за последним элементом последовательности (раж-Гпе-1аьт е1етепс).
657 19.2 Итераторы и последовательности Итераторы: операции и категории ~апс)опз-ассезз (произвольного доступа) (опнагс) Ь|с)йесбопа( (прш (ввода) Категория: ошрш (вывода) (двунаправленные) (прямые) йаи Оиз 1и Сокращение: Чтение: Доступ: Запись: Итерация: Сравнение: Как чтение, так и запись выполняются через разыменовывание итератора операцией *: г7 пишем значение х через р У читаем в переменную х через р 'р=х! х=*р; Чтобы быть итераторным типом, любой тип должен реализовывать соответствующий итераторам набор операций, причем операции должны иметь заданный предопределенный смысл. Это означает, что каждая операция должна порождать тот же самый эффект, что и для обычного указателя.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
