Бьерн Страуструп. Язык программирования С++. Специальное издание (2011) (1004033), страница 115
Текст из файла (страница 115)
Организуйте этот набор итераторов так, чтобы пользователь мог взаимозаменяемо использовать итераторы, обеспечиваю- щие достаточную для алгоритма функциональность. Минимизируйте повто- рение кода при реализации этих контейнеров. Какие еше типы итераторов 1 б.5. Упражнения 553 могут потребоваться пользователю? Перечислите достоинства и недостатки вашего подхода. 9. (*2) Завершите классы Солта!пег, Гасгог и ХЫ из $16.2.2. 10. (*2.5) Сгенерируйте 10000 однородно распределенных на интервале от 0 до 1023 чисел и сохраните их в; а) стандартном библиотечном контейнере гесгог; Ь) контейнере Гесгог из В16.5 [7[; с) контейнере Гесгог из В16.5[9[.
Во всех случаях вычислите среднее арифметическое элементов контейнеров. Засеките время. Оцените, измерьте и сравните мелсду собой объемы потребления памяти для трех этих стилей вектора. 11. (*1.5) Напишите такой итератор, чтобы )'есгог из в16.2.2 мог использоваться в стиле контейнера из 516.2.1. 12.
('1.5) Напишите класс, производный от Солта!пег так, чтобы [естог из в16.2.1 мог использоваться в стиле контейнера из 516.2.2. 13. (*2) Напишите такие классы, чтобы [гесгог из В16.2.1 и гесгог из В16.2.2 могли использоваться как стандартные контейнеры. 14. (*2) Напишите шаблон, реализующий контейнер с теми же функциями-членами и теми же типами, что и стандартный гесгог, лля существующего (нестандартного) контейнерного типа. Не модифицируйте при этом существующий контейнерный тип. Как вы поступите с его функциональностью, не совпадающей со стандартной? 15. (*1.5) Кратко опишите возможное поведение функции 0пр!(саге е!степы() из В!6.3.6 для гесгог<згг!па, состоящего из трех элементов: 0оп ' г 0о гй!з (не делай этого).
Стандартные контейнеры Теперь самое время поставить вашу работу на прочный теоретический фундамент. — Сзм Морган Стандартные контейнеры — обзор операций и контейнеров — эффективность— внутреннее представление — требования к элементам контейнеров — последовательные контейнеры — гесгог — Им — йехие — адаптеры — стек — очереди— очереди с приоритетами — ассоциативные контейнеры — ассоциативные массивы — сравнения — контейнеры ти1птар — контейнеры вег — контейнеры ти!пвег — «почти контейнеры» — битовые поля Ь)жег — встроенные массивы— хэш-таблицы — реализация Ьавй тар — советы — упражнения.
17.1. Стандартные контейнеры В стандартной библиотеке определяются два вида контейнеров — посеедовательные контейнеры (зеаиепсез) и ассоциативные контейнеры (атос)абае сопгатегв). Все последовательные контейнеры похожи на гесгог (016.3). Если не сказано обратное, типы и функции, упоминавшиеся в связи с векторами, могут с тем же успехом использоваться и для других последовательных контейнеров. В то же время ассоциативные контейнеры дополнительно обеспечивают доступ к своим элементам на основе ключей (ф3.7.4). Встроенные массивы (Ь5.2), объекты типа вйчпя (глава 20) и га!аггау (Ь22.4), а также битовые поля Ь~гвег 617.5.3) содержат элементы, и тоже могут трактоваться как контейнеры. Однако они не являются в точном архитектурном смысле стандартными контейнерами.
Если бы это было так, то они не удовлетворяли бы своему первичному (главному) предназначению. Например, встроенные массивы содержали бы в таком случае свой размер, а это препятствовало бы их совместимости со встроенными массивами языка С, Ключевая идея стандартных контейнеров состоит в их взаимозаменяемости в тех случаях, где это имеет смысл. Пользователь может выбирать между ними на Глава 17. Стандартные контейнеры 556 основе вопросов эффективности и наличия специализированных операций. Например, если в задаче часто требуется поиск по ключу, то стоит применить ассоциативный контейнер саар (817.4.!). С другой стороны, если преобладают типичные для списков операции, то стоит применить!1вс (817.2.2).
Если большая часть вставок и удалений элементов осуществляется на концах контейнера, то лучше всего подойдут с(еаие (двусторонняя очередь, 817.2.3), йсас1с (стек, 817.3.1) или аиеие (очередь, 817.3.2). Кроме того, пользователь может построить свой собственный контейнер в согласии с архитектурой и приемами построения стандартных контейнеров (817.6).
По умолчанию, в этом случае лучше использовать гессог (516.3), ибо он реализован столь универсально, что его можно применять в самых разных контекстах. Идея унифицированной работы с разными типами контейнеров (в более общем контексте — с различными источниками информации) приводит к понятию обобщенного программирования (82.7.2, 83.8). Для поддержки этой идеи стандартная библиотека содержит множество обобщенных алгоритмов (глава 18), которые позволяют программисту абстрагироваться от конкретных деталей индивидуальных контейнеров. 17.1.1. Обзор контейнерных операций В этом разделе перечислены почти все общие для стандартных контейнеров типы, итераторы, функции доступа и другие операции.
За большими подробностями обращайтесь к стандартным заголовочным файлам (<гессе«>, <11тс>, <псар> и др.; см. 516.1.2). Типы ($16.3.1) Тип элемента Тип аллокатора Тип индексов, счетчиков и т д ассе суре Тип разности итераторов с(фегепсе суре Ведет себя подобно га1ие фре* Йегасог Ведет себя подобно сопйт га1ие суре* сопи ссегасог Рассматривает контейнер в обратном порядке, как хасае суре* гегегзе йегагог сопес гегегзе де«итог Рассматривает контейнер в обратном порядке, каксоптсиссие суре* ,' гс1егепсе хасае сурей сопзс хасае фрей сопзс «е~егепсе Тип ключа (для ассоциативных контейнеров) ссеу фре Тип псарреИ хасае (для ассоциативных контеинеров) псарресс суре Тип критерия сравнения (для ассоциативных контейнеров) сссу соспраге Контейнер можно последовательно просмотреть в определенном порядке с помощью его типа йегасог, или в обратном порядке (с помощью обратных итерато- 17.1.
Стандартные контейнеры 557 ров). Для ассоциативных контейнеров порядок просмотра основывается на его кри- терии сравнения (по умолчанию это <); Итераторы ($16.3.2) Ьедт () Указывает на первый элемент Указывает на элемент, следующий за последним еиа () Указывает на первый элемент обратной последовательности гЬедти ( ) Указывает на элемент, следующий за последним в обратной последовательности гела' ( ) К некоторым элементам возможен прямой доступ: Контейнеры предоставляют операции, типичные для списков: Операции со списками (616.3.6) добавить х перед р Ьмегт (р, х) добавить и копий х перед р (изет( (р, и, х) тзегт(р,у)гзт,!азт) Добавить элементы из (утгзт: !ам [ передр Удалить элемент в позиции р егазе (р) Удалить элементы (7(гзт:(азт( егазе (утгзт, !азт) е(еаг ( ) Удалить все элементы Векторы и двусторонние очереди обеспечивают эффективные операции в конце последовательности своих элементов.
Кроме того, списки и двусторонние очереди обеспечивают эффективные операции в начале последовательности своих элементов. Глава 17. Стандартные контейнеры 558 В приложении Е обсуждается поведение контейнеров в случае, когда операции аллокаторов или операции над элементами генерируют исключения. Контейнеры предоставляют операции получения числа элементов и некоторые другие операции: егге ( ) Число элементов еицну ( ) , 'Контейнер пуст? Размер максимально возможного контейнера тах е1ге() сарас11у() Память, выделенная под гесгог гезегяе ( ) гез(ее ( ) Обмен элементами у двух контейнеров опар () лет адосатог () , 'Предоставляет копию контейнерного аллокатора < ( Один контейнер лексикографически предшествует второму? Контейнеры реализуют множественные варианты конструкторов и операций присваивания: Конструкторы и тд.
($16З.4) , Пустой контейнер сои)а)пег ( ) соитагиег (и) и элементов с умолчательными значениями (не для ассоциативных контейнеров) соптагиег ( и,х ) Уничтожить контейнер и все его элементы -сопгатег ( ) соиапиег (ттгзт, гатт) , сопта1иег (х) Другие операции (816З.8, $16З.9, $16З.10,) ~ Резервирует память для потенциальных расширений (только для ~ контейнера гестас) , 'Изменяет размер контейнера (для гесгог, Ж и йеаие) и копий х (не для ассоциативных контейнеров) Инициализируется элементами из (Г)гзсгазг( Копирующий конструктор (инициализируется элементами из х) 17.1. Стандартные контейнеры 559 Ассоциативные контейнеры обеспечивают поиск на основе ключей: Операции ассоциативных контейнеров (917.4.1) Доступ к элементу с ключом Ь (для контейнеров с уникальными ключами] орега1ог[] (й) Найти элемент с ключом Ф 71 И(Ь] Найти первый элемент с ключом Ь 1оиег ЬоиИ(Ь) Найти первый элемент с ключом, большим Ь иррег Ьоиий(Ь) Найти 1отгег Ьоиит( и иррег Ьоииту для элемента с ключом Ь едио1 гаще (Ь] Копия объекта сравнения ключей Йеу соер(] Копия объекта сравнения гиарреИ гауие га(ие сотар () Кроме этих общих операций большинство контейнеров предоставляют также и специализированные операции.
17.1.2. Краткий обзор контейнеров Приведем краткую сводную информацию по стандартным контейнерам в следующей табличной форме: Операции стандартных контейнеров Итераторы 051 Ргоп1 операции операции 9 19.2.1 0(п)ч- йап СОП51+ СОП51 геетог В[ 1151 СОП51 соп51 СОП51 0(п) СОП51 СОП51 йап Иеаие СОП51 СОП51 отиса СОП51 СОП51 Еиеие Обо9(п)) 0((о9(пИ рпогйу аиеие жар Ойо9(п)) В( Ойо9(пИ+ ОДО9(п))+ [ В( гии(йтар ; Ойо9(пИ+ Ойо9(пИ+ В( 0(п)+ 0(п)+ СОП51 ( йап СОП51 йап СОП51 йап СОП51 Ьтуеет СОП51 та(т(еет ипиа аггау га(аггау 9 16.3.3 ' ф 1 7.4.1.3 9 16.3.6 9 20.3.9 ~ 1 7.2.2.2 9 20.3.9 Васк (51аск) операции 9 16.3.5 ф 20 3.12 Глава 17. Стандартные контейнеры 560 В колонке лгегагогв аббревиатура Вал означает итератор произвольного доступа, а В! — двунаправленный итератор; операции с двунаправленными итераторами являются подмножеством операций с итераторами произвольного доступа (й19.2.1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
