Что такое контейнер в с

Урок №197. Контейнеры STL

Безусловно, наиболее часто используемым функционалом библиотеки STL являются контейнерные классы (или как их еще называют — «контейнеры»). Библиотека STL содержит много разных контейнерных классов, которые можно использовать в разных ситуациях. Если говорить в общем, то контейнеры STL делятся на три основные категории:

Сейчас сделаем их краткий обзор.

Последовательные контейнеры

Последовательные контейнеры (или «контейнеры последовательности») — это контейнерные классы, элементы которых находятся в последовательности. Их определяющей характеристикой является то, что вы можете добавить свой элемент в любое место контейнера. Наиболее распространенным примером последовательного контейнера является массив: при добавлении 4 элементов в массив, эти элементы будут находиться (в массиве) в точно таком же порядке, в котором вы их добавили.

Начиная с C++11, STL содержит 6 контейнеров последовательности:

Класс vector (или просто «вектор») — это динамический массив, способный увеличиваться по мере необходимости для содержания всех своих элементов. Класс vector обеспечивает произвольный доступ к своим элементам через оператор индексации [] , а также поддерживает добавление и удаление элементов.

В следующей программе мы добавляем 5 целых чисел в вектор и с помощью перегруженного оператора индексации [] получаем к ним доступ для их последующего вывода:

Результат выполнения программы:

Класс deque (или просто «дек») — это двусторонняя очередь, реализованная в виде динамического массива, который может расти с обоих концов. Например:

Результат выполнения программы:

7 8 9 10 0 1 2 3

List (или просто «список») — это двусвязный список, каждый элемент которого содержит 2 указателя: один указывает на следующий элемент списка, а другой — на предыдущий элемент списка. List предоставляет доступ только к началу и к концу списка — произвольный доступ запрещен. Если вы хотите найти значение где-то в середине, то вы должны начать с одного конца и перебирать каждый элемент списка до тех пор, пока не найдете то, что ищете. Преимуществом двусвязного списка является то, что добавление элементов происходит очень быстро, если вы, конечно, знаете, куда хотите добавлять. Обычно для перебора элементов двусвязного списка используются итераторы.

Хотя о классе string (и wstring) обычно не говорят, как о последовательном контейнере, но он, по сути, таковым является, поскольку его можно рассматривать как вектор с элементами типа char (или wchar).

Ассоциативные контейнеры

Ассоциативные контейнеры — это контейнерные классы, которые автоматически сортируют все свои элементы (в том числе и те, которые добавляете вы). По умолчанию ассоциативные контейнеры выполняют сортировку элементов, используя оператор сравнения < .

set — это контейнер, в котором хранятся только уникальные элементы, и повторения запрещены. Элементы сортируются в соответствии с их значениями.

multiset — это set, но в котором допускаются повторяющиеся элементы.

map (или «ассоциативный массив») — это set, в котором каждый элемент является парой «ключ-значение». «Ключ» используется для сортировки и индексации данных и должен быть уникальным, а «значение» — это фактические данные.

multimap (или «словарь») — это map, который допускает дублирование ключей. Все ключи отсортированы в порядке возрастания, и вы можете посмотреть значение по ключу.

Адаптеры

Адаптеры — это специальные предопределенные контейнерные классы, которые адаптированы для выполнения конкретных заданий. Самое интересное заключается в том, что вы сами можете выбрать, какой последовательный контейнер должен использовать адаптер.

stack (стек) — это контейнерный класс, элементы которого работают по принципу LIFO (англ. «Last In, First Out» = «последним пришел, первым ушел»), т.е. элементы добавляются (вносятся) в конец контейнера и удаляются (выталкиваются) оттуда же (из конца контейнера). Обычно в стеках используется deque в качестве последовательного контейнера по умолчанию (что немного странно, поскольку vector был бы более подходящим вариантом), но вы также можете использовать vector или list.

queue (очередь) — это контейнерный класс, элементы которого работают по принципу FIFO (англ. «First In, First Out» = «первым пришел, первым ушел»), т.е. элементы добавляются (вносятся) в конец контейнера, но удаляются (выталкиваются) из начала контейнера. По умолчанию в очереди используется deque в качестве последовательного контейнера, но также может использоваться и list.

