План

1. Стандартная библиотека языка программирования.
2. Общие сведения и состав стандартной библиотеки шаблонов.
3. Библиотека контейнеров. Адаптеры контейнеров.
4. Библиотека итераторов. Адаптеры итераторов.
5. Библиотека алгоритмов.
6. Достоинства и недостатки стандартной библиотеки шаблонов.

Стандарт

Стандарт (англ. standard) - норма, образец, эталон, уровень; шаблон, штамп, трафарет ...

Вольная трактовка: стандарт – это согласованный метод выполнения чего-либо.

Стандартный

1. Соответствующий стандарту, типовой.
2. перен. Ничем не характерный, трафаретный, шаблонный (разг. неод.).

Толковый словарь Ушакова. Д.Н. Ушаков. 1935-1940.

Что такое стандартная библиотека?

Стандартная библиотека языка программирования — набор модулей, классов, объектов, констант, глобальных переменных, шаблонов, макросов, функций и процедур, доступных для вызова из любой программы, написанной на этом языке и присутствующих во всех реализациях языка.

Примеры стандартных библиотек

• C standard library
• C++ Standard Library
• Framework Class Library (FCL) (.NET Framework)
• Java Class Library (JCL)
• Ruby standard library
• Python standard library
• Go standard library

И другие не вошедшие языки программирования и фреймворки...

Состав стандартной библиотеки

Стандартная библиотека может включать:

• Подпрограммы;
• Определения макросов;
• Глобальные переменные;
• Определения классов;
• Шаблоны.

Большинство стандартных библиотек включают:

• Алгоритмы (например, алгоритмы сортировки);
• Структуры данных (такие как списки, деревья и хэш-таблицы);
• Взаимодействие с хост-платформой, включая ввод/вывод и вызовы операционной системы.

Типовые подходы к проектированию стандартной библиотеки

Стандартная библиотека должна содержать в себе:

• Первый подход — только те процедуры и функции, которые используются практически всеми и обладают максимальной универсальностью. C++: философия "универсальности".
• Второй подход — максимально возможное количество типичных алгоритмов, обеспечивать простую работу с большинством (в идеале, со всеми) объектами, с которыми может взаимодействовать программа. Python: философия "батарейки в комплекте".

Правила стандартной библиотеки

Выдержка из основных руководящих принципов ISO C++.

1. Используйте библиотеки везде, где это возможно

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

2. Предпочитайте стандартную библиотеку другим библиотекам

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

3: Не добавляйте нестандартные объекты в пространство имен std

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

А если не хватает стандартных библиотек?

Гвидо ван Россум (автор языка Python) в документации перечисляет примеры библиотек, которые входят в стандартную библиотеку Python: обработка XML, XML-RPC, сообщений электронной почты и средства локализации. В С++ это не часть стандартной библиотеки, а часть других библиотек, таких как Boost.

Что лучше, универсальность или всеобъемлемость?

При любом варианте имеется проблема роста объема библиотеки

Выдержка из основных руководящих принципов ISO C++:

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

В постоянном поиске качественного контента!

Основано на материале от radioprog.ru, @ashtanyuk и хендбук Яндекса.

Адаптированный материал публикуется с сохранением условий распространения.

Стандартная библиотека шаблонов

Библиотека стандартных шаблонов (STL) (англ. Standard Template Library) — набор согласованных обобщённых алгоритмов, контейнеров, средств доступа к их содержимому и различных вспомогательных функций в C++.

"Русский след" в C++

В ноябре 1993 года Александр Степанов (российско-американский программист) представил библиотеку, основанную на универсальном программировании, комитету ANSI/ISO по стандартизации C++.

Перспективы скорейшего широкого распространения STL значительно улучшились с решением Hewlett-Packard сделать его реализацию свободно доступной в Интернете в августе 1994 года.

Состав библиотеки STL

1. Контейнер (англ. container) — хранение набора объектов в памяти.
2. Итератор (англ. iterator) — обеспечение средств доступа к содержимому контейнера.
3. Алгоритм (англ. algorithm) — определение вычислительной процедуры.
4. Адаптер (англ. adaptor) — адаптация компонентов для обеспечения различного интерфейса.
5. Функциональный объект (англ. functor) — сокрытие функции в объекте для использования другими компонентами.

Контейнеры

Контейнеры предназначены для управления коллекциями объектов определенного типа. У каждой разновидности контейнеров имеются свои достоинства и недостатки.

Итераторы

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

Алгоритмы

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

Обобщенная архитектура STL

