Просмотр исходного текста страницы STL. Последовательные контейнеры

'''Внимание!''' В лекции могут содержаться ошибки и неточности. Прошу исправлять по мере обнаружения.
== Введение в STL ==
STL - Standart Template Library. Она стандартизированна. Существует несколько реализаций, в том числе:
* GCC
* MS
* STL Port
В неё входят:
* Контейнеры
* Итераторы
* Алгоритмы

== Последовательные контейнеры ==
Ко всем последовательным контейнерам предъявляются общие требования:
* Copy-constructable (т.е. публичный конструктор копирования).
* Assignable (т.е. публичный оператор присваивания).
* Стандартная семантика.

=== Разновидности ===
* <code>vector</code> - массив подряд идущих элементов.
* <code>list</code> - список взаимосвязанных элеметов.
* <code>deque</code> - совокупность связанных в список массивов фиксированной длины + индексная таблица.
* <code>string/wstring</code> - строка.
Для использования этих контейнеров необходимо перед названием типов писать <code>std::</code>.

=== <code>vector</code> ===
<source lang="cpp">
#include <vector>
using std::vector;
std::vector<int> v;
</source>
У шаблона есть и второй параметр - аллокатор. Он отвечает за стратегию распределения памяти. Его использовать не надо!

Основные методы вектора представлены ниже:
<source lang="cpp">
v.push_back(13); //добавить элемент к вектору
v.empty(); //вектор пуст?
v.size(); //количество элементов в векторе
v[i]; //обращение к i-му элементу вектора
v.at(i); //то же самое
v.erase(it); //удаление элемента по итератору (о них будет рассказано далее)
</source>
Пример хранения структуры графа:
<source lang="cpp">
vector<vector<int> > g;
</source>

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

=== Итераторы ===
При работе с непрерывными массивами мы использовали указатели с операциями <code>*p</code> и <code>++p</code>. У контейнеров для таких целей применяются итераторы.
<source lang="cpp">
vector<int> v(100, 0);
vector<int>::iterator it = v.begin();
for (; it != v.end(); ++it)
  *it = 5;
</source>
Если заменить вектор на другой контейнер, последний цикл будет работать по-прежнему (с учётом того, что такой конструктор есть тольео у вектора).

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

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

=== Использование итераторов ===
Вставка в список производится по итераторам:
<source lang="cpp">
v.insert(v.begin() + 5, 10); //вставить 10 на 5-ю позицию
v.end(); //указывает на элемент после последнего! 
</source>
Рассмотрим простой пример:

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

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

=== Различные замечания ===
# <code>l.size()<//code> в большинстве реализаций работает за О(1).
# В <code>deque</code> удаление и добавление в начало и конец работают за О(1).
# <code>vector</code> не умеет уменьшаться, он только растёт.
<source lang="cpp">
v.clear(); //v.erase(v.begin(), v.end());
//чтобы действительно очистить буфер, надо:
vector<int>().swap(v);
//чтобы заменить, немного иначе:
vector<int>(v).swap(v);
</source> 
# При расширении массивов могут возникнуть проблемы, а именно, инвалидация итераторов. Можно использовать:
<source lang="cpp">
v.reserve(100); //зарезервировать размер буфера, равный 100
v.reserve(v.size() + 100); 
v.capacity; //размер буфера
</source>
# Инвалидация может так же произойти и при удалении элементов (итератор будет указывать не на тот элемент, который ожидается). Ниже приведены два примера правильной работы с итераторами:
<source lang="cpp">
//удаляем все элементы, кратные 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 ===

to be continued...