priority_queue (очередь с приоритетом) — это тип очереди, в которой все элементы отсортированы (с помощью оператора сравнения < ). При добавлении элемента, он автоматически сортируется. Элемент с наивысшим приоритетом (самый большой элемент) находится в самом начале очереди с приоритетом, также, как и удаление элементов выполняется с самого начала очереди с приоритетом.

Снова про STL: контейнеры

В предыдущей заметке речь шла о массивах как прототипе и прародителе контейнеров. Теперь дошла очередь до собственно контейнерных классов и поддерживающих их библиотек.

Под термином библиотека стандартных шаблонов (STL, Standard Template Library) понимают набор интерфейсов и компонентов, первоначально разработанных Александром Степановым, Менг Ли и другими сотрудниками AT&T Bell Laboratories и Hewlett-Packard Research Laboratories в начале 90-х годов (хотя и позже ещё весьма многие приложили руку к тому, что стало на сегодня стандартным компонентом C++). Далее библиотека STL перешла в собственность компании SGI, а также была включена как компонент в набор библиотек Boost. И наконец библиотека STL вошла в стандарты C++ 1998 и 2003 годов (ISO/IEC 14882:1998 и ISO/IEC 14882:2003) и с тех пор считается одной из составных частей стандартной библиотек C++.

Стандарт не называет эту часть библиотеки STL, но эту хронологию хорошо бы учитывать, разбираясь с какой версией компилятора, языка и литературы вы имеете дело — в процессе сокращения HP STL до размеров, подходящих для стандартизации, часть алгоритмов и функторов выпали из состава библиотеки, а кое-что, со временем, и добавляется (например, расширение набора переопределенных прототипов некоторых методов контейнеров). По тексту будет использоваться традиционное название STL только чтобы было ясно какую часть стандартной библиотеки C++ мы имеем в виду.

Первоначальной целью STL (это хорошо видно из хронологии комментариев в заголовочных файлах) было создание боле гибкой модели регулярных контейнеров по сравнению с массивами и обобщение на них некоторых широко используемых алгоритмов (таких как поиск, сортировка и некоторых других). Но затея оказалась плодотворнее первоначальных намерений, и была существенно расширена. STL вводит ряд понятий и структур данных, которые почти во всех случаях позволяют сильно упростить программный код. Вводятся следующие категории понятий:

Контейнер — способ хранения набора объектов в памяти.
Итератор — средство доступа к содержимому отдельных объектов в контейнере.
Алгоритм — определение наиболее стандартных вычислительных процедур на контейнерах.
Адаптер — адаптация основны категорий для обеспечения наиболее употребляемых интерфейсов (таких как стек или очередь).
Функтор (функциональный объект) — сокрытие функции в объекте для использования её другими категориями.

Центральным понятием STL, вокруг которого крутится всё остальное, это контейнер (ещё используют термин коллекция). Контейнер — это набор некоторого количества обязательно однотипных элементов, упакованных в контейнер определённым образом. Простейшим прототипом контейнера в классическом языке C++ является массив. Тот способ, которым элементы упаковываются в контейнер и определяет тип контейнера и особенности работы с элементами в таком контейнере. STL вводит целый ряд разнообразных типов контейнеров, основные из них:

последовательные контейнеры — вектор (vector), двусвязный список (list), дэк (deque);
ассоциативные контейнеры — множества (set и multiset ), хэш-таблицы (map и multimap);
псевдо контейнеры — битовые маски (bitset), строки (string и wstring), массивы (valarray);

Здесь видно достаточно интересное поведение вектора (в этом и его смысл): как только при добавлении очередного элемента вектора его ёмкости становится недостаточно для ещё одного элемента, делается новое размещение вектора, резервируя для него удвоенную ёмкость (с запасом, чтобы следующее же добавление нового элемента не потребовало тут же нового переразмещения).

Примечание: Показанное выше удвоение ёмкости вектора при переразмещении — это характерное поведение для реализации библиотек компилятора GCC. Но точный алгоритм резервирования ёмкости под будущие элементы стандарт оставляет на волю реализатора, поэтому на него нельзя рассчитывать, и описан он здесь только для качественного понимания картины (реализации Visual Studio ведут себя по-другому, резервируя только небольшой избыток… это вы изучите сами).

