Б. Страуструп - Язык программирования С++. Специальное издание, 3-изд. Бином. 2004 (1160791), страница 114
Текст из файла (страница 114)
[18] При необходимости пользуитесь геяегве(), чтобы сделать быстродействие предсказуемым; 9' 16.3.8. 16.5. Упражнения Решение некоторых задач к этой главе можно найти. просмотрев исходньгй текст реализации стандартной библиотеки. Сделайте одолжение — попытайтесь найти собственные решения, прежде чем смотреть, как подошел' к этим проблемам разработчик вашей библиотеки. 1.
(*1.5) Создайте эес1ог<сйаг, содержащий буквы в алфавитном порядке. Распечатайте элементы этого вектора в прямом и в обратном порядке. 2. (*1.5) Создайте эес1ог<ягЯгшй> н считайте в него список названий фруктов из сш. Отсортируйте список и распечатайте. 3. ('1.5) Используя вектор из 9 16.5[2], напишите цикл распечатки названий фруктов, начинающихся на букву а. чс ('1) Используя вектор из 9 16.5[2], напишите цикл, удаляющий все фрукты, названия которых начинаются на букву а. 5. (*1) Используя вектор из 9 16.5[2], напишите цикл, удаляющий все цитрусовые. 6.
('1.5) Используя вектор из 4 16.5[2], напишите цикл, удаляющий все фрукты, которые вы не любите. 7. ('2) Завершите классы Уес(ог,7хя1и7(огиз 6 16.2.1. 8. (*2.5) Взяв класс йог, подумайте, как обеспечить итераторы для перебора в возрастающем порядке, в убывающем порядке, для перебора контейнера, способного изменяться при итерации, и перебора неизменяющегося (1пшшгаЫе) контейнера. Организуйте этот набор нтераторов, так чтобы пользователь мог взаимозаменяемым образом использовать итераторы, обеспечивающие достаточную функциональность алгоритмов.
Мннимизируйте повторение фрагментов кода в реализации этих контейнеров. Какие еще итераторы могут понадобиться пользователю? Перечислите достоинства и недостатки вашего подхода. 9. ('2) Завершите классы Соп1ашег, Уес1ог и 7яя( из Э 16.2.2. 10. ('25) Сгенерируйте 10 000 равномерно распределенных случайных чисел в диапазоне от 0 до 1023 и сохраните их; а) в стандартном библиотечном контейнере вес(ог; б) в контейнере Уес1ог из 6 16.5[7]; в) в контейнере Уес(ог из 9 16.5[9]. Во всех случаях сосчитанте арифметическое среднее элементов вектора (как если бы вы его еще не знали). Засеките время.
Оцените, измерьте и сравните потребление памяти в этих трех стилях векторов. 11. (*1.5) Напишите итератор, чтобы Уес1ог из э 16.2.2 использовался как контейнер в стиле 9 16.2.1. 518 Глава 16. Организация библиотеки и контейнеры 12. ('1.5) Напишите класс, производный от Соп1а(пег, чтобы Уес1ог из Ч 16.2.1 использовался как контейнер в стиле з 16.2.2. 13. ('2) Напишите классы, чтобы Ъес1ог из 8 16.2.1 и 1гес1ог из ~ 16.2.2 использовались как стандартные контейнеры.
14. ("2) Напишите шаблон, реализующий контейнер с теми же функциями-членами и типами членов, как н стандартный оес1ог, для существующего (нестандартного, неучебного) контейнерного типа. Не модифьщируььте уже суьцествуюпьий контейнерный тип. Как бы вы стали работать с функциональностью, предлагаемой нестандартным оес1ог, но не предоставляемой стандартным? 15, (*1.5ь) Вкратце обрисуйте возможное поведсние функции 11ир11са1е е1етеп1з ~~ нз 6 16.3.6 для иес1ог<з1г(пй>, состояьцего из трех злементов: с(оп'1 ь(о 1й1з (не делай этОГО).
Стандартные контейнеры Твлврь силов время поставить вату работу на твердый теорел|ический фундамент. — Сэм Моргая Стандартные контейнеры — обзор операций и контейнеров — эффективность— представление — требования к элементам — последовательности .. вектора— списки †очере с двумя концами — адаптеры — стек — очереди — очереди с приоритетами — ассоциативные контейнеры — ассоциативные массивы— сравнения — контейнеры ти111тар — множества — множества с дублированием элементов — «почти контейнеры» -- битовые наборы — массивы — хэш-таблицы— реализация Лаял тир — советы — упражнения.
17Л. Стандартные контейнеры В стандартной библиотеке определены два типа контейнеров — последовательности и ассоциативные контейнеры. Все последовательности очень похожи на иес1ог (й 16.3). Если не сказано обратное, типы членов и функции, упоминавшиеся для векторов, могут с тем же эффектом использоваться и для любого другого контейнера. Но ассоциативные контейнеры дополнительно предоставляют доступ к элементам на основе ключей (6 3.7А).
Встроенные массивы Я 5 2), строки в(кйги(глава 20), па1аггау Я 22Л) и битовые наборы Ь11ве1Я 17.5.3) содержат элементы, а следовательно могут считаться контей- ' нерами. Однако эти типы не являются полностью разработанными стандартными контейнерами. Если бы они являлись таковыми, это помешало бы их основному предназначению. Например, встроенный массив не может одновременно содержать собственный размер и оставаться совместимым по размещению в памяти с массивами языка С.
Ключевая идея для стандартных контейнеров заключается в том, что когда это представляется разумным, онн должны быть логически взаимозаменяемыми, Пользователь может выбирать между ними, основываясь на соображениях эффективности и потребности в специализированных операциях. Например, если часто требуется поиск по ключу, можно воспользоваться тир (ассоцнативным массивом) (6 17.4.) ).
С другой стороны, если преобладают универсальные операции, характерные для списков, можно воспользоваться контейнером 11в1 Я 17.2.2). Если добавления и удаления элементов часто производятся в концы контейнера, следует подумать об использовании г(ег)ие (очереди с двумя концами, 6 17.2.3), в1ас(г (стека, ~ 17.3.1) или диене (оче- Глава 17.
Стандартные контейнеры 520 17.1.1. Обзор операций В этом разделе перечислены общие и почти общие члены стандартных контейнеров. Если хотите узнать подробности, прочитайте заголовочные файлы вашей стандарт- ной библиотеки (<пес1ог>, <Дз1>, <шар> и т, д.; 6 16.1.2). Типы членов (й!6.3.1) па)ие (уре а((оса(ог (уре зьве 1уре д1фегелсе 1уре 1гегагог солз1 (1ега1ог гепегзе 1(ега(ог Тип элемента Тип распределителя памяти Тип индексов, счетчика элементов и т. п. Тип разности между итераторамн Ведет себя подобно ва(ие 1уре* Ведет себя подобно соля( па1ие (уре* Просматривает контейнер в обратном порядке; как па1ие 1уре* Просматривает контейнер в обратном порядке; как солз1 иа1ие 1уре* Ведет себя подобно ва(ие (уре8 Ведет себя подобно соля( иа!ие (урей Тип ключа (только для ассоциативных контейнеров) Тип таррег( па1ие (отображенного значения); только для ассоциативных контейнеров Тип критерия сравнения (только для ассоциативных контейнеров) соля( гевегзе Йега1ог ге7егелсе солз1 геуегелсе Йеу гуре гларреа 1уре леу сотри~ е Контейнер может быть последовательно просмотрен илн в порядке, определяемом его итератором, или в обратном порядке.
Для ассоциативного контейнера порядок основывается на его (контейнера) критерии сравнения (по умолчанию это <). Итераторы (й 16.3.2) Ьеу(л Ц ела 11 гЬеу(л 1] Указывает на первый элемент Указывает на элемент, следующий за последним Указывает на первый элемент в обратной последовательности Указывает на элемент, следующий за последним, в обратной последовательности. ген 1) реди, 6 17.3.2).
Кроме того, пользователь может разработать дополнительные контейнеры, вписывающиеся в рамки стандартных контейнеров Я 17.6). По умолчанию должен использоваться еес1ог Я 16.3); он реализован, чтобы хорошо работать для самого широкого диапазона задач. Идея обращения с различными видами контейнеров — и в более общем случае со всеми видами источников информации — унифицированным способом, ведет к понятию обобщенного (йепег|с) программирования (6 2 7,2, 8 3.8).
Для поддержки этой идеи стандартная библиотека содержит множество обобщенных алгоритмов (глава 18). Такие алгоритмы избавляют программиста от необходимости знать подробности отдельных контейнеров. 521 17.1. Стандартные контейнеры К некоторым алементам можно обратиться прямо: Доступ к элементам (ф 16.3.3) Ггопг (] Ьасй () П а1() Первый элемент Последний элемент Обращение по индексу, доступ без проверки (не для списка) Обращение по индексу, доступ с проверкой (не для списка) Векторы и очереди с двумя концами обеспечивают эффективные операции с конном (Ьаск) своей последовательности элементов.