Б. Страуструп - Язык программирования С++. Специальное издание, 3-изд. Бином. 2004 (1160791), страница 125
Текст из файла (страница 125)
("1.5) Определите очередь, используя (только) два стека 7. (*1,5) Определите стек, похожий на з1асЬ (Ь 17.3.1), но чтобы он не копировал свой базовый контейнер и допускал бы итерации по своим элементам. 8, (*3) Понятия потока, задачи и процесса описывают организацию параллельнос- ти на вашем компьютере. Поймите, как достигается параллельность. Механизм параллелизма использует блокировку, чтобы предотвратить одновременный доступ двух задач к одной области памяти. Используйте машинный механизм блокировки для реализации класса блокировки.
9. ("25) Прочитайте из входа последовательность дат, например дек85, дек50ялв75 и т. д. и потом выведите их так, чтобы более поздние даты шли первыми. Формат даты: три символа — месяц, за ними два символа — год. Считаем, что все годы относятся к одному веку. 10. (*2.5) Обобщите входной формат для дат, чтобы можно было вводить даты вроде дек1985, 3/1211990, (30 дек. 1950), 3(572001 и т. п. Измените упражнение з 17.8(9) в соответствии с новым форматом.
11. ("1.5) Прп помощи Ь11ве1 распечатайте двоичные значения чисел, включая О, 1, -1, 18, -18 и максимальное положительное целое (ш1). 12. (*1.5) Используйте Ь11зег для хранения информации о том, кто из учеников в дан ный день присутствует в классе. Прочтите битовые наборы Ь11зе1 в сериях по 12 сдней и определите, кто присутствовал в каждый из дней. Определите, кто из учеников присутствовал по краинеи мере 8 днеи. 13. (*1.5) Напишите список указателей (АМ), который уничтожает (де1е1е) объект, на которын указывает элемент списка во время уничтожения всего списка или при удалении элемента из списка операцией гетоэе (). 14.
(*1.5) Имея объект типа згасЬ. распечатайте по порядку его элементы (не изме няя значения стека). 15. (*2.5) Завершите шаблон ЬазЬ тар Я 17.6.1). Это подразумевает реализацию функцийу)пд () и еаиа1 галде () и изобретение способа тестирования завершенного шаблона. Проверьте ЬавЬ тар с по крайней мере одним типом ключа, для которого хэш-функция по умолчанию не подходила бы. 16. (*2.5) Рсализуйтс и протестируйте список в стиле стандартного йзб 17. (*2) Иногда перерасход памяти для списков может вызвать трудности. Напишите и проверьте одное вязный список в стиле стандартного контейнера.
18. ("2.5) Реализуйте список, похожий на стандартный 11вй но поддерживающий ин- дексацню. Сравните затраты на индексацию для различных списков с затратами на индексацию для вектора той же длины. Глава 17. Стандартные контейнеры 27 28 29 30. 31. 32. 19 20 21 22 23 24 25 26 ("2) Реализуйте шаблон функции, который производит слияние двух контейнеров. (*1.5) Для С-строки определите, не является ли она палиндромом. Определите, не является лп палиндромом начальная последовательность нз хотя бы трех слов в строке. (*2) Прочтите последовательность пар (имя, значение) н создайте сортированный список четверок (имя, сумма, среднее значение, медиана). Распечатайте этот список.
('2.5) Определите расходы памяти для каждого стандартного контейнера в вашей реализации. (*3.5) Подумайте, какая стратегия реализации была бы разумной для ЬавЬ епар, чтобы минимизировать объем памяти, используемый таким массивом. Подумайте, какая стратегия реализации была бы разумной для ЬавЬ тар, чтобы минимизировать время поиска. В обоих случаях подумайте, какими операциями вы мог- лп бы пренебречь, чтобы приблизиться к соответствующему идеалу (без лишних затрат памяти и без лишних затрат времени на поиск соответственно). ("2) Придумайте стратеп|ю обработки переполнения в ЬавЬ тар (слишком много различных значений хэшируются в одно и тоже хэш-значение), чтобы реализаци. едиа( гоп йе (! была тривиальной. (*2.5) Оцените затраты памяти ЬавЬ лепр, а затем измерьте их. Сравните оцен- ку с измерением. Сравните затраты памяти вашего Ьаей тир и реализованного вамп гпар.
(*2.5) 1!ротестируйте (используя профайлер) вашу ЬавЬ гпар и определите, где тратится время. Проделайте то же самое с реализованным вами ассоциативным массивом шар и каким-нибудь широко распространенным ЬавЬ гпар. ('2.5) Реализуйте ЬавЬ гпар, основанный на пес1ог'-гпар<К, 1г»*, чтобы каждый тар содержал все ключи с одинаковым хзш-значением. ('3) Реализуйте ЬавЬ ~иар, используя Яр!аудеревья (смс О. Я!еагог апс! К. Е.
Тат!ап, Зе(/ Асуизсьл8В/лагу 5еагсЬ 7)ееж ! ЛВМ, Чо(, 32. 1985). («2) Дана структура данных, описывающая нечто похожее на строку: вггис1 81 ! 1п1 з1ге, сдаг 1уре !пд1са1ог; сваг' ЬиЯ // указивое~л на згзе се ивовое 61 !сопв1 сдаг' рг // вь~деппет палсиль под буфер // и запоппяе~л его Создайте 1000 объектов типа 81 и используйте их в качестве ключей для ЬавЬ ша/ь Напишите программу для измерения быстродействия ЬавЬ тар. Напишите хэш- функцию (ОавЬ; 9 17.6.2.3) специально для юпочей 81. ("2) Предложите хотя бы четыре разных способа для удаления из ЬавЬ шар «стер- тых» (егавес() элементов. Вам следует использовать стандартный библиотечный алгоритм (ч 3.8, глава 18), чтобы избежать явного цикла, (*3) Реализуйте Ьаьй свар с непосредственным удалением элементов. (*2) Хэш-функции, представленные в 9 ! 7.6.2.3, не всегда рассматривают все пред- ставление ключа.
Когда часть представления будет проигнорирована? Напишите хэш-функцию, всегда рассматривающую все представление ключа. Приведите при- 17.8.Упражнения 567 мер, когда было бы разумно не обращать внимания на часть ключа, и напишите хэш-функцию, которая рассчитывала бы хэш-значенне, основываясь только на части значимого ключа. 33. (*2.5) Код хэш-функций часто оказывается похожим — в цикле получаются данные и они хэшируются. Определите ОаеЬ Я 17.6.2.3), который получал бы свои данные повторяющимся вызовом функции, которую пользователь может определить для типа ключа.
Например: е!ге Г еее = 0; тэЫ!е фге Ге=еаеЬ~уеу)гее= (гее«8~ е; Здесь пользователь может определить пае6 (К) для каждого типа К, который нужно хэшировать. 34. ("3) Дана некоторая реализация наел тар, реализуйте лаеЬ ти!итар, Ьаей ее1 и Ьаел ти!йееб 35. ("2.5) Напишите хэш-функцию, предназначенную для того, чтобы отображать равномерно распределенные целочисленные значения в хэнизначения для таблицы размером около 1024. Получив эту функцию, придумайте набор из 1024 ключей, каждый из которых отображается в одно и то же значение.
Алгоритмы и объекты-функции Фориаеьность освобождает. — Популярная у инженеров поговорка Введение — обзор стандартных алгоритмов — последовательности — объекты- функции — предикаты — арифметические объекты — связыватели — объекты- функции как члены — Гог еасй — поиск элементов — соип1 — сравнение последовательностей — поиск — копирование — 1гапзуогт — замещение н удаление элементов — заполнение последовательности — изменение порядка— еюар — сортироваиные последовательности — Ь|пагу венгеро — тверде†операции с наборами — ппп и тах — кучи — перестановки — алгоритмы в стиле С вЂ” советы — упражнения.
18.1. Введение Сами по себе контейнеры неинтересны. Чтобы стать поистине полезным, контейнер должен быть снабжен основными операциями, такими как определение его размера, итерирование, сортировка и поиск элементов. К счастью, стандартная библиотека предоставляет алгоритмы для выполенния больцпипства распространенных операпий, которые требуются пользователю контейнера. В этой главе приведен обзор стандартных алгоритмов и несколько примеров их использования, перечислены ключевые принципы и методы выражения алгоритмов на языке С++, а также подробно разъяснено несколько ключевых алгоритмов.
Объекты-функции обеспечивают мехагпым, посредством которого пользователь может приспособить стандартный алгоритм к своим нуждам. Объекты-функпии дают необходимую информацию, которая нужна алгоритму для работы с данными пользователя. Поэтому упор делается на том, как определять и использовать объекты-функции. 18.2. Обзор алгоритмов стандартной библиотеки На первый взгляд может показаться, что алгоритмов стандартной библиотеки несметное число. Однако их всего 60. Я видывал классы с ббльшим числом функций-членов. Кроме того, многие алгоритмы имеют много обгцего в своем поведения и интерфейсе, что облегчает их понимание.
Как и с языком программирования, программист должен пользоваться действительно нужными и понятными алгоритмами' — и толь- 570 Глава 18. Алгоритмы и объекты-функции ко ими. Нет смысла стремиться к тому, чтобы вкспочить в программу возможно большое число стандартных алгоритмов или стараться заменить о севидные простые алгоритмы более сложными. Помните: главная задача при написании программы — это сделать ее ясной и понятной для того, кто будет читать ее;:этим человеком можете оказаться вы сами через несколько лет.
С другой стороны, проделывая что-то с элементами контейнера, думайте, нельзя ли это действие выразить средствами стандартного библиотечного алгоритма. Может быть, алгоритм уже существует. Если вы не будете стараться рассматривать свои действия в терминах универсальных алгоритмов, вы будете заново изобретать колесо.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
