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

Внимание! В лекции могут содержаться ошибки и неточности. Прошу исправлять по мере обнаружения.

Введение в STL

STL - Standart Template Library. Она стандартизированна. Существует несколько реализаций, в том числе:

• GCC
• MS
• STL Port

В неё входят:

• Контейнеры
• Итераторы
• Алгоритмы

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

Ко всем последовательным контейнерам предъявляются общие требования:

• Copy-constructable (т.е. публичный конструктор копирования).
• Assignable (т.е. публичный оператор присваивания).
• Стандартная семантика.

Разновидности

• vector - массив подряд идущих элементов.
• list - список взаимосвязанных элеметов.
• deque - совокупность связанных в список массивов фиксированной длины + индексная таблица.
• string/wstring - строка.

Для использования этих контейнеров необходимо перед названием типов писать std::.

vector

#include <vector>
using std::vector;
std::vector<int> v;

У шаблона есть и второй параметр - аллокатор. Он отвечает за стратегию распределения памяти. Его использовать не надо!

Основные методы вектора представлены ниже:

v.push_back(13); //добавить элемент к вектору
v.empty(); //вектор пуст?
v.size(); //количество элементов в векторе
v[i]; //обращение к i-му элементу вектора
v.at(i); //то же самое
v.erase(it); //удаление элемента по итератору (о них будет рассказано далее)

Пример хранения структуры графа:

vector<vector<int> > g;

deque

to be continued...