§24 Стандартная библиотека C++ (STD)

Стандартная библиотека C++

Стандартная библиотека C++ (далее – STD) представляет собой большой набор функций и классов для решения различных задач. STD и ядро языка C++ развивались и стандартизировались параллельно. В следствие этого, многие важные вещи, например ввод/вывод, не являются частью ядра, а принадлежат STD. Все компоненты STD согласованы друг с другом, но основаны на разных принципах проектирования. Ядром STD является Библиотека стандартных шаблонов (англ. Standard Template Library). В настоящее время эта библиотека настолько сильно интегрирована в STD и настолько сильно на неё повлияла, что рассматривается как её неотъемлемая часть.
В основу разработки библиотеки стандартных шаблонов (далее – STL) положена парадигма обобщенного программирования. Архитектуру STL разработали Александр Степанов и Менг Ли. STL вошла в стандартную библиотеку C++ весной 1994 года. Компоненты библиотеки стандартных шаблонов имеют ярко выраженные общие принципы проектирования, которые заметно отличают её от других библиотек STD.
STD также включает в себя спецификации стандарта ISO C11 (в версии стандарта C++17) стандартной библиотеки языка Си. Каждый заголовочный файл из стандартной библиотеки языка Си включен в STD под именами, начинающиеся префиксом ‘c’, например, “ctime”.
По правилам языка C++ соответствующий компонент STD добавляется в программу путем включения заголовочного файла с помощью директивы: #include <имя_файла>. При этом обычное “расширение” в имени заголовочных файлов (“.h”) отбрасывается.

Основные компоненты STD:
  • Утилиты
  • Строки
  • Контейнеры
  • Алгоритмы
  • Числа
  • Ввод/вывод
  • Локализация
  • Регулярные выражения
Александр Александрович Степанов

Александр Александрович Степанов

Компоненты STL

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

В STL выделяют пять основных компонентов:

Контейнеры

Контейнеры — это специализированные классы, предназначенные для хранения коллекции однотипных объектов и обеспечения доступа к этим объектам. Контейнер – это структура данных похожая на массив. Контейнер управляет выделяемой для его элементов памятью и предоставляет функции-члены для доступа к ним, либо непосредственно, либо через итераторы. Конструкторы контейнеров имеют дополнительный специальный аргумент allocator (распределитель). Аллокатор инкапсулирует (т. е. скрывает) реализацию выделения и освобождения памяти. Аллокатором по умолчанию является шаблон std::allocator (если не определен пользовательский распределитель). В качестве инструментов выделения и освобождения памяти этот аллокатор использует стандартные операции new и delete. Для различных контейнеров имеются как общие, так и специфичные операции, применимые только для данного вида коллекции объектов. Разные контейнеры обеспечивают различную эффективность тех или иных операций. Выбор оптимального контейнера для конкретного случая зависит не только от предоставляемой функциональности, но и от его эффективности при различных рабочих нагрузках. Контейнеры подразделяются на следующие виды:

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

В последовательных контейнерах элементы располагаются последовательно, один за другим. Позиция зависит от времени и места вставки, но не связана со значением элемента. Каждый элемент контейнера имеет свой индекс (за исключением контейнера list); как и в массивах, отсчет начинается с "0". Но, в отличие от C-массивов, имеющих фиксированный размер, последовательные контейнеры – динамические массивы (за исключением контейнера array). К последовательным контейнерам относятся классы:

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

Ассоциативные контейнеры

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

Класс set (множество) представляет собой упорядоченный контейнер, соответствующий математическому понятию множества. set хранит упорядоченное множество уникальных ключей (или просто – значений).
Класс map (словарь) реализует упорядоченный ассоциативный массив пар элементов, состоящих из уникальных ключей и соответствующих им значений. Контейнеры multiset и multimap допускают существование нескольких ключей с одинаковым значением.
Помимо упорядоченных ассоциативных контейнеров, имеются неупорядоченные структуры данных (хеш-массивы) с возможностью быстрого поиска:

  • unordered_set
  • unordered_map
  • unordered_multiset
  • unordered_multimap
Контейнеры-адаптеры

Контейнеры-адаптеры (container adaptor) — это обёртки над другими контейнерами, предоставляющие особые наборы операций. Оборачиваемый контейнер может быть задан как дополнительный параметр шаблона. Если параметр не задан, будет использоваться, специфический для адаптера, контейнер по умолчанию. К контейнерам-адаптерам относятся:

Контейнер stack (стек) реализует структуру данных в которой элементы добавляются и удаляются в вершине стека (т. е. с одного конца). Массив элементов, организован по принципу LIFO (англ. last in — first out, «последним пришёл — первым вышел»). Контейнер queue (очередь) реализует структуру данных в которой добавление элемента возможно только в конец очереди, а выборка — из начала очереди, при этом выбранный элемент из очереди удаляется.
Контейнер priority_queue (очередь с приоритетами) поддерживает операции, аналогичные классу stack, но вставка элементов предполагает их неявную сортировку, так что операция извлечения элемента извлекает всегда минимальный (или максимальный, если определена соответствующая функция сравнения) элемент коллекции.

Псевдо-контейнеры

Подведем черту упоминанием еще одного типа контейнеров – псевдо-контейнеров. Это особый вид контейнеров, которые созданы для специфичных элементов на основе каркаса для проектирования новых контейнеров, предоставляемого библиотекой стандартных шаблонов. К псевдо-контейнерам относятся:

Интеллектуальные указатели

В контейнерах, для хранения элементов, используется семантика передачи объектов по значению. Другими словами, при добавлении, контейнер получает копию элемента. Следовательно, может возникнуть перерасход памяти. Если создание копии нежелательно, то используют контейнер указателей на элементы. Присвоение элементов реализуется с помощью операции присваивания, а их уничтожение происходит с использованием деструктора. Но в этом таится опасность. Например, не совпадают время жизни объекта и время жизни указателя на этот объект, возникают утечки памяти. Чтобы избежать таких проблем используются интеллектуальные (умные) указатели. “Интеллектуальными” они называются так потому, что позволяют избежать, выше упомянутых, проблем. Однако, они не дают 100% гарантии, что не появятся подобные проблемы в результате непродуманности алгоритма. Существует два основных типа умных указателей:

  • shared_ptr
  • unique_ptr

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

Print Friendly, PDF & Email

Comments are closed.