Все компоненты стандартной библиотеки С++ располагаются в пространстве имен std. Компоненты STL оформлены в виде шаблонов и поэтому могут использоваться с произвольными типами элементов.

Общие сведения о контейнерах

Контейнеры библиотеки STL можно разделить на два типа:

• последовательные (линейные);
• ассоциативные (нелинейные).

Общие вложенные типы

• Container::value_type;
• Container::iterator;
• Container::const_iterator.

Принципы организации контейнеров

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

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

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

Контейнеры последовательностей

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

Начиная с C++11, STL содержит контейнеров последовательностей: std::array, std::vector, std::deque, std::list и std::forward_list.

Контейнер std::array

Класс array - это контейнеры последовательности фиксированного размера: они содержат определенное количество элементов, упорядоченных в строгой линейной последовательности.

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

Он так же эффективен с точки зрения размера хранилища, как и обычный массив, объявленный с помощью синтаксиса языковых скобок ([]).

#include <array>
#include <iostream>
#include <iterator>
#include <string>

int main() {
  std::array<int, 3> a1{{1, 2, 3}};  // Особенность стандарта C++11
  std::array<int, 3> a2 = {1, 2, 3};  // Результат пересмотра стандарта в C++14
  std::array<std::string, 2> a3 = {std::string("a"), "b"};

  std::sort(a1.begin(), a1.end());
  std::reverse_copy(a2.begin(), a2.end(),
                    std::ostream_iterator<int>(std::cout, " ")); // В консоли: 3 2 1 
  std::cout << '\n';

  for (const auto& s : a3) std::cout << s << ' '; // В консоли: a b 
}

Контейнер std::vector

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

Класс vector обеспечивает произвольный доступ к своим элементам через operator[], а вставка и удаление элементов с конца вектора, как правило, происходит быстро.

#include <iostream>
#include <vector>

int main() {
  std::vector<int> vect;
  for (int count = 0; count < 6; ++count)
    vect.push_back(10 - count);  // вставить в конец

  for (int index = 0; index < vect.size(); ++index)
    std::cout << vect[index] << ' ';

  std::cout << '\n';
}

Консольный вывод:

10 9 8 7 6 5

Контейнер std::deque

Класс deque (жарг. дэк, дек от англ. deque — double ended queue; двусторонняя очередь, очередь с двумя концами) - это класс двусторонней очереди, реализованный как динамический массив, который может расти с обоих концов.

P.S. Если что, Ребекка или Киану Ривз поправят

#include <deque>
#include <iostream>

int main() {
  std::deque<int> deq;
  for (int count = 0; count < 3; ++count) {
    deq.push_back(count);  // вставить в конец
    deq.push_front(10 - count);  // вставить в начало
  }

  for (int index = 0; index < deq.size(); ++index)
    std::cout << deq[index] << ' ';

  std::cout << '\n';
}

Консольный вывод:

8 9 10 0 1 2

Контейнер std::list

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

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

#include <iostream>
#include <list>

int main() {
  std::list<int> first;  // пустой список целых чисел
  std::list<int> second(4, 100);  // четыре целых числа со значением 100
  std::list<int> third(second.begin(), second.end());  // повторение second
  std::list<int> fourth(third);  // копирование third

  int myints[] = {16, 2, 77, 29};
  std::list<int> fifth(myints, myints + sizeof(myints) / sizeof(int));

  std::cout << "The contents of fifth are: ";
  for (std::list<int>::iterator it = fifth.begin(); it != fifth.end(); it++)
    std::cout << *it << ' ';
  std::cout << '\n';
}

Консольный вывод:

The contents of fifth are: 16 2 77 29 

Некоторые общие наблюдения по контейнерам

• Контейнеры копируют структуры, очень часто используемые в программировании: динамические массивы (vector), очереди (queue), стеки (stack), кучи (priority_queue), связанные списки (list), деревья (set), ассоциативные массивы (map)...
• Многие контейнеры имеют несколько общих функций-членов и совместно используют функциональные возможности.
• Решение о том, какой тип контейнера использовать для конкретных нужд, как правило, зависит не только от функциональности, предлагаемой контейнером, но и от эффективности некоторых его элементов (сложности).

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

Ассоциативные контейнеры – это контейнеры, которые автоматически сортируют свои входные данные, когда эти входные данные вставляются в контейнер. По умолчанию ассоциативные контейнеры сравнивают элементы с помощью operator<.

