Последовательный контейнер
Последовательными контейнерами (англ. Sequence containers) в языке программирования C++ считаются несколько предопределённых шаблонных типов данных стандартной библиотеки STL, которые обеспечивают упорядоченный способ хранения своих элементов. Каждый из элементов такого контейнера имеет определённую позицию, которая зависит от времени и места помещения его в контейнер, но не зависит от значения элемента. Как правило, к последовательным контейнерам относятся списки, вектора, очереди двустороннего доступа, массивы (начиная со стандарта C++11) и ряд других. Обычно их реализуют на практике в виде связанного списка или массива[1][2].
Описание[править | править код]
Все основные стандартные классы-контейнеры библиотеки STL подразделяются на последовательные и ассоциативные контейнеры. Ключевое отличие последовательных контейнеров от ассоциативных заключается в том, что при помещении элемента в последовательный контейнер он остаётся там, где его разместили, а в ассоциативном он перемещается туда, где ему положено находиться в соответствии со внутренним устройством контейнера[3].
Традиционно в категорию стандартных последовательных контейнеров входят массивы array, списки (как односвязные forward_list, так и двусвязные list), динамические вектора vector и очереди deque[4][5][6]. Иногда в их состав также включают строки string, а к нестандартным последовательным контейнерам относят списки slist и строковые данные rope[7].
Требования к элементам[править | править код]
Основная технологическая оснастка библиотеки STL (контейнеры, итераторы, алгоритмы) реализована в виде шаблонных классов. Как следствие, эта инфраструктура может одинаково эффективно обрабатывать как встроенные, так и пользовательские типы данных. Тем не менее, все элементы всех контейнеров библиотеки STL должны подчиняться ряду достаточно общих требований. Во-первых, они должны быть перемещаемыми и копируемыми. Во-вторых, к ним должно быть допустимо применение операции присваивания. В-третьих, для их уничтожения должен быть доступен деструктор. В дополнение к этим требованиям ряд последовательных контейнерных классов требует наличия конструктора по умолчанию, а в некоторых методах может потребоваться определённая операция сравнения на равенство operator==() для элементов[8][9].
Базовый функционал[править | править код]
С основными последовательными контейнерами связан набор стандартных операций, поддерживаемых всеми классами библиотеки STL для унифицированного доступа к своим элементам[10].
| Название | Функции |
|---|---|
+ |
Объединение элементов |
+= |
Добавление элементов в контейнер |
<< |
Добавление элемента в контейнер |
at() |
Доступ к произвольному элементу |
front() и first() |
Предоставляют ссылку на первый элемент в предположении, что он существует. Использование метода front() предпочтительнее по стандарту STL.
|
back() и last() |
Предоставляют ссылку на последний элемент в предположении, что он существует. Использование метода back() предпочтительнее по стандарту STL.
|
contains() |
Проверка контейнера на наличие переданного элемента |
erase() |
Удаляет элемент, на который указывает параметр-итератор |
IndexOf() |
Возвращает индекс первого элемента, который соответствует значению переданного параметра. |
pop_front() |
Удаляет из контейнера первый элемент |
pop_back() |
Удаляет из контейнера последний элемент |
replace() |
Заменяет значение элемент контейнера на значение своего параметра |
push_front() и prepend() |
Добавляют элемент в начало контейнера. Использование метода push_front() предпочтительнее по стандарту STL.
|
push_back() и append() |
Добавляют элемент в конец контейнера. Использование метода push_back() предпочтительнее по стандарту STL.
|
В дополнение к ним важной операцией считается функция resize(), которая позволяет динамически варьировать количество элементов в коллекции за линейное время. Её поддерживают все классы, за исключением массива array, который идеологически не предназначен для изменений своего размера в памяти[11].
Примечания[править | править код]
- ↑ Josuttis, 2012, Containers, p. 167—168.
- ↑ Литвиненко, 2005, Стандартная библиотека шаблонов STL, с. 137.
- ↑ Meyers, 2001, Containers, p. 16.
- ↑ Josuttis, 2012, Sequence containers, p. 169.
- ↑ Containers Архивная копия от 14 января 2020 на Wayback Machine www.cplusplus.com
- ↑ Containers in C++ STL Архивная копия от 12 января 2020 на Wayback Machine www.geeksforgeeks.org
- ↑ Meyers, 2001, Containers, p. 11.
- ↑ Josuttis, 2012, Requirements for Container Elements, p. 244.
- ↑ Posch, Galowicz, 2018, Sequence containers, p. 14.
- ↑ Шлее, 2015, Последовательные контейнеры, с. 96.
- ↑ Josuttis, 2012, Containers, p. 176.
Источники[править | править код]
- Литвиненко, Н. А. Технология программирования на C++ : Начальный курс. — СПб. : «БХВ-Петербург», 2005. — 288 с. — ББК 32.973.26-018.1я73. — УДК 681.3.068Ь800.92C++(075.8)(G). — ISBN 5-94157-655-2.
- Шлее, М. Qt 5.3 : Профессиональное программирование на C++. — СПб. : «БХВ-Петербург», 2015. — 928 с. — ББК 32.973.26-018.1. — УДК 004.438C++(G). — ISBN 978-5-9775-3346-1.
- Josuttis, N. M. The C++ Standard Library : A Tutorial and Reference : [англ.]. — 2nd. — Addison-Wesley, 2012. — ISBN 978-0-321-62321-8.
- Meyers, S. Effective STL : 50 Specific Ways to Improve Your Use of the Standard Template Library : [англ.]. — 2nd. — Addison-Wesley, 2001. — ISBN 0-201-74962-9.
- Posch, M. Expert C++ Programming : Leveraging the power of modern C++ to build scalable modular applications : [англ.] / M. Posch, J. Galowicz. — 2nd. — Packt Publishing, 2018. — ISBN 978-1-78883-139-0.