Б. Страуструп - Язык программирования С++. Специальное издание, 3-изд. Бином. 2004 (1160791), страница 115
Текст из файла (страница 115)
Кроме того списки и очереди с двумя концами обеспечивают такие же операции в начале (1гопг) своей последовательности, Операции со стеком и очередями (й 16.3.5, й 17.2.2.2) рияЬ Ьасй(] рор Ьасй(] рияЬ )гоп1() Добавление в конец Удаление последнего элемента Добавление нового первого элемента (только для списков и очередей с двумя концами) Удаление первого элемента (только д.ля списков и очередей с двумя концами) рор ~гопг(] Контейнеры обеспечивают операции со списками: Операции со списками (ф 16.3. 6) 1пяегг (р, х) 1пяег1 (р, п, х] тяег1 (р, 1)гя1, 1аяг] егаяе (р] егаяе Ягя1, 1аяг) с1еаг (] Добавление х перед р Добавление и копий х перед р Добавление элементов из (1)гяп1аяг( перед р Удаление элемента в позиции р Удаление ( дгяг:1аяг( Удаление всех элементов Другие операции (й 16.3.8, й 16.3.9, ф 16.3.10) я1яе () етр1у (] тах я1ге() сарас11у () геяегпе () гея1хе () Висло элементов Контейнер пуст? Размер самого большого возможного контейнера Память, выделенная под вектор (только для векторов) Выделяет память под вектор (только для векторов) Изменяет размер контейнера (только для векторов, списков и очередей с двумя концами) Обмен местами элементов двух контейнеров Получает копию контейнерного распределителя памяти Содержимое двух контейнеров совпадает? Содержимое двух контейнеров различается? Один контейнер лексикографическн меньше другого? яшар (] уе1 айосатог () В приложении Д обсуждается поведение коттейнера, если выделение лама~и или операция над элементами генерирует исключение.
Все контейнеры обеспечивают операпни, связанные с получением информации о числе элементов, и несколько других опсраций; Глава 17. Стандартные контейнеры 522 Контейнеры обеспе твают множество разных конструкторов и операций присваивания: Конструкторы и пр. (ф 16.3.4) соп1атег () соп1атег (и) Пустой контейнер и элементов со значением по умолчанию (не для ассоциативных контейнеров) п копий х (не для ассоциативных контейнеров) Инициализирует элементы из фгз1:1аз1[ Копирующий конструктор; инипиализирует элементами из контейнерах Уничтожает контейнер и все его элементы соп1а1пег (и, х) соп1атег (йгз1, 1аз1) соп1аспег(х) -соп1атег () Присваивания (9 16.3.4) Копирующее присваивание; берутся элементы из контейнера х Присваивание и копий х (це д,ля ассоциативных контейнеров) Присваивание из [)сгз1:1аз1[ орега1ог= (х) озяб (п, х) алям (1фсгз1, 1аз1) Ассоциативные контейнеры обеспечивают поиск элементов по ключам: Ассоциативные операции (9 17.4.1) орега1ог[) (Й) Доступ к элементу с ключом Й (для контейнеров с уникальным ключам) Находи~ элемент с клк>чом Й Находит первый элемент с ключом Й Находит первый элемент с ключом больше Й Находит 1ошег Ьоипс( (нижнюю границу) и иррег Ьоипс( (верхнюю границу) элементов с ключом Й Копирует объект с совпавгпим к.лючом Копирует объект с совпавшим таррес( эа1ие (отображенным значением) Япс( (Й) 1ошег Ьоипс1 (Й) иррег Ьоипс( (Й) ес)иа1 гапуе(Й) Йеу сотр() оа1ие соспр () 17.1.2.
Краткий обзор контейнеров Станлартные контейнеры вкратце можно описать примерно так: Стандартные операции с контейнерами Ц Операции Операции Операции Итераторы со списками с началом с концом (стековые) ф 16.3.3 9 16.3.6 6 17.2.2.2 9 16.3.5 ч 19.2.1 917А.1.3 ф 20.3.9 ф 20.3.9 ф 20.3.12 0(п)+ сопят 0(п) оес1ог 11з1 с(ение Кап В( Кап сопле+ сопле сопят сопзг сопле сопзс сопзг В дополнение к этим распространенным операциям больптнство контейнеров обес- печивает несколько специализированных операций. 523 17.1.
Стандартные контейнеры Стандартные операции с контейнерами бпродоллсвнив) Ц Операции Операции Операции Итераторы со списками с началом с концом (стековые) 9 16.3.3 9 16.3.6 9 17.2.2.2 з 16.3.5 з 19.2.1 9 1'? А.1.3 9 20.3.9 9 20З.9 9 203.12 в(асй г?иене рпоп1у г?иеие 0(п) сонат+ О(п) сопят сопзт« О(!оя(п)) 0(!оя(п)) О(!оя(п)) тар О(!оЯ(п)) 0(!о6(п))+ В( ти?1?тар 0(!оя(п))+ В! ввг 0(!ой(п)) 0(!о6(п))+ В1 ти?1?ве1 О(!ои(ц))+ В! в1п'пд агтау оа1аггау Ь11ве1 0(п)+ 0(п)+ сопят+ Кап Кап Йап сопзг сонат сопзг сопзс В столбце Итвраторы Рап означает итератор с произвольным доступом, а В1 — двунаправленный итератор; операции для двунаправленных итераторов представляют собой подмножество операций для нтераторов с произвольным доступом Ц 19.2.1). Записи в других ячейках — это степень эффективности операций.
Запись сола( означает, что операция занимает время, которое не зависит от числа элементов в контейнере. Другое принятое обозначение для постоянного времени — О (1!. О (и! означает, что время пропорционально числу участвующих в операции элементов. Суффикс+ показывает, что иногда операция может оказаться более дорогой. Например, вставка элемента в список имеет фиксированную стоимость (эта операция отмечена сопв1), в то время как та же операция с вектором приводит к перемещению всех элементов после места вставки (для вектора эта операция отмечена как О (и!).
Иногда нужно переместить все элементы (поэтому я добавил +). «Большое О» — общепринятая запись. Я добавил + для программистов, заботящихся кроме среднего быстродействия еще и о предсказуемости. Общепринятый термин для О (и)+ — э го амортизироваянов линейное время. Естественно, если число элементов невелико, то постоянное время может оказаться больше, чем О (и!. Однако для больших структур данных сопвг может считаться «дешево», О (и! — «дорого», а О (1од (гг() — «довольно дешево».
Даже для умеренно больших значений п время О (1од'(и!) ближе к константе, чсги к О (л!. Те, кого заботит цена, должны присмотреться к э гому повнимательнее. В частности, вы должны понять, какие элементы учитываются в п. Никакая базовая операция не бывает «слишком дорогой», то есть О (и"и! илн хуже. Не с гптая в(г?пд, перечисленные оценки стоимости отражают требования к стандарту. Опенки для в1ппу — это мои допущения. Данные для е(асй и !?иеие отражают стоимость реализации по умолчанию с использованием г(ение (9 17.3.1, 9 17.3.2).
Приведенные опенки сложности и цены являются оценками сверху. Они существуют для того, чтобы дать пользователям какую-то ориентацию в том, что можно ожидать от реализации операций, Естественно, в важных случаях разработчики библиотеки постараются реализовать функции получше. 524 Глава 17, Стандартные контейнеры 17.1.3. Представление Стандарт не предписывает специального представления для каждого стандартного контейнера, Вместо этого он определяет интерфейсы контейнеров и некоторые требования к сложности. Чтобы удовлетворить общим требованиям, разработчики библиотеки выберут подходящие и часто тщательно оптимизированные реачнзации. Контейнер почти наверняка будет представлен структурой данных, содержащей элементы, доступ к которым осуществляется через дескриптор, содержащий информацию о разме1ю и емкости.
Для векторов структура элементов данных является непрерывной последователыюстью этих элементов и очень напоминает массив: элементы дополнительное пространство,' Лналогичпо, список наилучшим образом представляется набором связей, указывающих на элементы; гер элементы: Д вЂ” Д Ц Лссоциативпый массив скорее всего реализуется как (сбалансированное) дерево узлов, указывающих на пары (ключ, значение): гпар: гер -н ~~узел ~узел~ пары (ключ, значение): Строки можно реализовать, как описано в ~ 11.12, или, например, как последователь- ность массивов, каждый из которых содержит не слишком много символов: з1г1па: ~ гер строковые сегменты; ~ Здесь гер обозначает «представлениеа (гергезепгаг1оп). 17.1.4.
Требования к элементам Элементы в контейнере — это копии вставленных объектов. Таким образом, чтобы стать элементом контейнера, объект должен быть такого типа, который позволил бы реализации контейнера скопировать его. Контейнер может копировать элементы при помощи копирую1цего конструктора илн присваивания; в обоих случаях получающаяся копия 525 17.1. Стандартные контейнеры должна быть эквивалентным объектом.
Грубо говоря, зто означает, что любая придуманная вами проверка значений объектов на равенство должна считать копию равной оригиналу. Другими словами, копирование элемента должно работать очень похоже на обычное копирование для встроенных типов (включая указатели). Например; Х< Хаорегагог= (соне! Х8 а) // правильный оператор присваивания ( // копировпние всех членов а в *г!из ге!игп "!!г!з; делает Х подходящим для типа элемента в стандартном контейнере, но пои! Уаорегазог= (сопя! УЬ а) О неправильный оператор присваивания ( //обнуление всех членови ) обрабатывает Унеправильным образом, потому что присваивапие Уне имеет ни принятого возврагцаемого типа, ни традипионного смысла. Некоторые нарушения правил для стандартных контейнеров могу~ быть выявлены компилятором, но другие не выявляются и могут привестн к неожиданностям в поведении программы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