Ассоциативные контейнеры автоматически сортируют свои элементы по некоторому критерию. Критерий представляется в виде функции, которая сравнивает либо значения, либо специальные ключи, определяемые для этих значений.

• set (набор) – это контейнер, в котором хранятся уникальные элементы, дублирование которых запрещено. Элементы отсортированы по их значениям.
• multiset – это set, в котором разрешены повторяющиеся элементы.
• map (также называемый ассоциативным массивом) – это набор, в котором каждый элемент представляет собой пару, называемую парой ключ/значение. Ключ используется для сортировки и индексации данных и должен быть уникальным. Значение – это фактические данные.
• multimap (также называемый словарем) – это map, который позволяет дублировать ключи. Реальные словари – это multimap'ы: ключ – это слово, а значение – это значение слова. Все ключи отсортированы в порядке возрастания, и вы можете искать значение по ключу. Некоторые слова могут иметь несколько значений, поэтому словарь – это multimap, а не map.

В тоже время существуют неупорядоченные ассоциативные контейнеры: unordered_set, unordered_multiset, unordered_map и unordered_multimap.

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

#include <iostream>
#include <map>

bool fncomp(char lhs, char rhs) { return lhs < rhs; }

struct classcomp {
  bool operator()(const char& lhs, const char& rhs) const { return lhs < rhs; }
};

int main() {
  std::map<char, int> first;
  first['a'] = 10; first['b'] = 30; first['c'] = 50; first['d'] = 70;

  std::map<char, int> second(first.begin(), first.end());
  std::map<char, int> third(second);
  std::map<char, int, classcomp> fourth;  // класс для сравнения

  bool (*fn_pt)(char, char) = fncomp;
  std::map<char, int, bool (*)(char, char)> fifth(fn_pt); // указатель функции для сравнения
}

Адаптеры контейнеров

Адаптеры контейнеров – это специальные предопределенные контейнеры, адаптированные для конкретных целей.

Интересная особенность адаптеров контейнеров заключается в том, что можно выбрать, какой контейнер последовательности использовать.

Адаптер std::stack

Класс stack (стек) – это контейнер, в котором элементы работают по принципу LIFO ("last in, first out", "последним вошел, первым вышел"), где элементы вставляются (push) и удаляются (pop) из конца контейнера.

Стеки в качестве контейнера последовательности по умолчанию используют deque (что кажется странным, поскольку вектор кажется более естественным), но также могут использовать vector или list.

Базовое использование стека:

#include <iostream>
#include <stack>

int main() {
  using namespace std;

  stack<string> languages;

  languages.push("C++");
  languages.push("Java");
  languages.push("Python");

  cout << languages.top();
}

Использование иных контейнеров последовательностей:

#include <iostream>
#include <list>
#include <stack>
#include <vector>

int main() {
  using namespace std;
  stack<char> dsc1;
  stack<char, deque<char> > dsc2;
  stack<int, vector<int> > vsi1;
  stack<int, list<int> > lsi;

  vector<int> v1;
  v1.push_back(1);
  stack<int, vector<int> > vsi2(v1);
  cout << "The element at the top of stack vsi2 is " << vsi2.top() << "."
       << endl;
}

Адаптер std::queue

Класс queue (очередь) – это контейнер, в котором элементы работают по принципу FIFO ("first in, first out", "первым вошел, первым вышел"), где элементы вставляются (push) в конец контейнера и удаляются (pop) спереди.

Очереди по умолчанию используют deque (двухстороннюю очередь), но также могут использовать list.

Адаптер std::priority_queue

Класс priority_queue (очередь с приоритетом) – это тип очереди, в которой элементы хранятся отсортированными (с помощью operator<). Когда элемент вставляется, он сортируется в этой очереди.

Удаление элемента спереди возвращает элемент с наивысшим приоритетом в очереди с приоритетом.

Итератор

Итератор – это объект, который может перемещаться по контейнерному классу, при этом пользователю не нужно знать, как реализован этот контейнер.

Для многих классов итераторы являются основным способом доступа к элементам.

Итератор лучше всего представить себе как указатель на заданный элемент в контейнере с набором перегруженных операторов для предоставления набора четко определенных функций:

• operator* – разыменование итератора возвращает элемент, на который итератор в данный момент указывает;
• operator++ – перемещает итератор к следующему элементу в контейнере. Большинство итераторов также предоставляют operator-- для перехода к предыдущему элементу;
• operator== и operator!= – базовые операторы сравнения, чтобы определить, указывают ли два итератора на один и тот же элемент;

• operator= – присваивание итератору новой позиции (обычно в начало или в конец элементов контейнера).

