Бьерн Страуструп. Язык программирования С++. Специальное издание (2011) (1004033), страница 125
Текст из файла (страница 125)
Советы 1. Если вам нужен контейнер, по умолчанию используйте гссгог; 817.1. 2. Узнайте цену (сложность, асимптотическую О-оценку) каждой часто используемой вами операции; 817.1.2. 3. Интерфейс, реализация и представление контейнеров — различные понятия. Не путайте их; 817.1.3. 4. Выполнять сортировку и поиск можно в соответствии с разными критериями; $ 17.1.4.1. 5.
Не пользуйтесь С-строками в качестве ключа, если вы не предоставили соответствующего критерия сравнения; 817.1.4.1. 6. Вы можете определить критерий сравнения так, чтобы эквивалентные, хотя и различающиеся значения ключей, отображались в один и тот же ключ; ~ 17.1.4.1. 7. При вставке или удалении элементов предпочитайте операции на конце контейнера (Ьасй-операции) 817.1.4.1.
8. Если нужно выполнять много вставок и удалений в голове или середине контейнера, предпочитайте (Ьт, 817.2.2. 9. Используйте тар или ти(итар, когда обращение к элементам выполняется главным образом по ключу; 917.4.1. 10. Для достижения максимальной гибкости используйте минимальный набор операций; 817.1.1. 11. Если элементы должны быть упорядочены, выбирайте тар, а не йазй тар; 517.6.1. 12. Когда важна скорость поиска, выбирайте йазй тар, а не тар; 817.6.1. 13. Если для элементов невозможно определить операцию <, выбирайте йазй тар, а не тар; 817.6.1.
14. Для проверки наличия ключа в ассоциативном контейнере применяйте функцию гтиИ(); 817,4,1,6, 603 ! 7.8, Упражнения 15. Для нахождения всех элементов контейнера с заданным ключом применяйте функцию едиа1 галде ! ); 817.4 1.6. 16. Если нужно хранить несколько значений для одного ключа, применяйте ти(итар; 817.4.2. 17.
Когда сам ключ является единственным значением, которое нужно хранить, применяйте хег или тиЫзег, 817.4.3. 17.8. Упражнения Решение некоторых задач можно найти, посмотрев реализацию стандартной библиотеки. Сделайте себе полезное одолжение: не пытайтесь смотреть сторонний код до того, как вы сами попробовали решить задачу. 1. (*2.5) Изучите О-нотацию (817.1.2). Выполните измерения для операций стандартных контейнеров с целью определения числовых коэффициентов, вовлеченных в О-нотацию. 2.
(*2) Существуют телефонные номера, которые не умещаются в тип !оид. Напишите тип рйоие иитЬег и класс, предоставляющий набор полезных операций с контейнером телефонных номеров типа рйоие иитЬег. 3. (*2) Напишите программу, которая заносит разные слова в файл в алфавитном порядке. Создайте две версии: в первой из них слова есть последовательность символов, ограниченных пробельными символами, а во второй слова есть последовательность букв, ограниченных символами, не являющихся буквами. 4. (*2.5) Реализуйте простую версию карточной игры»Яо!!га(ге». 5. (*1.5) Реализуйте простой тест слов, выявляющий, являются лн они палиндромами (например, козак, ода, о~уо и т.д.). Также реализуйте простой тест целых чисел, выявляющий, являются ли эти числа палиндромами.
Затем реализуйте проверку на палиндромность уже целых предложений. Обобщите эти решения. б. (*1.5) Определите очередь (г!цеце), используя (только) два стека. 7. (*1.5) Определите стек, похожий на тип згас7г 817.3.1), но который не копирует нижележащий контейнер (на котором он базируется) и который допускает итерации по своим элементам. 8.
(*3) Понятия потока, задачи и процесса составляют основные понятия параллельного исполнения программ на вашем компьютере. Разберитесь подробнее в этих механизмах. Для предотвращения одновременного доступа двух задач к одной области памяти применяется блокировка. Реализуйте класс блокировки, опираясь на системный механизм блокировок на вашей машине. 9. (*2.5) Читайте даты из потока ввода, например, Рес85, Рес50, Хаи76 и т.д., а потом выведите их так, чтобы более поздние даты шли первыми. Формат дат должен состоять из трех символов под месяц, после чего следуют два символа под год.
Полагаем, что все годы относятся к одному веку. 604 Глава 17. Стандартные контейнеры 10. ("2.5) Обобщите входной формат для дат так, чтобы он включал даты типа Вес!905, !2/3/!990, 3! 6/200! и т.д. Переделайте упражнение 817.8[9[, чтобы оно соответствовало новому формату. 11. ("1.5) Используйте Ь!)хе!для печати двоичных значений некоторых чисел, например 1, -1, О, И и -И, а также максимально возможного положительного Ьяа 12. ('1.5) Используйте Ь!)хе!для хранения информации о том, кто в текущий день присутствует на занятиях.
Прочтите эти Ь!жег за 12 дней и определите, кто присутствовал всегда? Кто присутствовал не менее 8 дней? 13. (*1.5) Определите список указателей, который уничтожает объекты, адресуе- мые этими указателями, во время уничтожения самого списка или при удалении элемента из списка операцией генюке. 14. ("1.5) Располагая объектом типа згас7г, распечатайте по порядку его элементы (не изменяя содержимого самого стека). 15. ('2.5) Завершите шаблон Ьазй агар (817.6.1), то есть реализуйте функции 0ад () и е9иа! еааяе (), а также продумайте схему его тестирования.
Выявите хотя бы один тип ключа, для которого хэш-функция у типа Ьазй агар плохо подходит (так что требуется иная хэш-функция). 16. (*2.5) Реализуйте и оттестируйте работу некоторого списка, выполненного в духе стандартного типа !ма 17. (*2) Иногда бывает, что излишнее потребление списком !!зг памяти накладно. Напишите и оттестируйте работу односвязного списка, выполненного в духе стандартных контейнеров.
18. (*2.5) Реализуйте список, похожий на стандартный !мг, но дополнительно поддерживающий индексацию. Сравните стоимость индексации списков и стоимость индексации для стандартного вектора (то есть типа тес!ос). 19. ('2) Реализуйте шаблонную функцию, которая выполняет слияние двух кон- тейнеров.
20. ('1.5) Располагая С-строкой, определите, не является ли она палиндромом. Определите, не является ли палиндромом ее начальная последовательность из хотя бы трех слов? 21. (*2) Прочтите последовательность пар (имя,значение) и сформируйте отсортированный список четверок (имя,сумма, среднее значение, медиана). Распечатайте этот список. 22. (*2.5) Определите расход памяти под стандартные контейнеры на вашей системе. 23. (*3.5) Рассмотрите вопрос об оптимальной стратегии реализации Ьазй тиар, требующей минимального расхода памяти под такой ассоциативный контейнер. Затем рассмотрите вопрос об оптимальной стратегии реализации Ьазй тар, достигающей минимального времени поиска. В обоих случаях решите, какими операциями пренебречь ради приближения к идеалу.
Подсказка: имеется огромная литература, посвященная хэшированию. 24. (*2) Разработайте такую стратегию обработки переполнения в Ьазй ятар (слишком высокая кучность хэшей для разных значений), при которой реализация е9иа! галде() была бы тривиальной. 17.8. Упражнения 605 25. (*2.5) Оцените затраты памяти под йазй тар, а затем измерьте эти затраты. Сравните оценку с результатом измерений. 26. (*2.5) Постарайтесь выявить, где сосредоточены основные временные затра ты в вашем йазй тар, и каковы они. Сравните эти результаты с аналогичны- ми результатами для стандартного тар, а также для какого-либо иного йазй тар. 27. (*2.5) Реализуйте йазй тар, основанный на вессог<тар<2(, !>*>, так, чтобы каждый тар содержал все ключи с одинаковым хэш-значением.
28. (*3) Реализуйте йазй ивар, используя Бр!ау-деревья (см. 1). Б!еа!ог, с<.Е. Таг)ап, Без-Аоуизс!п8 В!по«у Яеагсй Тгеез, )АБМ, Чо!. 32, !985). 29. (*2) Дана структура данных, описываюшая строкоподобную сушностгк Создайте 1000 объектов типа Бс и используйте их в качестве ключей для йазй тар. Измерьте производительность такого йазй тар. Напишите хэш-функцию (Назй; 817.6.2.3) специально для ключей Яс. 30. (*2) Приведите четыре разных способа удаления из йазй тар «стертых» (егазес)) элементов. Используйте стандартный библиотечный алгоритм (83.8, глава 18) во избежание явного цикла. 31. (*3) Реализуйте йазй тар с немедленным удалением элементов.
32. (*2) Хэш-функции, рассмотренные в 817.6.2.3, не всегда используют полное представление ключа. Когда часть представления игнорируется? Приведите пример, когда бывает разумным игнорировать часть ключа и напишите соот- ветствующую хэш-функцию. 33. (*2.5) Код хэш-функций имеет обыкновение следовать общей схеме — в цик ле получают новые данные и хэшируют их. Определите Назй (817.6.2.3), кото- рый получает данные повторяющимся вызовом функции, которую пользова- тель предоставляет для каждого типа ключа.
Например: сдге сгез = Ос сгййе (сдге с в=йазй ) lсеу) ) «ез= (гез«3) "гс Здесь пользователь может определить йазй (К> для каждого типа лТ, подлежа- шего хэшированию. 34. (*3) Имеется некоторая реализация йазй тар. Реализуйте йазсс ти1йтар йазй зес и йазй тиспзек 35. (*2.5) Напишите хэш-функцию, предназначенную для отображения равно- мерно распределенных целых значений в таблицу хэш-значений размером около 1024. Исходя из такой функции, придумайте набор из 1024 ключей, ка- ждый из которых отображается в одно и то же значение.
за асс Бс ! йсс зсгес сйаг Суре !пс(!саго«; сйог* Ьиг) Бс(сопя« сйаг* р) с йуказывоет но иге символов й выделяет память под буфер и заполняет его Алгоритмы и классы функциональных объектов Формальность освобождает. — Популярная поговорка инженеров Введение — обзор стандартных алгоритмов — последовательности — функциональные объекты — предикаты — арифметические функциональные объекты— связывающие адаптеры — адаптирование функций-членов — алгоритм уог енса — поиск элементов — свинг — сравнение последовательностей — алгоритмы поиска — копирование — гган4огт — замещение и удаление элементов— заполнение последовательности — изменение порядка — вмар — сортированные последовательности — Ынагу веагса — тегде — операции над множествами— ппн и тах — кучи — перестановки — алгоритмы в С-стиле — советы — упражнения.
18.1. Введение Контейнеры сами по себе не столь интересны. По настоящему полезными они становятся тогда, когда снабжаются операциями определения размера, итерирования, сортировки и поиска элементов. Стандартная библиотека предоставляет алгоритмы для решения большинства из наиболее распространенных задач,необходимых пользователям контейнеров. Данный раздел резюмирует стандартные алгоритмы; в нем приводится несколько примеров их использования, объясняются ключевые принципы и методы реализации алгоритмов на языке С++, а также подробно рассматривается ряд важнейших алгоритмов. Функциональные объекты (бзпсгюп оЬЗесгз) обеспечивают механизм, с помощью которого пользователь может приспособить стандартный алгоритм под свои нужды.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
