Обзор контейнеров C++ STL

Подсказки. В этой статье основное внимание уделяется временной сложности алгоритма добавления, удаления и проверки каждого контейнера.

В C++ контейнер относится к общей структуре данных, которая может вмещать различные типы данных и является шаблоном класса. Например, установленный шаблон класса:

template <class _Key, class _Compare = less<_Key>,
          class _Allocator = allocator<_Key> >
class _LIBCPP_TYPE_VIS_ONLY set

В C++ существует три основных типа контейнеров:

последовательный контейнер
ассоциативный контейнер
адаптер контейнера

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

Элементы, используемые для указания на последовательные контейнеры и ассоциативные контейнеры
Использование аналогично указателю
Существуют константы (имя класса контейнера::имя переменной итератора) и неконстантные (имя класса контейнера::имя переменной const_iterator)
Элемент, на который он указывает, может быть прочитан через итератор
неконстантные итераторы и элемент, на который они указывают, могут быть изменены

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

Что такое последовательный контейнер, то есть позиция элемента вставляется последовательно, и позиция вставки не имеет ничего общего со значением элемента.Ядро в том, что контейнер не сортируется. Все последовательные контейнеры имеют следующие 10 функций-членов:

#返回迭代器
begin
end
rbegin  //返回指向最后一个元素的迭代器
rend
#返回元素引用
front
back
#其他
erase（删除区间时返回被删除元素后面的迭代器；也可删除一个或几个元素）
clear
push_back
pop_back

Существует три типа последовательных контейнеров:

1.vector файл заголовка динамического массива`<vetor>`

Элементы хранятся в памяти непрерывно.

Время произвольного доступа: постоянное время (поскольку к адресу можно получить доступ напрямую, подписавшись).

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

Добавить или удалить элементы в середине или в начале: o(n) (будет перемещать положение других элементов).

Тип итератора: произвольный доступ (поддерживает индексный доступ, случайное перемещение, например: a[i]).

Время запроса: o(n) (поскольку сортировки нет, возможен только текущий поиск, что менее эффективно).

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

Достоинства: память полностью совместима с C, эффективный произвольный доступ, экономия места

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

Конструктор:

 vector();
 vector(int n);
 vector(int n, const T &a); //把n个元素初始化为a
 vector(iterator first,iterator last); //初始化为其他容器上区间[first,last)一致的内容

Общие функции-члены

void pop_back();
void push_back(const T &val);
int size();
T & font();
T & back();

deque[read:dek, часто читаемый dkju:] файл заголовка двунаправленной очереди`<deque>`

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

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

Добавление или удаление элементов на обоих концах обычно происходит за постоянное время. (У двухсторонней очереди нет такой емкости, как у вектора, и ей не нужно перераспределять пространство памяти. Это связано с тем, что двухсторонняя очередь состоит из динамически выделяемых смежных пространств, а именно буферов, которые можно связать в любое время, добавив новое пространство. Это не нужно быть похожим на вектор. "Перераспределить в 2 раза больше места из-за нехватки старого места, затем скопировать элемент, затем освободить старое пространство". Время увеличивается при перераспределении буферов).

Вставка посередине: высокая временная сложность.

Тип итератора: произвольный доступ (менее эффективный, чем векторный).

Время запроса: o(n) (по той же причине, что и выше).

**Преимущества: эффективный произвольный доступ, удобная внутренняя вставка и удаление элементов, высокая эффективность push и pop на обоих концах **

**Недостаток: большое использование памяти **

list заголовочный файл двусвязного списка`<list>`

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

Добавление или удаление элементов в любом месте во времени: постоянное время.

Время запроса: o(n) (по той же причине, что и выше).

Тип итератора: двунаправленный (доступ по индексу не поддерживается, операторы сравнения для итераторов и операторы +- не поддерживаются)

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

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

Общие функции-члены: (обратите внимание, что все они находятся в последовательных контейнерахсписок уникальныхиз)

push_front
pop_front
sort   //不支持STLsort算法
remove
unique
merge
reverse
splice

В частности, функция сортировки списка имеет две версии: без параметров и сравнение.

list<T> classname
classname.sort(compare);  //compare自定义
classname.sort();

ассоциативный контейнер (тип итератора: двунаправленный)

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

Время вставки и извлечения элементов: o(log(N)) (поскольку это реализовано красно-черным бинарным деревом, время соответствует сбалансированному бинарному дереву).

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

В основном он включает следующие 4 вида:

set
multiset
map
multimap

В дополнение к функциям-членам, которые есть у всех контейнеров, все они имеют следующие функции-члены.

find
lower_bound
upper_bound
equal_range
count
insert

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

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

Адаптеры контейнеров (итераторы не поддерживаются)

Эта концепция звучит немного абстрактно, но на самом деле STL помогает нам абстрагироваться от методов манипулирования данными, необходимых в реальной работе. Например, переменный ток может иметь любое напряжение передачи, но в реальной жизни нам нужно только 220 В, и трансформатор помогает нам выполнить эту основную функцию. Точно так же контейнеры работают по-разному, но на самом деле нам нужно, чтобы они работали только в соответствии с некоторыми реальными спецификациями.

Они оба имеют следующие 3 функции-члена:

push
top
pop

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

стек файл заголовка стека`<stack>`

является конечной последовательностью и удовлетворяет тому, что элементы в последовательности, которые удаляются, извлекаются и изменяются, могут быть только элементами, вставленными в последовательность последними (верхний элемент стека). Это,ЛИФО «первым пришел — первым вышел».

Его можно реализовать с помощью vector, deque, list (худшая производительность), а компилятор использует deque по умолчанию.

Например, при отладке программы стек ошибок представляет собой приложение.

файл заголовка очереди`<queue>`

Вставки могут быть сделаны только в конце, а удаления, извлечения и модификации разрешены только в начале.ФИФО.

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

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

priority_queue файл заголовка приоритетной очереди`<queue>`

Элемент с наивысшим приоритетом всегда удаляется из очереди первым.

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

Например, алгоритм планирования потоков операционной системы, некоторые из них планируются в соответствии с приоритетом.

Суммировать

Если требуется произвольный доступ, используйте вектор
Если количество элементов хранения известно, используйте вектор
Нужна случайная вставка и удаление в любой позиции, используйте список
Часто вставляйте и удаляйте элементы в начале и в конце контейнера, используйте deque
Если структура элемента сложная, используйте список или вектор для хранения указателей (требуются дополнительные усилия для поддержания памяти), в зависимости от требований.
Если операция основана на ключевых значениях, используйте set/map
Если вам нужны частые поиски, используйте map/set