Отметим на дальнейшее, пока без комментариев, то важное обстоятельство, что операции помещения элементов в контейнер выполняет копирование элемента, что влечёт за собой а).требование наличия копирующего конструктора для типа элементов и б).для структурных элементов это может привести к заметным затратам производительности.

Таким образом мы получили эквивалент массива C++, размер которого (size()) динамически меняется в произвольных пределах от нескольких единиц до миллионов элементов. Обратим внимание (это очень важно), что увеличение размера вектора достигается ни в коем случае не индексацией за пределы его текущего размера, а «заталкиванием» (метод push_back()) нового элемента в конец вектора (симметрично, метод pop_back() выталкивает последний элемент из массива и уменьшает его size()). Другой способ изменить размер вектора — это сразу вызвать методы resize() под нужный размер. Именно потому, что размер вектора, в отличие от массива, может динамически меняться, для вектора предусмотрено 2 разных способа индексации: как операция [ i ] и как метод-функция at( i ). Они различаются: метод at() проверяет текущий размер вектора size(), и при индексации за его границу возбуждает исключение. Напротив, операция индексации не проверяет границу, что небезопасно, но зато это быстрее. Метод at() позволяет нам контролировать выход за границы вектора и либо квалифицировать это как логическую ошибку, либо корректировать текущий размер контейнера под потребность, как в вот таком фрагменте (здесь попыток доступа вдвое больше, чем реально выполненных операций):

Стандарт C++11 привносит дополнительные выразительные средства, такие, например, как списки инициализации и выводимость типов, которые намного упрощают работу с контейнерами (и даже делают ненужными старые привычные приёмы записи). Вот как может описываться матрица, когда одновременно описываются её а). конфигурация (квадратная, хотя может быть прямоугольная и даже треугольная), b). размерность (3х3) и c). инициализирующие значения:

А заодно, здесь же показана работа с векторами (транспонирование квадратной матрицы и вывод в выходной поток) как с псевдо-массивами (пользуясь только индексированием), чем вектора, по существу, и являются (в частности, показано как тип элемента вектор определяется на основании выводимого типа по стандарту C++11):

Примечание: В рамках того, что мы уже знаем о векторах, возникает иногда вопрос: а как строго должен определяться тип возвращаемого size() результата (чтобы избежать зависимости от платформы) и, соответственно, любых переменных циклов, оперирующих с размером вектора? Временами от блюстителей чистоты синтаксиса следует ответ, что это должен быть size_t, и этот ответ — неверный (тем более, что для многих платформ size_t и определяется как unsigned int). Если вы захотите записать абсолютно строгого определение типа size() вектора, то строку в примере выше следует записать вот так:

Или, полагаясь на выводимость типов C++11, вот так:

Отметив здесь этот тонкий нюанс (приняв к сведению), мы не станем его применять далее, во избежания лишней громоздкости примеров, а будем использовать для размерностей просто unsigned.

Name already in use

CPP-2019 / texts / 11-STL-1.md

Go to file T
Go to line L
Copy path
Copy permalink

Open with Desktop
View raw
Copy raw contents Copy raw contents

Copy raw contents

Стандартная библиотека шаблонов

В этой и двух последующих лекциях мы затронем вопросы, связанные с STL — стандартной библиотекой шаблонов, входящей в состав стандартной библиотеки языка С++. Не будет преувеличением сказать, что STL составляет ядро стандартной библиотеки и является важнейшей ее частью, широко используемой в промышленном программировании.

Общие сведения и состав STL

контейнеры (хранение объектов),
итераторы (доступ к элементам контейнера, инструмент для перебора элементов),
алгоритмы (обработка элементов),
контейнерные адаптеры (обёртки над контейнерами)
функциональные объекты, функторы (обобщение функций)

Контейнеры предназначены для управления коллекциями объектов определенного типа. У каждой разновидности контейнеров имеются свои достоинства и недостатки.

Итераторы предназначены для перебора элементов в коллекциях объектов (контейнерах или их подмножествах). Главное достоинство итераторов — они предоставляют небольшой, но стандартный интерфейс, подходящий для любого типа контейнера.

