Язык программирования C++. Пятое издание - Стенли Липпман

Эта глава основана на материале разделов 3.2–3.4. Здесь подразумевается, что читатель знаком с их материалом.

9.1. Обзор последовательных контейнеров

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

• цена добавления и удаления элементов из контейнера;

• цена непоследовательного доступа к элементам контейнера.

Таблица 9.1. Типы последовательных контейнеров

vector Массив переменного размера (вектор). Обеспечивает быстрый произвольный доступ. Вставка и удаление элементов, кроме как в конец, могут быть продолжительными deque Двухсторонняя очередь. Обеспечивает быстрый произвольный доступ. Быстрая вставка и удаление в начало и конец list Двухсвязный список. Обеспечивает только двунаправленный последовательный доступ. Быстрая вставка и удаление в любую позицию forward_list Односвязный список. Обеспечивает только последовательный доступ в одном направлении. Быстрая вставка и удаление в любую позицию array Массив фиксированного размера. Обеспечивает быстрый произвольный доступ. Не позволяет добавлять или удалять элементы string Специализированный контейнер, подобный вектору, содержащий символы. Быстрый произвольный доступ. Быстрая вставка и удаление в конец

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

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

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

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

Типы forward_list и array были добавлены согласно новому стандарту. Класс array — более безопасная и легкая в употреблении альтернатива встроенным массивам. Как и встроенные массивы, объект библиотечного класса array имеет фиксированный размер. В результате он не поддерживает операции по добавлению и удалению элементов или изменению размеров контейнера. Класс forward_list предназначен для замены наилучших самодельных односвязных списков. Следовательно, у него нет функции size(), поскольку сохранение или вычисление его размера повлекло бы дополнительные затраты по сравнению с самодельным списком. Для других контейнеров функция size() гарантированно будет выполняться быстро с постоянной скоростью.

По причинам, изложенным в разделе 13.6, новые библиотечные контейнеры работают существенно быстрее, чем в предыдущих версиях. Библиотечные контейнеры почти наверняка работают так же (если не лучше), чем даже наиболее тщательно разработанные альтернативы. Современные программы С++ должны использовать библиотечные контейнеры, а не множество примитивных структур, подобных массивам.

Решение о том, какой последовательный контейнер использовать

Как правило, если нет серьезных оснований предпочесть другой контейнер, лучше использовать контейнер vector.

Ниже приведено несколько эмпирических правил по выбору используемого контейнера.

• Если нет причин использовать другой контейнер, используйте вектор.

• Если имеется много небольших элементов и дополнительных затрат, не используйте контейнер list или forward_list.

• Если нужен произвольный доступ к элементам, используйте контейнер vector или deque.

• Если необходима вставка или удаление элементов в середину, используйте контейнер list или forward_list.

• Если необходима вставка или удаление элементов в начало или в конец, но не в середину, используйте контейнер deque.

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

  • сначала решите, необходимо ли фактически добавлять элементы в середину контейнера. Зачастую проще добавлять элементы в vector, а затем использовать библиотечную функцию sort() (рассматриваемую в разделе 10.2.3) для переупорядочивания контейнера по завершении ввода;

  • если вставка в середину необходима, рассмотрите возможность использования контейнера list на фазе ввода, а по его завершении — копирования списка в вектор.

Но что если нужен и произвольный доступ, и вставка (удаление) элементов в середину контейнера? Решение будет зависеть от отношения цены доступа к элементам в контейнере list и forward_list цены вставки (удаления) элементов в контейнер vector или deque. Как правило, выбор типа контейнера определит преобладающая операция приложения (произвольный доступ или вставка и удаление). В таких случаях, вероятно, потребуется проверка производительности приложения с использованием контейнеров обоих типов.

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

Упражнения раздела 9.1

Упражнение 9.1. Какой из контейнеров (vector, deque или list) лучше подходит для приведенных ниже задач? Объясните, почему. Если нельзя отдать предпочтение тому или иному контейнеру, объясните, почему?

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

• Чтение неизвестного заранее количества слов. Новые слова всегда добавляются в конец. Следующее значение извлекается из начала.

• Чтение неизвестного заранее количества целых чисел из файла. Числа сортируются, а затем выводятся на стандартное устройство вывода.

9.2. Обзор библиотечных контейнеров

Возможные операции с контейнерами составляют своего рода иерархию.

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

• Другие операции являются специфическими только для последовательных (табл. 9.3), ассоциативных (табл. 11.7) или неупорядоченных (табл. 11.8) контейнеров.

• Остальные являются общими лишь для небольшого подмножества контейнеров.

Таблица 9.2. Средства контейнеров

Псевдонимы типов iterator Тип итератора для контейнера данного типа const_iterator Тип итератора, позволяющий читать, но не изменять значение элемента size_type Целочисленный беззнаковый тип, размер которого достаточно велик, чтобы содержать значение размера наибольшего возможного контейнера данного типа difference_type Целочисленный знаковый тип, размер которого достаточно велик, чтобы содержать значение разницы между двумя итераторами value_type Тип элемента reference Тип l-значения элемента; то же, что и value_type& const_reference Тип константного l-значения элемента; аналог const value_type& Конструкторы С с; Стандартный конструктор, создающий пустой контейнер С c1(c2); Создает контейнер c1 как копию контейнера c2 С c(b, е); Копирует элементы из диапазона, обозначенного итераторами b и е (недопустимо для массива) C c{а, b, c...}; Списочная инициализация контейнера с Присвоение и замена c1 = c2 Заменяет элементы контейнера c1 элементами контейнера c2 c1 = {a, b, c...} Заменяет элементы контейнера c1 элементами списка (недопустимо для массива) a.swap(b) Меняет местами элементы контейнеров а и b swap(а, b) Эквивалент a.swap(b) Размер c.size() Возвращает количество элементов контейнера c (недопустимо для контейнера forward_list) c.max_size() Возвращает максимально возможное количество элементов контейнера с c.empty() Возвращает логическое значение false, если контейнер c пуст. В противном случае возвращает значение true Добавление/удаление элементов (недопустимо для массива) Примечание: интерфейс этих функций зависит от типа контейнера c.insert(args) Копирует элемент(ы), указанный параметром args, в контейнер c c.emplace(inits) Использует параметр inits для создания элемента в контейнере с c.erase(args) Удаляет элемент(ы), указанный параметром args, из контейнера c c.clear() Удаляет все элементы из контейнера c; возвращает значение void Операторы равенства и отношения ==, != Равенство допустимо для контейнеров всех типов <, <=, >, >= Операторы отношения (недопустимы для неупорядоченных ассоциативных контейнеров) Получения итераторов c.begin(), c.end() Возвращают итератор на первый и следующий после последнего элемент в контейнере с c.cbegin(), c.cend() Возвращают const_iterator Дополнительные члены реверсивных контейнеров (недопустимы для forward_list) reverse_iterator Итератор, обеспечивающий доступ к элементам в обратном порядке const_reverse_iterator Реверсивный итератор, не позволяющий запись в элементы с.rbegin(), c.rend() Возвращает итератор на последний и следующий после первого элементы контейнера c c.crbegin(), c.crend() Возвращают итератор const_reverse_iterator

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