Стандартная библиотека шаблонов (STL) в C++ — Введение в контейнеры

Современный эффективный C++

Стандартная библиотека шаблонов (STL) в C++ — введение в контейнеры

STL Like a Pro — вводите, разбирайтесь, выбирайте, используйте и визуализируйте контейнеры!

· Overview
  ∘ Why use STL?
· STL Containers
  ∘ Container types
  ∘ Containers Visualized
  ∘ Why use STL Containers?
· Container Specifications
· Sequential Containers
· Choosing the right container
· Conclusion
· References
· Supplemental Material
  ∘ Vectors
  ∘ Deques
  ∘ Stacks
  ∘ Lists and forward lists
  ∘ Demo Code
· Additional Resources: Dig Deeper
· Contact

В рамках изучения Стандартной библиотеки шаблонов (STL) C++ мы приступаем к важнейшему аспекту библиотеки — контейнерам STL. .

К концу этого урока вы поймете следующее.

• Как правильно выбрать контейнер и насколько это важно.
• Типы контейнеров, предлагаемых STL, а также их преимущества и недостатки.
• Выбор наилучшей структуры данных (т. е. контейнера) для заданного алгоритма.

Во-первых, мы познакомимся с контейнерами и их важностью в обеспечении эффективного C++[1].

Читателям, незнакомым с STL, или тем, кто ищет полную историю, настоятельно рекомендуется вернуться к части 1.

Обзор

Как и в Части 1, STL состоит из модулей, изображенных следующим образом:

Где каждый ребенок ведет свой блог. Следовательно, STL в целом будет состоять из нескольких частей.

Зачем использовать STL?

STL предоставляет навороты для фундаментальных алгоритмов и структур данных, принося пользу пользователю.

1. Он хорошо протестирован и оптимизирован.
2. Нет необходимости изобретать велосипед.
3. Это приводит к более короткому и компактному исходному коду.

Примечание: (2) предполагает, что мотивация является практической или решает проблему в области исследований или промышленности. При изучении входов и выходов структур данных (например, стека) полезным упражнением может быть реализация класса без STL; однако я считаю, что есть более эффективные способы изучения этих концепций, а также изучения легкодоступного STL. Например, в рамках вводного курса C++ или самообучения повторная реализация заголовка <string> также входит в ядро ​​C++ (см. Часть 1). Возможно, тема на будущее :)

Кроме того, STL в целом расширяем и эффективен при связывании алгоритмов и структур данных (см. Часть 1).

Отзыв. При наличии M контейнеров и N алгоритмов при исчерпывающем выполнении комбинаций обычно требуется NxM процессов. Однако итераторы лежат в основе философии STL и структуры, сокращая количество операций до N +M. Визуально это можно изобразить следующим образом.

Включите заголовок контейнера, алгоритма,итератора или функтора, при этом последние три подлежат будущему блог.

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

STL-контейнеры

Контейнеры STL — это общие структуры данных с соответствующей функциональностью. Почему бы не реализовать свои собственные — ну, мотивация, указанная в пунктах 1–3 в предыдущем разделе, довольно кратко резюмирует причину. Сошлемся на слова знатока и лидера в технических тонкостях эффективного C++.

They’re simply better than their competition, regardless of whether that competition comes from containers in other libraries or is a container type you’d write yourself. STL containers aren’t just good. They’re really good. 
— Scott Meyers

Типы контейнеров

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

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

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

Визуализация контейнеров

Зачем использовать контейнеры STL?

В своей Modern-Day Effective STL [1] Стив Мейер выбрал следующий пункт для начала своей знаменитой книги.

ℹ️ Item 1. Choose your containers with care.