Алгоритмы предназначены для обработки элементов коллекций. (Поиск, сортировку, модификацию и т.д.). В работе алгоритмов используются итераторы. Алгоритм достаточно запрограммировать только один раз для обобщенного контейнера, потому что интерфейс итераторов является общим для всех контейнеров.

Рисунок 1. Архитектура библиотеки

Все компоненты стандартной библиотеки С++ располагаются в пространстве имен std.

Компоненты STL оформлены в виде шаблонов и поэтому могут использоваться с произвольными типами элементов.

STL формирует архитектуру для включения других классов коллекций и алгоритмов, работающих в сочетании с существующими коллекциями и алгоритмами.

STL — хороший пример концепции унифицированного (обобщенного) программирования.

Общие сведения о контейнерах

Контейнеры библиотеки STL можно разделить на два типа:

последовательные (линейные),
ассоциативные (нелинейные),

Общие вложенные типы

Container::value_type
Container::iterator
Container::const_iterator

Контейнеры должны поддерживать семантику значений вместо ссылочной семантики. При вставке элемента контейнер создает его внутреннюю копию, вместо того чтобы сохранять ссылку на внешний объект. Следовательно, элементы контейнера STL должны поддерживать копирование.

Элементы в контейнере располагаются в определенном порядке. Это означает, что при повторном переборе с применением итератора порядок перебора элементов должен остаться прежним. В каждом типе контейнера определены операции, возвращающие итераторы для перебора элементов.

В общем случае операции с элементами контейнеров небезопасны. Вызывающая сторона должна проследить за тем, чтобы параметры операции соответствовали требованиям.

Общие методы контейнеров

Метод	Назначение
ContType c	Создает пустой контейнер, не содержащий элементов
ContType c1(c2)	Создает копию контейнера того же типа
ContType c(beg,end)	Создает контейнер и инициализирует его копиями всех элементов в интервале [beg, end)
c.

Последовательные контейнеры – упорядоченные коллекции, в которых каждый элемент занимает определенную позицию. Позиция зависит от времени и места вставки, но не связана со значением элемента.

Контейнер array является оберткой над обычным статическим массивом. Размер контейнера определяется во время объявления и в дальнейшем не может быть изменен.

Наиболее популярный последовательный контейнер. Обеспечивает быструю вставку и удаление элемента с одного конца.

Рисунок 2. Схематическое изображение вектора

Элементы вектора копируются во внутренний динамический массив.
Вектор является упорядоченной коллекцией, т.е. элементы всегда хранятся в определенном порядке.
Вектор обеспечивает произвольный доступ к своим элементам. Обращение к любому элементу с известной позицией выполняется напрямую и с постоянным временем.
Итераторы векторов являются итераторами произвольного доступа, что позволяет применять к векторам все алгоритмы STL.
Операции присоединения и удаления элементов в конце вектора выполняются с высоким быстродействием.
Если элементы вставляются или удаляются в середине или в начале, быстродействие снижается, поскольку все элементы в последующих позициях приходится перемещать на новое место. На самом деле для каждого последующего элемента вызывается оператор присваивания.
Один из способов повышения быстродействия векторов заключается в выделении для вектора большего объема памяти, чем необходимо для хранения всех элементов
Векторы поддерживают стандартные операции проверки размера size(), empty() и max_size().
Функция capacity() возвращающая максимальное количество элементов, которые могут храниться в текущей выделенной памяти. Если количество элементов превысит это значение, вектору придется перераспределить свою внутреннюю намять.

Емкость вектора необходимо учитывать по двум причинам:

в результате перераспределения памяти становятся недействительными все ссылки, указатели и итераторы элементов вектора;
на перераспределение памяти требуется время.

Чтобы предотвратить перераспределение памяти, можно заранее зарезервировать некоторую емкость функцией reserve().

Либо можно проинициализировать вектор достаточным количеством элементов, для чего конструктору передается начальный размер вектора:

Емкость вектора напрямую никогда не уменьшается.

После вызова функции swap() все ссылки, указатели и итераторы продолжают ссылаться на первоначально выделенную память. Т.е. все ссылки, указатели и итераторы становятся недействительными.

Некоторые важные операции над вектором:

