Контейнер последовательности (C++)

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

В текущей версии стандарта C++ определены следующие контейнеры: array, vector, list, forward_list, deque. В каждом из этих контейнеров реализованы разные алгоритмы хранения данных, а это значит, что они имеют разные гарантии скорости для разных операций:

• array реализует массив без изменения размера во время компиляции.
• vector реализует массив с быстрым произвольным доступом и возможностью автоматического изменения размера при добавлении элементов.
• deque реализует двустороннюю очередь со сравнительно быстрым произвольным доступом.
• list реализует двусвязный список .
• forward_list реализует односвязный список .

Поскольку для правильной работы каждый из контейнеров должен иметь возможность копировать свои элементы, тип элементов должен соответствовать CopyConstructible и Assignable требования. Для данного контейнера все элементы должны принадлежать к одному типу. Например, нельзя хранить данные в форме char и int в одном экземпляре контейнера.

История

Первоначально только vector, list и deque были определены. До стандартизации языка C++ в 1998 году они были частью стандартной библиотеки шаблонов (STL), опубликованной SGI . Александр Степанов , главный разработчик STL, сожалеет о выборе вектора имени , говоря, что оно пришло из старых языков программирования Scheme и Lisp , но не соответствует математическому значению этого термина.

The array контейнер впервые появился в нескольких книгах под разными названиями. Позже он был включен в библиотеку Boost и был предложен для включения в стандартную библиотеку C++. Мотивация включения array заключалось в том, что он решает две проблемы массива в стиле C: отсутствие STL-подобного интерфейса и невозможность копирования, как любой другой объект. Впервые он появился в C++ TR1 , а затем был включен в C++11 .

The forward_list контейнер был добавлен в C++11 как компактная альтернатива list когда обратная итерация не нужна.

Характеристики

array, vector и deque все поддерживают быстрый произвольный доступ к элементам. list поддерживает двунаправленную итерацию, тогда как forward_list поддерживает только однонаправленную итерацию.

array не поддерживает вставку или удаление элементов. vector поддерживает быструю вставку или удаление элемента в конце. Любая вставка или удаление элемента не в конце вектора требует наличия элементов между позицией вставки и концом вектора, который нужно скопировать. затронутых Таким образом , итераторы элементов становятся недействительными. Фактически, любая вставка потенциально может сделать недействительными все итераторы. Кроме того, если выделенное хранилище в vector слишком мал для вставки элементов, выделяется новый массив, все элементы копируются или перемещаются в новый массив, а старый массив освобождается. deque, list и forward_list все поддерживают быструю вставку или удаление элементов в любом месте контейнера. list и forward_list сохраняет допустимость итераторов для такой операции, тогда как deque делает недействительными все из них.

Вектор

Элементы vector хранятся последовательно. Как и все динамических массивов реализации , векторы имеют низкое использование памяти и хорошую локальность ссылок и использование кэша данных . В отличие от других контейнеров STL, таких как деки и списки , векторы позволяют пользователю обозначать начальную емкость контейнера.

Векторы допускают произвольный доступ ; то есть на элемент вектора можно ссылаться так же, как и на элементы массива (по индексам массива). Связанные списки и множества , с другой стороны, не поддерживают произвольный доступ или арифметику указателей.

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

Емкость и перераспределение

Типичная векторная реализация внутренне состоит из указателя на динамически выделяемый массив. и, возможно, элементы данных, содержащие емкость и размер вектора. Размер вектора относится к фактическому количеству элементов, а емкость — к размеру внутреннего массива.

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

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

Операцию резерва() можно использовать для предотвращения ненужных перераспределений. После вызова Reserve(n) емкость вектора гарантированно будет не ниже n.

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

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

Специализация для bool