Как мы увидим, разные контейнеры лучше всего подходят для определенных сценариев. И хотя интерфейс STL является достаточно чистым и согласованным, чтобы легко заменить один тип другим (т. е. как показано в приведенном ниже примере кода), выбор контейнера может существенно повлиять на скорость и ясность исходного кода. Кроме того, алгоритмы не зависят от параметра в контейнере. (т. е. будет рассмотрено, когда мы дойдем до элемента 2 ниже.

Прежде чем приступить к выбору лучшего контейнера, давайте сначала рассмотрим набор контейнеров последовательности.

Характеристики контейнера

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

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

Таким образом, для контейнеров на основе последовательностей:

• array имеет статический размер, а все остальные — динамические.
• последовательности array и array содержат vector и deque соответственно; list и forward_list используют двойные и односвязные списки.
• Только list и forward_list не поддерживают произвольный доступ, а вперед/назад и вперед соответственно.
• Только list и forward_list всегда освобождают память; vector и deque имеют методы shrink_to_fit()Последний иногда освобождает память сам по себе.
• Наконец, vector и list имеют резервирование памяти, а deque и forward_list — нет.

Правильный выбор контейнера

ℹ️ Item 2. Beware the illusion of container-independent code.

Подытожим ситуацию и соответствующий контейнер, который лучше всего выбрать.

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

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

Mai Pham резюмирует сложности Big-O в следующем сообщении в блоге.

Вкратце

💡 Vector, list, and deque offer the programmer different complexity trade-offs and should be used accordingly; the vector is the type of sequence that should be used by default, and a list should be used when there are frequent insertions and deletions from the middle of the sequence, the deque is the data structure of choice when most insertions and deletions take place at the beginning or at the end of the sequence.

Заключение

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

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

Рекомендации

[1] http://www.uml.org.cn/c%2B%2B/pdf/EffectiveSTL.pdf

[2] https://www.abebooks.com/Effective-STL-Specific-Ways-Improve-Use/22536211326/bd

[3] Эффективный современный C++

Дополнительный материал

Векторы

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

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

В качестве примера возьмем std::vector, который похож на другие контейнеры.

std::vectortemplate предоставляет массивы динамического размера на основе кучи без необходимости явного управления памятью.

std::vector v; 
v.push_back(1); 
v.push_back(2); 
v.push_back(3); 
std::cout << v[0] <<‘, ‘<< v[1] <<‘, ‘<< v[2] << std::endl; 
// 1, 2, 3

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

STL предлагает множество конструкторов. Для std::vector являются следующие:

• Конструктор по умолчанию: создает пустой вектор.
• Конструктор копирования: создает копию существующего вектора.
• vector v(N, V): создает вектор с набором элементов N со значениями K.
• vector v(N): создает вектор с N элементами (нулевыми значениями)

Преобразование в массив

Если у вас есть вектор элементов vНо вам нужно передать его при вызове функции void f(int *a) (т. е. принимает указатель на массив элементов *a), как, по-вашему, мы можем это сделать?

Решение:

void f(int *a); 
vector v; 
f(&v[0]);

Пояснение:

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

Деки

std::deque шаблонирует двустороннюю очередь с интерфейсом, аналогичным векторам, но эффективно вставляет и удаляет в начале и в конце структуры данных. push_back() и pop_back(), наряду с большинством других операций std::vector, также доступны для деков; также std::deque предлагают push_front() и pop_front().

💡 Note. Deques are not guaranteed to be implemented internally as contiguous arrays.

Стеки

Шаблон std::stack не является отдельной структурой данных. Это шаблон адаптера — специализированный интерфейс к существующему шаблону.

По умолчанию std::stack реализуется с std::deque, но можно указать использовать std::vectorили std::list.

💡 Note. The pop method does not return the item that was popped. If you want this item, use the top method before the pop method.

Стеки обеспечивают базовые операции со стеком:

stack s; if (!s.empty()) { 
// Test if empty
    std::cout << s.size() << std::endl; // Size of the stack 
} 
s.push(4); // “push” operation 
std::cout << s.top() << std::endl; // top of stack 
s.pop(); // “pop” operation

Списки и переадресованные списки

Контейнеры на основе связанных списков, std::forward_list и std::list, отличаются несколькими важными аспектами. Во-первых, первые содержат только ссылку на следующий элемент, в то время как последние имеют две связи для связи с предыдущим компонентом. Две ссылки эффективно итерируют список в любом направлении, что приводит к дополнительным затратам памяти и небольшим временным затратам при вставке и удалении элементов. Таким образом, объекты forward_list более эффективны, чем объекты list, хотя они итерируются только вперед.

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

Демонстрационный код

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

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

Дополнительные ресурсы: Копайте глубже

STL контейнеры имеют необязательный аргумент (т. е. Allocator()), который позволяет контролировать память (т. е. управлять). Дебби Нирван отлично освещает эту тему.

Абхишек Ратор публикует в блоге практическое руководство, охватывающее все компоненты STL.

Майк Макмиллан подробно изучает STLvector.

Вместе с map и multimap.

Адитья Джейн демонстрирует использование контейнеров STL для реализации структур tree и graph.

Книга Скотта Мейера «Эффективный STL» вдохновила меня на создание этого блога. Вананд Гаспарян очень хорошо отзывается о книге.

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

Контакт

Want to Connect? Follow Dr. Robinson on LinkedIn, Twitter, Facebook, and Instagram. Visit my homepage for papers, blogs, email signups, and more!