C++ за 21 день седьмое издание

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

Как и подразумевает их название, последовательные контейнеры (sequential container) используются для содержания данных в последовательном виде, таком как массивы и спи­ ски. Последовательные контейнеры характеризуются быстрым выполнением вставки, но относительно медленным поиском.

Ниже приведены последовательные контейнеры библиотеки STL.

0. 
   s t d :: v e c to r . Работает как динамический массив и увеличивается с конца. Вектор по­ хож на книжную полку, книги на которую можно добавлять или удалять по одной с конца.
   

0. 
   s t d : : deque . Подобен контейнеру s t d : : v e c to r , но новые элементы можно вставлять и удалять также вначале.
   
1. 
   s t d : : l i s t . Работает как двухсвязный список. Список похож на цепь, где каж ­ дый объект связан со следую щ им звеном. Вы можете добавить или удалить звено (т.е. объект) в любой позиции.
   

0. 
   s t d : : f o r w a r d l i s t . Подобен списку s t d : : l i s t , но односвязный список позволяет осуществлять перебор только в одном направлении.
   

Класс v e c t o r библиотеки STL сродни массиву и обеспечивает произвольный доступ

0. 
   элементам, т.е. вы можете непосредственно обращаться к элементам вектора по пози­ ции, используя оператор индексирования ([ ]), и манипулировать их данными. Кроме того, вектор STL является динамическим массивом, а потому может изменять свои размеры, чтобы приспособиться к требованиям приложения. Для обеспечения этой возможности при сохранении способности произвольного обращения к элементам массива по позиции большинство реализаций контейнера v e c to r библиотеки STL сохраняет все элементы по­ следовательно (т.е. в смежных областях). Поэтому вектор должен часто изменять свои раз­ меры; он может существенно ухудшить производительность приложения в зависимости от типа объектов, которые содержит. Кратко вектор был представлен в листинге 4.4, а более подробно контейнер v e c t o r обсуждается на занятии 17, “Классы динамических массивов библиотеки STL”.
   

Контейнер l i s t библиотеки STL является реализацией обычного связанного списка. Хотя к элементам списка нельзя обращаться произвольно, как в векторе STL, список спо­ собен организовать элементы в разделах, состоящих из нескольких участков, несмежных

Контейнеры STL

379

0. 
   памяти. Поэтому у контейнера s t d : : l i s t нет присущих вектору проблем с производи­ тельностью, связанных с перераспределением его внутреннего массива. Подробно класс списка библиотеки STL обсуждается на занятии 18, “Классы двухсвязного и односвязного списков библиотеки STL”.