Метод	Назначение
c.at(idx)	Возвращает элемент с индексом idx (при недопустимом значении индекса генерируется исключение out_of_range)
c[idx]	Возвращает элемент с индексом idx (без интервальной проверки!)
c.front()	Возвращает первый элемент (без проверки его существования!)
c.back()	Возвращает последний элемент (без проверки его существования!)
c.begin()	Возвращает итератор произвольного доступа для первого элемента
c.end()	Возвращает итератор произвольного доступа для позиции за последним элементом
c.rbegin()	Возвращает обратный итератор для первого элемента при переборе в обратном направлении
c.rend()	Возвращает обратный итератор для позиции за последним элементом при переборе в обратном направлении
c.insert(pos, elem)	Вставляет в позицию итератора pos копию элемента elem и возвращает позицию нового элемента
c.insert(pos, n, elem)	Вставляет в позицию итератора pos n копий элемента elem (и не возвращает значения)
c.insert(pos, beg, end)	Вставляет копию всех элементов интервала [beg,end) в позицию итератора pos (и не возвращает значения)
c.push_back(elem)	Присоединяет копию elem в конец вектора
c.resize(num)	Приводит контейнер к размеру num (если size() при этом увеличивается, новые элементы создаются своим конструктором по умолчанию)
c.resize(num, elem)	Приводит контейнер к размеру num (если size() при этом увеличивается, новые элементы создаются как копии elem)
c.pop_back()	Удаляет последний элемент (не возвращая его)
c.erase(pos)	Удаляет элемент в позиции итератора pos и возвращает позицию следующего элемента
c.erase(beg, end)	Удаляет все элементы из интервала [beg, end) и возвращает позицию следующего элемента
c.clear()	Удаляет все элементы (контейнер остается пустым)

Итераторы остаются действительными до момента

вставки
или удаления элемента с меньшим индексом
или перераспределения памяти

Согласно стандарту, исключения генерирует только одна функция at() — безопасная версия оператора индексирования.

Пример использования вектора:

Контейнер c возможностью быстрой вставки и удаления элементов на обоих концах за O(1). Реализован как список указателей на массивы фиксированного размера.

Дек очень похож на вектор. Он обладает практически тем же интерфейсом и поддерживает произвольный доступ. Дек быстро выполняет операции вставки и удаления как с конца, так и с начала.

Рисунок 3. Схематическое изображение дека

По своим возможностям деки во многом отличаются от векторов:

Вставка и удаление выполняются быстро как в начале, так и в конце.
Операции выполняются с амортизированным постоянным временем.
Внутренняя структура содержит дополнительный уровень ссылок, поэтому обращение к элементам и перемещение итератора в деках обычно выполняются чуть медленнее.
Итераторы должны быть умными указателями особого типа.
Обычные указатели не подходят из-за необходимости перехода между блоками.
В системах с ограниченными размерами блоков памяти дек может содержать больше элементов, поскольку он не ограничивается одним блоком памяти. Следовательно, функция max_size() может возвращать для деков большую величину.
Деки не позволяют управлять емкостью и моментом перераспределения памяти. При любых операциях вставки и удаления, выполняемых не в начале или конце вектора, становятся недействительными все указатели, ссылки и итераторы элементов дека.
Перераспределение памяти в общем случае выполняется более эффективно, чем для векторов, потому что декам не приходится копировать все элементы.
Освобождение неиспользуемых блоков может привести к уменьшению объема памяти, занимаемой деком (происходит ли это и как — зависит от реализации).

Следующие особенности векторов характерны также и для деков:

Дек является упорядоченной коллекцией, т.е. элементы всегда хранятся в определенном порядке.
Итераторы деков являются итераторами произвольного доступа, что позволяет применять к векторам все алгоритмы STL.
Вставка и удаление элементов в середине контейнера выполняется относительно медленно, потому что для освобождения места или заполнения пропуска приходится перемещать элементы с обоих концов.

Деки не поддерживают методы, связанные с емкостью (capacity() и reserve()).

В деках определены прямые функции вставки и удаления первого элемента: push_front() и pop_front().

Двусвязный список. В любом месте контейнера вставка и удаление производятся за O(1).

Рисунок 4. Схематическое изображение списка