Каждый контейнер включает четыре основные функции-члена для использования с operator=:

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

• cbegin() возвращает константный (только для чтения) итератор, представляющий начало элементов в контейнере;
• cend() возвращает константный (только для чтения) итератор, представляющий элемент сразу за концом элементов.

Все контейнеры предоставляют (как минимум) два типа итераторов:

• container::iterator предоставляет итератор для чтения/записи;
• container::const_iterator предоставляет итератор только для чтения.

Пример итерации по контейнеру set

#include <iostream>
#include <set>

int main() {
  std::set<int> myset;
  myset.insert(7);  myset.insert(2); myset.insert(-4);

  std::set<int>::const_iterator it;  // объявляем итератор
  it = myset.cbegin();  // присваиваем ему начало набора
  while (it != myset.cend()) 
  {
    std::cout << *it << " "; 
    ++it; 
  }
  std::cout << '\n';
  // Консольный вывод: -4 2 7
}

Инвалидация итераторов

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

• Удаление делает некорректным итератор на удалённый элемент в любом контейнере.
• В vector добавление потенциально инвалидирует все итераторы (может произойти выделение нового буфера), иначе инвалидируются только итераторы на все следующие элементы.
• В vector удаление элемента инвалидирует итераторы на все следующие элементы.
• В deque удаление/добавление инвалидирует все итераторы, кроме случаев удаления/добавления первого или последнего элементов.

Адаптеры итераторов

Адаптеры итераторов - классы, которые обладают интерфейсом итератора, но делают нечто совершенно иное. Существуют три вида итераторных адаптеров: обратные итераторы, потоковые итераторы, итераторы вставки. Подробнее здесь.

Алгоритмы

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

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

Чтобы использовать любой из алгоритмов STL, просто включите заголовочный файл algorithm.

Алгоритмы min_element и max_element

Алгоритмы min_element и max_element находят минимальный и максимальный элементы в объекте контейнерного класса. std::iota генерирует непрерывную последовательность значений.

#include <algorithm>  // std::min_element и std::max_element
#include <iostream>
#include <list>
#include <numeric>  // std::iota

int main() {
  std::list<int> li(6);
  // Заполняем li числами, начиная с 0.
  std::iota(li.begin(), li.end(), 0);

  std::cout << *std::min_element(li.begin(), li.end()) << ' '
            << *std::max_element(li.begin(), li.end()) << '\n';
  // Консольный вывод: 0 5
}

Алгоритмы sort и reverse

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
  std::vector<int> vect{7, -3, 6, 2, -5, 0, 4};,

  std::sort(vect.begin(), vect.end());
  for (int i : vect) std::cout << i << ' '; // Вывод: -5 -3 0 2 4 6 7
  std::cout << '\n';

  std::reverse(vect.begin(), vect.end());
  for (int i : vect) std::cout << i << ' '; // Вывод: 7 6 4 2 0 -3 -5
  std::cout << '\n';
}

Достоинства и недостатки STL

Обсудим достоинства и недостатки STL, предложенные коллегами.

Достоинства

• Каждый контейнер обеспечивает стандартный интерфейс в виде набора операций, так что один контейнер может использоваться вместо другого, причем это не влечет существенного изменения кода.
• Дополнительная общность использования обеспечивается через стандартные итераторы.

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

Недостатки

• Контейнеры не имеют фиксированного стандартного представления. Они не являются производными от некоторого базового класса. Это же верно и для итераторов. Использование стандартных контейнеров и итераторов не подразумевает никакой явной или неявной проверки типов во время выполнения.
• Каждый доступ к итератору приводит к вызову виртуальной функции. Эти затраты по сравнению с вызовом обычной функции могут быть значительными.
• Предотвращение выхода за пределы контейнера попрежнему возлагается на программиста, при этом каких-то специальных средств для такого контроля не предлагается.

Добро пожаловать в удивительный мир...

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

• HP — фактически, референсная реализация самого А. Степанова;
• Dinkumware — легла в основу STL от Microsoft;
• SGI — легла в основу GCC.

Правильная и эффективная реализация компонента STL — весьма непростая задача и обширная тема.

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

Все они в итоге приведут к эффективности на определенной платформе и увеличению производительности решений (или нет ).

На десерт

Строка std::basic_string не рассматривается стандартом как контейнер, но ведет себя очень похоже на него из-за своего сходства.

С ней можно работать через итераторы, а также есть свой аналог адаптеров - представление.

Вопросы?

If not, just clap your hands!