Стандартная библиотека определяет специализацию vector шаблон для bool. В описании этой специализации указано, что реализация должна упаковывать элементы так, чтобы каждый bool использует только один бит памяти. Многие считают это ошибкой. vector<bool> не соответствует требованиям для контейнера стандартной библиотеки C++ . Например, container<T>::reference должно быть истинным значением типа T. Это не тот случай, когда vector<bool>::reference, который представляет собой прокси-класс, конвертируемый в bool. Аналогичным образом, vector<bool>::iterator не дает bool& при разыменовании . Среди Комитета по стандартизации C++ и Библиотечной рабочей группы существует общее мнение, что vector<bool> должен быть признан устаревшим и впоследствии удален из стандартной библиотеки, а функциональность будет вновь введена под другим именем.

Список

The list Структура данных реализует двусвязный список . Данные хранятся в памяти несмежно, что позволяет структуре данных списка избежать перераспределения памяти, которое может потребоваться для векторов при вставке новых элементов в список.

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

Списки эффективны при вставке новых элементов в список; это ⁠ $O(1)$⁠ операция. Никакого смещения не требуется, как в случае с векторами.

Списки не имеют возможности произвольного доступа, как векторы ( ⁠ $O(1)$⁠ операция). Доступ к узлу в списке — это ⁠ $O(n)$⁠ операция, требующая обхода списка для поиска узла, к которому необходимо получить доступ.

При использовании небольших типов данных (например, целых) затраты памяти гораздо значительнее, чем у векторов. Каждый узел занимает sizeof(type) + 2 * sizeof(type*). Указатели обычно представляют собой одно слово (обычно четыре байта в 32-битных операционных системах), а это означает, что список из четырехбайтовых целых чисел занимает примерно в три раза больше памяти, чем вектор целых чисел.

Список пересылки

The forward_list Структура данных реализует односвязный список .

Поэтому

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

Множество

array без изменения размера реализует массив . Размер определяется во время компиляции параметром шаблона. По своей конструкции контейнер не поддерживает распределители, поскольку по сути это оболочка массива в стиле C.

Обзор функций

Контейнеры определяются в заголовках, названных в честь имен контейнеров, например vector определяется в заголовке <vector>. Все контейнеры удовлетворяют требованиям концепции , Container а это значит, что они имеют begin(), end(), size(), max_size(), empty(), и swap() методы.

Функции-члены

Функции	array ( С++ 11 )	vector	deque	list	forward_list ( С++ 11 )	Описание
Основы	(скрытый)	(конструктор)	(конструктор)	(конструктор)	(конструктор)	Создает контейнер из различных источников.
		(деструктор)	(деструктор)	(деструктор)	(деструктор)	Уничтожает контейнер и содержащиеся в нем элементы.
		operator=	operator=	operator=	operator=	Присваивает значения контейнеру
	—	assign	assign	assign	assign	Присваивает значения контейнеру
Распределители		get_allocator	get_allocator	get_allocator	get_allocator	Возвращает распределитель, используемый для выделения памяти для элементов.
Элемент доступ	at	at	at	—	—	Доступ к указанному элементу с проверкой границ.
	operator[]	operator[]	operator[]			Доступ к указанному элементу без проверки границ.
	front	front	front	front	front	Доступ к первому элементу
	back	back	back	back	—	Доступ к последнему элементу
	data	data	—	—		Доступ к базовому массиву
Итераторы	begin cbegin	begin cbegin	begin cbegin	begin cbegin	begin cbegin	Возвращает итератор в начало контейнера
	end cend	end cend	end cend	end cend	end cend	Возвращает итератор до конца контейнера
	rbegin crbegin	rbegin crbegin	rbegin crbegin	rbegin crbegin	—	Возвращает обратный итератор к обратному началу контейнера.
	rend crend	rend crend	rend crend	rend crend		Возвращает обратный итератор на обратный конец контейнера.
Емкость	empty	empty	empty	empty	empty	Проверяет, пуст ли контейнер
	size	size	size	size	—	Возвращает количество элементов в контейнере.
	max_size	max_size	max_size	max_size	max_size	Возвращает максимально возможное количество элементов в контейнере.
	—	reserve	—	—	—	Хранение запасов в контейнере
		capacity				Возвращает количество элементов, которые могут храниться в выделенном на данный момент хранилище.
		shrink_to_fit	shrink_to_fit			Уменьшает использование памяти за счет освобождения неиспользуемой памяти ( C++11 ).