Список не поддерживает произвольный доступ к элементам.
Вставка и удаление элементов в любой позиции выполняются быстро.
В результате вставки и удаления элементов указатели, ссылки и итераторы, относящиеся к другим элементам, остаются действительными.
Обработка исключений в списках реализована так, что практически каждая операция завершается успешно или не вносит изменений – транзакционная безопасность.

Эти принципиальные различия отражены в функциях списков, что делает их непохожими на функции векторов и деков:

В списках не определены ни оператор индексирования, ни метод at().
Списки не поддерживают операции, связанные с емкостью и перераспределением памяти.
Списки поддерживают много специальных методов для перемещения элементов.

Эти методы представляют собой оптимизированные версии одноименных универсальных алгоритмов. Оптимизация основана на замене указателей вместо копирования и перемещения значений.

Список поддерживает стандартный набор:

c.remove(val) — Удаляет все элементы со значением val
c.remove_if(op) — Удаляет все элементы, для которых op(elem) возвращает true

Ассоциативные контейнеры автоматически сортируют свои элементы по некоторому критерию. Критерий представляется в виде функции, которая сравнивает либо значения, либо специальные ключи, определяемые для этих значений.

По умолчанию элементы или ключи контейнеров сравниваются при помощи оператора <. Но можно передать в контейнер собственную функцию сравнения и определить новый порядок сортировки.

Критерий сортировки также применяется при проверке на равенство: два элемента равны, если каждый из них не больше другого.

Ассоциативные контейнеры обычно реализуются в виде сбалансиорванных бинарных деревьев. У каждого элемента (узла) есть один родитель и два потомка. Все предки слева от узла имеют меньшие значения, а все предки справа — большие значения.

Ассоциативные контейнеры различаются по типу элементов и по тому, как они обходятся с дубликатами.

STL содержит четыре стандартных класса ассоциативных контейнеров:

Множества (set) — коллекции, в которых элементы сортируются в соответствии с их значениями. Каждый элемент присутствует в коллекции только в одном экземпляре, дубликаты не разрешаются.
Мультимножества (multiset) — то же, что и множества, но с возможностью хранения дубликатов. Т.е., мультимножество может содержать несколько элементов с одинаковыми значениями.
Отображения (map) — коллекции, состоящие из пар «ключ/значение». У каждого элемента имеется ключ, определяющий порядок сортировки, и значение. Каждый ключ присутствует в коллекции только в одном экземпляре, дубликаты не разрешаются.
Мультиотображения (multimap) — то же, что и отображения, но с возможностью дублирования ключей. Это означает, что мультиотображение может содержать несколько элементов с одинаковыми ключами.

Рисунок 5. Множества на основе деревьев

Пример с мультимножеством:

Элементами отображений и мультиотображений являются пары «ключ/значение».

Рисунок 6. Отображения на основе деревьев

Поэтому синтаксис объявления, вставки и обращения к элементам несколько изменяется, а именно:

Для вставки элемента в коллекцию необходимо создать объект pair. Задача может решаться с помощью вспомогательной функции make_pair().

Итератор ссылается на пару «ключ/значение», поэтому мы не можем просто направить его в выходной поток данных. Вместо этого приходится работать с отдельными членами структуры pair, которым присвоены имена first и second:

выражение pos->first определяет первый компонент пары «ключ/значение», то есть ключ элемента мультиотображения.
выражение pos->second определяет второй компонент пары «ключ/значение», то есть значение элемента мультиотображения. (Как и в случае с обычными указателями, это выражение представляет собой сокращенную запись для (*pos).second .)

При работе с отображениями операция вставки может осуществляться оператором индексирования []:

Индекс используется в качестве ключа и может иметь произвольный тип.

Оператор индексирования в данном случае работает не так, как обычный оператор индексирования массивов. Отсутствие элемента, связанного с индексом, не является ошибкой. При появлении нового индекса (или ключа) создается и вставляется в контейнер новый элемент, ключом которого является указанный индекс. Таким образом, в ассоциативных массивах индекс в принципе не может принимать недопустимое значение.

Следовательно, в приведенном коде создаются новые элементы. А оператор присваивания связывает ключи со значениями, преобразованными к типу float.

Containers library

Библиотека Containers-это общая коллекция шаблонов классов и алгоритмов,которые позволяют программистам легко реализовать такие распространенные структуры данных,как очереди,списки и стеки.Существует два (до C++11)три (с C++11)класса контейнеров:

