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); //то же самое, только в случае выхода за пределы вектора кидается исключение out_of_range
v.erase(it); //удаление элемента по итератору (о них будет рассказано далее)

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

vector<vector<int> > g;

deque

#include <deque>
std::deque<int> d;
d.push_back(10);
d.push_front(7);
// + методы, присущие vector

Итераторы

При работе с непрерывными массивами мы использовали указатели с операциями *p и ++p. У контейнеров для таких целей применяются итераторы.

vector<int> v(100, 0);
vector<int>::iterator it = v.begin();
for (; it != v.end(); ++it)
  *it = 5;

Если заменить вектор на другой контейнер, последний цикл будет работать по-прежнему (с учётом того, что такой конструктор есть тольео у вектора).

Замечание: В условии цикла разумно использовать именно оператор !=, а не <, поскольку последний определён не для всех итераторов.

list

#incude <list>
std::list<int> l;
l.push_back(7);
//и другие аналогичные методы

Использование итераторов

Вставка в список производится по итераторам:

v.insert(v.begin() + 5, 10); //вставить 10 на 5-ю позицию
v.end(); //указывает на элемент после последнего!

Рассмотрим простой пример:

|1|2|3|4|5|6|7|8|9|

v.begin() + 5 указывает на 6. Если от него получить итератор, который бежит в обратном направлении, он будет указывать на 5. Поэтому итератор удобнее рассматривать как указывающий на промежуток, а не на конкретный элемент.

Различные замечания

• l.size() в большинстве реализаций работает за О(1).
• В deque удаление и добавление в начало и конец работают за О(1).
• vector не умеет уменьшаться, он только растёт.

v.clear(); //v.erase(v.begin(), v.end());
//чтобы действительно очистить буфер, надо:
vector<int>().swap(v);
//чтобы заменить, немного иначе:
vector<int>(v).swap(v);

• При расширении массивов могут возникнуть проблемы, а именно, инвалидация итераторов. Можно использовать:

v.reserve(100); //зарезервировать размер буфера, равный 100
v.reserve(v.size() + 100); 
v.capacity; //размер буфера

• Инвалидация может так же произойти и при удалении элементов (итератор будет указывать не на тот элемент, который ожидается). Ниже приведены два примера правильной работы с итераторами:

//удаляем все элементы, кратные 2
for (it = v.begin(); it != v.end(); ) {
  if (*it % 2)
    v.erase(it);
  else
    ++it;
}
//вставим перед элементами, кратными 2, новые элементы, равные 0
for (it = v.begin(); it != v.end(); ++it) {
  if (*it % 2) {
    it = v.insert(it, 0);
    ++it;
  }
}

string

typedef basic_string<char> string;
typedef basic_string<wchar> wstring;

Стратегия cow (copy on write) позволяет выиграть при копировании.

Для const объектов есть const_iterator.

Строки на самом деле имеют три параметра в конструкторе. Один из них - аллокатор, отвечает за распределение памяти, и другой - chartrait, определяет механизм сравнения строк.

Код в стиле С

• s.c_str(); возвращает строку в стиле С.
• string(str); конструирует строку в стиле С++ от строки в стиле С.
• &v[0]; v.size(); возвращают указатель на начало массива и его длину.
• vector|list|deque<int>(p, p+size); конструируют вектор, список или деку соответственно от массива.