Модификаторы		clear	clear	clear	clear	Очищает содержимое
		insert	insert	insert	—	Вставляет элементы
		emplace	emplace	emplace		Конструирует элементы на месте ( C++11 )
		erase	erase	erase		Стирает элементы
		—	push_front	push_front	push_front	Вставляет элементы в начало
			emplace_front	emplace_front	emplace_front	Создает элементы на месте в начале ( C++11 )
			pop_front	pop_front	pop_front	Удаляет первый элемент
		push_back	push_back	push_back	—	Вставляет элементы до конца
		emplace_back	emplace_back	emplace_back		Конструирует элементы на месте в конце ( C++11 )
		pop_back	pop_back	pop_back		Удаляет последний элемент
		—	—	—	insert_after	Вставляет элементы после указанной позиции ( C++11 )
					emplace_after	Создает элементы на месте после указанной позиции ( C++11 )
					erase_after	Стирает элементы на месте после указанной позиции ( C++11 )
		resize	resize	resize	resize	Изменяет количество хранимых элементов
	swap	swap	swap	swap	swap	Заменяет содержимое другим контейнером того же типа.
	fill	—	—	—	—	Заполняет массив заданным значением

Существуют и другие операции, доступные как часть класса списка, а также алгоритмы, являющиеся частью C++ STL ( Algorithm (C++) ), которые можно использовать с list и forward_list сорт:

Операции

• list::merge и forward_list::merge - Объединяет два отсортированных списка.
• list::splice и forward_list::splice_after - Перемещает элементы из другого списка
• list::remove и forward_list::remove - Удаляет элементы, равные заданному значению
• list::remove_if и forward_list::remove_if - Удаляет элементы, удовлетворяющие определенным критериям.
• list::reverse и forward_list::reverse - Меняет порядок элементов на обратный
• list::unique и forward_list::unique - Удаляет последовательные повторяющиеся элементы.
• list::sort и forward_list::sort - Сортирует элементы

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

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

#include <iostream>
#include <vector>
#include <array>
#include <algorithm> // sort, max_element, random_shuffle, remove_if, lower_bound 
#include <functional> // greater
#include <iterator> // begin, end, cbegin, cend, distance

// used here for convenience, use judiciously in real programs. 
using namespace std;

int main()
{
  array arr{ 1, 2, 3, 4 };

  // initialize a vector from an array
  vector<int> numbers(cbegin(arr), cend(arr));

  // insert more numbers into the vector
  numbers.push_back(5);
  numbers.push_back(6);
  numbers.push_back(7);
  numbers.push_back(8);
  // the vector currently holds { 1, 2, 3, 4, 5, 6, 7, 8 }

  // randomly shuffle the elements
  shuffle(begin(numbers), end(numbers));
  
  // locate the largest element, O(n)
  auto largest = max_element(cbegin(numbers), cend(numbers));
  
  cout << "The largest number is " << *largest << "\n";
  cout << "It is located at index " << distance(largest, cbegin(numbers)) << "\n";
  
  // sort the elements
  sort(begin(numbers), end(numbers));

  // find the position of the number 5 in the vector 
  auto five = lower_bound(cbegin(numbers), cend(numbers), 5);  
  
  cout << "The number 5 is located at index " << distance(five, cbegin(numbers)) << ‘\n’;
  
  // erase all the elements greater than 4   
  numbers.erase(
    remove_if(begin(numbers),
              end(numbers),
              [](auto n) constexpr { return n > 4; });
  
  // print all the remaining numbers
  for (const auto& element : numbers)
    cout << element << " ";
}

Результат будет следующим:

The largest number is 8
It is located at index 6 (implementation-dependent)
The number 5 is located at index 4
1 2 3 4

Ссылки

• Уильям Форд, Уильям Топп. Структуры данных с C++ и STL , второе издание. Прентис Холл, 2002. ISBN   0-13-085850-1 . Глава 4: Класс Vector, стр. 195–203.
• Джосуттис, Николай М. (1999). Стандартная библиотека C++ . Аддисон-Уэсли. ISBN  0-201-37926-0 .