sequence containers,
ассоциативные контейнеры,и

неупорядоченные ассоциативные контейнеры,

каждый из которых предназначен для поддержки различных операций.

Контейнер управляет пространством хранилища,выделенным для его элементов,и предоставляет функции членов для доступа к ним,либо напрямую,либо через итераторы (объекты со свойствами,сходными с указателями).

Большинство контейнеров имеют,по крайней мере,несколько общих функций и имеют общие функции.Какой контейнер лучше всего подходит для конкретного приложения,зависит не только от предлагаемой функциональности,но и от его эффективности для различных рабочих нагрузок.

Sequence containers

Контейнеры последовательностей реализуют структуры данных,доступ к которым возможен последовательно.

Associative containers

Ассоциированные контейнеры реализуют сортируемые структуры данных,которые можно быстро искать (сложность O(log n)).

Неупорядоченные ассоциативные контейнеры (с C++11)

В неупорядоченных ассоциативных контейнерах реализованы несортированные (хэшированные)структуры данных,которые можно быстро искать (амортизация O(1),наихудшая сложность O(n)).

Container adaptors

Контейнерные адаптеры обеспечивают другой интерфейс для последовательных контейнеров.

Views

span (начиная с C++20) и mdspan (начиная с C++23) — это представления без владения непрерывной последовательностью объектов, хранилище которых принадлежит какому-то другому объекту.

Iterator invalidation

Методы только для чтения никогда не делают недействительными итераторы или ссылки.Методы,изменяющие содержимое контейнера,могут сделать недействительными итераторы и/или ссылки,приведенные в этой таблице.

Category	Container	После вставки .	После стирания .	Conditionally
iterators valid?	references valid?	iterators valid?	references valid?
Sequence containers	array	N/A	N/A
vector	No	N/A	Вставка измененная емкость
Yes	Yes	Перед модифицированными элементами (для вставки только если емкость не изменилась)
No	No	На или после модифицированного элемента (элементов)
deque	No	Yes	Да,за исключением стертых элементов.	Измененный первый или последний элемент
No	No	Только модифицированная середина
list	Yes	Да,за исключением стертых элементов.
forward_list	Yes	Да,за исключением стертых элементов.
Associative containers	set multiset map multimap	Yes	Да,за исключением стертых элементов.
Неупорядоченные ассоциативные контейнеры	unordered_set unordered_multiset unordered_map unordered_multimap	No	Yes	N/A	Вставка вызвала повторную запись
Yes	Да,за исключением стертых элементов.	No rehash

Здесь, вставка относится к любому способу , который добавляет один или более элементы в контейнер и стирание относится к любому способу , который удаляет один или несколько элементов из контейнера.

Примерами методов вставки являются std::set::insert , std::map::emplace , std::vector::push_back и std::deque::push_front .

Обратите внимание, что std::unordered_map::operator[] также имеет значение, так как он может вставить элемент в карту.

Примеры способов стирания являются std::set::erase , std::vector::pop_back , std::deque::pop_front и std::map::clear .
- clear делает недействительными все итераторы и ссылки. Поскольку он стирает все элементы, это технически соответствует приведенным выше правилам.
Если не указано иное (явно или путем определения функции в терминах других функций),передача контейнера в качестве аргумента библиотечной функции никогда не аннулирует итераторы к объектам внутри этого контейнера и не изменяет их значения.

Отдельного упоминания заслуживает итератор прошедшего конца. Как правило, этот итератор становится недействительным, как если бы он был обычным итератором для нестертого элемента. Таким образом std::set::end никогда не становится недействительным, std::unordered_set::end становится недействительным только при перефразировании (начиная с C++11), std::vector::end всегда становится недействительным (поскольку он всегда после измененного элементы) и так далее.

Есть одно исключение: стирание, которое удаляет последний элемент std::deque does аннулировать последний итератор, даже если он не является стертым элементом контейнера (или вообще элементом). В сочетании с общими правилами для итераторов std::deque , чистый результат — единственная модифицирующая операция, которая делает not invalidate std::deque::end — это стирание, которое удаляет первый элемент, но не последний.
Похожие публикации: