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

Контейнеры STL

Проще всего начать знакомство с STL со стандартных типов для хранения данных -- контейнеров.

Каждый раз, когда в программе возникает необходимость оперировать множеством элементов, в дело вступают контейнеры. Контейнер -- это практическая реализация функциональности некоторой структуры данных. В языке C (не в C++) существовал только один встроенный тип контейнера: массив. Сам по себе массив имеет ряд недостатков: к примеру, размер динамически выделенного массива невозможно определить на этапе выполнения.

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

К примеру, нам может потребоваться структура данных «множество строк», поддерживающая следующие функции:
-- добавить строку к множеству;
-- удалить строку из множества;
-- определить, присутствует ли в рассматриваемом множестве данная строка;
-- узнать количество различных строк в рассматриваемом множестве;
-- просмотреть всю структуру данных, «пробежав» все присутствующие строки.

Конечно, легко запрограммировать тривиальную реализацию функциональность подобной структуры данных на базе обычного массива. Но такая реализация будет крайне неэффективной. Для достижения приемлемой производительности имеет смысл реализовать хэш-таблицу или сбалансированное дерево, но задумайтесь: разве реализация подобной структуры данных (хэш либо дерево) зависит от типа хранимых объектов? Если мы потом захотим использовать ту же структуру не для строк, а, скажем, для точек на плоскости -- какую часть кода придётся переписывать заново?

Реализация подобных структур данных на чистом C оставляла программисту два пути.

1) Жёсткое решение (Hard-Coded тип данных). При этом изменение типа данных приводило к необходимости внести большое число изменений в самых различных частях кода.

2) По возможности сделать обработчики структуры данных независимыми от используемого типа данных. Иными словами, использовать тип void* везде, где это возможно.

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

Шаблоны (Templates) в C++ предоставляют замечательную возможность реализовать контейнер один раз, формализовать его внешние интерфейсы, дать асимптотические оценки времени выполнения каждой из операций, а после этого просто пользоваться подобным контейнером с любым типом данных. Можете быть уверены: разработчики стандарта C++ так и поступили. В первой части курса мы на практике познакомимся с основными концепциями, положенными в основу контейнеров C++.

Первые шаги

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

#include <stack>

Типы контейнеров, а также алгоритмы, функторы, да и вообще вся библиотека STL определены не в глобальном пространстве имён. Ввиду большого количества зарезервированных слов в STL, все они вынесены в отдельное пространство имён, получившее название std.

Существует несколько способов пользоваться ключевыми словами из пространства имён std. Универсального, стопроцентно пригодного на все случаи жизни решения искать не следует, у каждого метода есть свои преимущества и недостатки. Перечислим их.

1. Добавить строку

   using namespace std;
   

   непосредственно после всех подключаемых (#include) файлов.

   Это решение плохо тем, что в STL есть ряд достаточно простых зарезервированных слов (например, swap, set, find, count), и подобное подключение пространства имён std потребует от программиста аккуратности в выборе названий для своих классов и функций. Тем не менее, если вы поставили себе целью овладеть STL в совершенстве, автор рекомендует использовать подключение пространства имён std именно в таком формате.

2. Подключить желаемые модули STL отдельными директивами using:

      using std::stack;
      using std::find;
   

3. Использовать директиву typedef для каждого используемого типа:

      typedef std::vector<int> VI;
   

4. Писать префикс std:: перед каждым STL типом данных либо алгоритмом.

Кроме того, не следует забывать про «особенность» парсеров компиляторов C++ в части описания шаблонов. Как вы помните, параметры шаблонов перечисляются в угловых скобках. При этом, две подряд идущих угловых скобки большинство трансляторов (совершенно справедливо) воспринимают как операцию «<<» или «>>». Поэтому, при наличии в коде вложенных STL конструкций следует не забывать оставлять между ними пробельный символ. Пример:

// Нехорошо: две закрывающих угловых скобки подряд
vector<vector<int>> WrongDefinition; 

// ОК 
vector< vector<int> > RightDefinition;

Забегая вперёд, следует заметить, что один из наиболее удачных способов борьбы с подобными ошибками -- использование typedef. Повторяя предыдущий пример:

typedef vector<int> vi;
typedef vector<vi> vvi;

Линейный контейнер vector

Простейшим контейнером STL является vector. Это всего лишь обычный (C-like) массив с расширенной функциональностью. Контейнер vector -- единственный в STL обратно-совместимый с чистым C контейнер. Это означает, что vector по сути дела и является обычным динамическим массивом, но с рядом дополнительных функций.

Знакомство с vector начнём с примеров:

#include <vector>

using namespace std;

vector<int> v(10);

for(int i = 0; i < 10; i++) {
   v[i] = (i+1)*(i+1);
}

for(int i = 9; i > 0; i--) {
   v[i] -= v[i-1];
}

Далее в этом тексте директивы #include и using будут опускаться.

Мы видим, что при описании контейнера типа vector сразу после ключевого слова vector в угловых скобках -- в качестве шаблонного параметра -- указывается тип данных.

Когда в программе встречается описание следующего вида

vector<int> v;

на самом деле создаётся пустой вектор. Будьте внимательны с конструкциями вроде

vector<int> v[10];

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

Вектор всегда может сказать свой текущий размер:

int elements_count = v.size();

Здесь следует сделать два замечания. Первое заключается в том, что согласно стандарту STL все методы, возвращающие размер контейнера, имеют беззнаковый тип. Это чревато не только надоедливыми предупреждениями о приведении и сравнении знакового и беззнакового типов, но и более серьёзными проблемами. Поэтому, в экстремальном программировании, автор рекомендует использовать простой макрос, который возвращает тип контейнера в «обычном» знаковом целом типе.

#define sz(c) int((c).size())

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

Второе замечание состоит в следующем: конструкция вида c.size() == 0 является признаком дурного тона в STL. Если следует определить, не пуст ли контейнер, следует использовать специальный метод empty(), определённый для каждого контейнера.

// Подобного кода следует избегать.
bool is_nonempty_notgood = (Container.size() >= 0); 

// ОК 
bool is_nonempty_ok = ! Container.empty();

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

Также с векторами широко используется функция push_back(x). Метод push_back(x) добавляет элемент в конец вектора, расширяя его на один элемент. Поясним это на примере:

vector<int> v;
for(int i = 1; i < 1000000; i *= 2) {
    v.push_back(i);
}
int elements_count = v.size(); 
// Здесь, кстати, мы получим предупреждение 
// о signed/unsigned mismatch

При использовании метода push_back(x) не следует беспокоиться за лишние операции выделения памяти. Конечно же, вектор не будет расширяться на один элемент при вызове push_back(x). Если о чём и следует беспокоиться при использовании push_back(x) -- так это об объёме используемой памяти. В большинстве реализаций STL использование push_back(x) может привести к тому, что занятый вектором объём памяти будет в два раза превосходить реальную потребность. О методах работы с памятью для векторов и о способах эффективного их использования мы ещё поговорим ниже.

Если хочется изменить размер вектора, используется метод resize(n):

vector<int> v(20);

for(int i = 0; i < 20; i++) {
    v[i] = i+1;
}

v.resize(25);

for(int i = 20; i < 25; i++) {
    v[i] = i*2;
}

После вызова метода resize(n) вектор будет содержать ровно n элементов. Если параметр n меньше, чем размер вектора до вызова resize(n), то вектор уменьшится и «лишние» элементы будут удалены. Если же n больше, чем размер вектора, то вектор увеличит свой размер и заполнит появившиеся элементы нулями. Если хранимым типом данных является более сложный объект, нежели стандартный тип данных новые элементы будут инициализированы конструктором по умолчанию.

Важно помнить, что если использовать push_back(x) после resize(n), то элементы будут добавлены после области, выделенной resize(n), а не в неё. В нижеприведённом примере, после выполнения данного фрагмента кода, размер вектора будет равен 30, а не 25.

vector<int> v(20);
for(int i = 0; i < 20; i++) {
	v[i] = i+1;
}
v.resize(25);
for(int i = 20; i < 25; i++) {
    v.push_back(i*2); // Запись производится в элементы 
                      // [25..30), а не [20..25) !
}

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

Существует много способов инициализировать вектор при создании.

Вектор можно создать как копию другого вектора:

vector<int> v1;
...
vector<int> v2 = v1;
vector<int> v3(v1);

Если вы хорошо знакомы с C++, то понимаете, что v2 и v3 инициализируются абсолютно идентично.

Как мы уже говорили, можно создать вектор желаемого размера:

vector<int> Data(1000);

В данном примере Data будет содержать тысячу нулей. Не забывайте об использовании круглых, а не квадратных скобок.

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

vector<string> names(20, "Unknown");

Как вы, конечно, помните, вектор может содержать любой тип данных, а не только int. string -- это стандартный контейнер для строки в STL, о нём мы поговорим чуть позже.

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

vector< vector<int> > Matrix; 
// Помните о лишних пробелах между угловыми скобками!

Сейчас вам должно быть понятно, как указать размер матрицы при создании:

int N, M;
...
vector< vector<int> > Matrix(N, vector<int>(M, -1));

Вышеприведённая конструкция создаёт матрицу с N строками и M столбцами. Изначально матрица будет заполнена значениями -1.

При использовании векторов следует помнить об одной очень важной особенности работы с памятью в STL. Основное правило здесь можно сформулировать таким образом: контейнеры STL всегда копируются при любых попытках передать их в качестве параметра.

Таким образом, если вы передаёте вектор из миллиона элементов функции, описанной следующим образом:

void some_function(vector<int> v) { 
   // Старайтесь никогда так не делать
   ...
}

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

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

void some_function(const vector<int>& v) { 
   // OK
   ...
}

Если содержимое контейнера может измениться по ходу работы функции, то модификатор const писать не следует:

int modify_vector(vector<int>& v) { 
   // Так держать
   v[0]++;
}

Правило копирования данных применимо ко всем контейнерам STL без исключения.

Также следует отметить, что если объекты, хранимые в контейнере, имеют некоторый физический смысл и/или связаны с другими объектами, следует задуматься об использовании не контейнера из объектов, а контейнера из указателей на объекты. Хорошим критерием здесь может служить следующее правило: всегда ли можно создать новый экземпляр моего класса при помощи конструктора по умолчанию? В случае любых сомнений при ответе на этот вопрос не следует «разбрасываться» объектами. Следует пользоваться контейнерами из указателей. Хорошим решением при этом будет использование контейнеров, содержащих умные указатели (smart pointers), но и поддержание отдельного массива (вектора) созданных объектов -- тоже достаточно грамотное решение.

Часто используется функция vector::reserve(n). Как уже было сказано, вектор не выделяет по одному новому элементу в памяти на каждый вызов push_back(). Вместо этого, при вызове push_back(), вектор выделяет больше памяти, чем реально требуется. В большинстве реализаций при необходимости выделить лишнюю память, vector увеличивает объём выделенной памяти в два раза. На практике это бывает не очень удобно. Наиболее простой способ обойти эту проблему заключается в использовании метода reserve. Вызов метода vector::reserve(size_t n) выделяет дополнительную память в будущее пользование vector. Параметр n имеет следующий смысл: вектор должен выделить столько памяти, чтобы вплоть до размера в n элементов дополнительных операций выделения памяти не потребовалось.

Рассмотрим следующий пример. Пусть имеется vector из 1 000 элементов, и пусть объём выделенной им памяти составляет 1 024 элемента. Мы собираемся добавить в него 50 элементов при помощи метода push_back(). Если вектор расширяется в два раза, его размер в памяти по завершении этой операции будет составлять 2 048 элементов, т. е. почти в два раза больше, чем это реально необходимо. Однако, если перед серией вызовов метода v.push_back(x) добавить вызов

v.reserve(1050);

то память будет использоваться эффективно. Если вы активно используете push_back(), то reserve() -- ваш друг.

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

Пары объектов (pair)

В качестве введения к данной лекции поговорим о «парах» объектов в STL -- std::pair.

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

template<typename T1, typename T2> struct pair {
   T1 first;
   T2 second;
};

К примеру, pair<int,int> есть пара двух целых чисел. Более сложный пример: pair<string, pair<int,int> > -- строка плюс два целых числа. Использовать подобную пару можно, например, так:

pair<string, pair<int,int> > P;
string s = P.first; // Строка
int x = P.second.first; // Первое целое
int y = P.second.second; // Второе целое

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

Сравнение пар предоставляет широкие возможности для экстремального программирования. Массив пар можно упорядочить, при этом упорядочивание будет производиться по полям в порядке описания пар слева направо.

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

vector< pair<double, pair<int,int> >

где double -- полярный угол точки, а pair<int,int> -- её координаты. После этого один вызов стандартной функции сортировки приведёт к тому, точки будут упорядочены по полярному углу.

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

Итераторы

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

Рассмотрим следующую задачу. Дан массив A длины N. Необходимо изменить порядок следования элементов в нём на обратный («развернуть массив на месте»).

Начнём издалека, с решения на чистом C.

void reverse_array_simple(int *A, int N) {
   // индексы элементов, которые мы 
   // на данном шаге меняем местами
   int first = 0, last = N-1; 
   while(first < last) { // пока есть что переставлять
      // swap(a,b) --- стандартная функция STL
      swap(A[first], A[last]); 
      first++; // смещаем левый индекс вправо
      last--; // а правый влево   
   }
}

Пока ничего сложного в этом коде нет. Его легко переписать, заменив индексы на указатели:

void reverse_array(int *A, int N) {
   int *first = A, *last = A+N-1;
   while(first < last) {
      swap(*first, *last);
      first++;
      last--;
   }
}

Рассмотрим основной цикл данной функции. Какие операции над указателями он выполняет? Всего лишь следующие:

*

сравнение указателей (first < last),

*

разыменование указателей (*first, *last),

*

инкремент и декремент указателя (first++, last-)

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

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

Обратим теперь внимание на то, что второй вариант функции, который использует указатели, может работать с любыми объектами, которые обеспечивают функциональность указателя. А именно: сравнение, разыменование, инкремент/декремент. В языке C уже есть удобный, привычный многим и проверенный временем синтаксис для непрямого обращения к данным: нам лишь осталось подставить вместо указателя объект, который умеет делать то же самое.

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

Итак, какую функциональность должен обеспечивать итератор? Примерно ту же, что и обычный указатель:

*

разыменование (int x = *it);

*

инкремент/декремент (it1++, it2-);

*

сравнение (об этом речь пойдёт позже; пока просто скажем, что это операции == и !=)

*

добавление константы (it += 20 -- сдвинуться на 20 элементов вперёд);

*

расстояние между итераторами (int dist = it2-it1);

Язык C++ предоставляет необходимые средства для создания произвольного объекта, который сможет вести себя именно таким образом.

Итак, какую функциональность должен обеспечивать итератор для двусвязного списка, чтобы наша функция reverse_array смогла функционировать? Более узкую, чем указатель, а именно: разыменование, инкремент/декремент, сравнение.

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

*

разыменование (*it);

*

инкремент (++);

*

сравнение (==).

В нашем примере с двусвязным списком, мы также предполагаем, что для его итератора определена операция -. Конечно, о добавлении константы, о сравнении двух итераторов на «больше/меньше» и, тем более, о вычислении разности между итераторами в двусвязном списке не может быть и речи.

В отличие от обычных указателей, итераторы могут также нести много другой полезной нагрузки. В качестве основных примеров, не вдаваясь в подробности, следует отметить проверку выхода за границы массива (Range Checking) и статистику использования контейнера (Profiling).

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

На самом деле, не всем итераторам необходимо поддерживать всю функциональность. В STL пошли по следующему пути: итератор поддерживает те операции, которые он может выполнить за O(1), т. е. независимо от размеров контейнера и параметров. Это означает, к примеру, что для итераторов по двусвязному списку, операции сравнения (<, >) и арифметические операции (it += offset или shift = it2-it1) не применимы. Действительно, время работы этих операций зависит как от размеров контейнера, так и от параметров. С другой стороны, операции сравнения (it1 == it2, it1 != it2), и инкремента/декремента (it1++, it2-), конечно, допустимы.

В свете вышесказанного, итераторы подразделяются по типам:
-- random access iterator: итератор произвольного доступа; умеет всё, что умеет делать указатель, и даже немного больше
-- normal iterator: то же, что итератор произвольного доступа, но не поддерживает арифметические операции <, >, +=, -=, -
-- forward iterator: то же, что normal iterator, но не поддерживает декремент. Пример: односвязный список.

Ввиду того, что итераторы списка нельзя сравнивать при помощи operator <, код функции обращения списка следует модифицировать:

template<typename T> void reverse_list(T *first, T *last) {
   if(first != last) { 
   // точнее, параноик написал бы if(!(first == last))
      while(true) {
         swap(*first, *last);
         first++;
         if(first == last) {
            break;
         }
         last--;
         if(first == last) {
            break;
         }
      }
   }
}

Пришло время вернуться к STL. Каждый контейнер в STL имеет собственный тип итератора, и даже часто не один. Программисту об этом знать не обязательно. Программисту лишь надо помнить, что для любого контейнера определены методы begin() и end(), которые возвращают итераторы начала и конца, соответственно.

Однако, в отличие от вышеприведённого примера, end() возвращает итератор, указывающий не на последний элемент контейнера, а на непосредственно следующий за ним элемент. Это часто бывает удобно. Например, для любого контейнера c разность (c.end() - c.begin()) всегда равна c.size(), если, конечно, итераторы данного типа контейнера поддерживают арифметические операции. А (c.begin() == c.end()) тождественно равно c.empty() -- для любых типов контейнеров.

Таким образом, STL-совместимая версия функции reverse_list приведена ниже.

template<typename T> void 
        reverse_list_stl_compliant(T *begin, T *end) {
   // Сначала мы должны уменьшить end,
   // но только для непустого диапозона
   if(begin != end) 
   {
      end--;
      if(begin != end) {
         while(true) {
            swap(*begin, *end);
            begin++;
            if(begin == end) {
               break;
            }
            end--;
            if(begin == end) {
               break;
            }
         }
      }
   }
}

Теперь эта функция полностью соответствует функции std::reverse(iterator begin, iterator end), определённой в модуле algorithm. В качестве упражнения хотелось бы порекомендовать читателю прочитать и разобрать код функции std::reverse какой-либо из стандартных реализаций STL -- например, SGI или Boost.

Каждый STL контейнер имеет так называемый интервальный конструктор: конструктор, который в качестве параметров принимает два итератора, который задают интервал объектов, тип которых приводим к типу контейнера. Это будет продемонстрировано в следующих примерах.

vector<int> v;
...
vector<int> v2(v);

// интервальный конструктор, v3 == v2
vector<int> v3(v.begin(), v.end()); 

int data[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 };
vector<int> primes(data,data+(sizeof(data)/sizeof(data[0])));

Последняя строка инициализирует vector<int> primes содержимым массива data при помощи интервального конструктора.

Более сложные примеры:

vector<int> v;
...
vector<int> v2(v.begin(), v.begin() + (v.size()/2));

Создаваемый вектор v2 будет содержать первую половину вектора v.

Особо следует выделить тот факт, что в качестве итератора алгоритмам STL можно передавать объекты произвольной природы -- необходимо лишь, чтобы они поддерживали соответствующий функционал. Разберём на примере функции reverse:

int data[10] = { 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 };
reverse(data+2, data+6);
// интервал { 5, 7, 9, 11 } переходит в { 11, 9, 7, 5 };

Кроме того, каждый контейнер имеет также так называемые обратные итераторы -- итераторы, служащие для обхода контейнера в обратном порядке. Обратные итераторы возвращаются методами rbegin()/rend():

vector<int> v;
vector<int> v2(v.rbegin()+(v.size()/2), v.rend());

Вектор v2 содержит первую половину v, в порядке от середины к началу.

Чтобы создать объект типа итератор, следует указать его тип. Тип итератора получается приписыванием к типу контейнера ::iterator, ::const_iterator, ::reverse_iterator или ::const_reverse_iterator. Смысл этих типов уже должен быть понятен слушателю.

Таким образом, содержимое вектора можно просмотреть следующим образом:

vector<int> v;

for(vector<int>::iterator it = v.begin(); it!=v.end(); it++) {
  *it = (*it) * (*it); // возводим каждый элемент в квадрат
}

В условии цикла строго рекомендуется использовать operator !=, а не operator <.

Алгоритмы STL

Теперь мы можем осуществить краткое введение в стандартные алгоритмы STL. Большая часть алгоритмов STL построена по единому принципу. Алгоритм получает на вход пару итераторов -- интервал. Если алгоритм осуществлял поиск элемента, то будет возвращен либо итератор, указывающий на соответствующий элемент, либо конец интервала. Конец интервала уже не указывает ни на какой элемент, что очень удобно.

find(iterator begin, iterator end, some_typy value) осуществляет поиск элемента в интервале. find(...) возвращает итератор, указывающий на первый найденный элемент, либо end, если подходящих элементов найдено не было.

vector<int> v;
for(int i = 1; i <= 100; i++) {
   v.push_back(i*i);
}

if(find(v.begin(), v.end(), 49) != v.end()) {
   // число 49 найдено в списке квадратов натуральных чисел, 
   // не превосходящих 100
}
else {
   // число 49 не найдено
}

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

Если контейнер поддерживает итераторы произвольного доступа, то можно найти индекс найденного элемента. Для это из значения, которое вернул алгоритм, нужно вычесть начало интервала:

int i = find(v.begin(), v.end(), 49) - v.begin();
if(i < v.size()) {
   // 49 найдено
   assert(v[i] == 49);
}

Напомним, что для использования стандартных алгоритмов STL следует подключать модуль algorithm.

Алгоритмы min_element и max_element в пояснениях не нуждаются:

int data[5] = { 1, 5, 2, 4, 3 };
vector<int> X(data, data+5);

// Значение
int v1 = *max_element(X.begin(), X.end()); 

// Индекс
int i1 = min_element(X.begin(), X.end()) - X.begin()); 

int v2 = *max_element(data, data+5); 
// Либо же просто в массиве
int i3 = min_element(data, data+5) - data;

В рамках введения в экстремальное программирование следует присмотреться к следующему макросу:

#define all(c) c.begin(),c.end()

(скобки вокруг правой части здесь ставить ни в коем случае нельзя!)

Также часто используется алгоритм sort(iterator begin, iterator end).

vector<int> X;
...
sort(X.begin(), X.end()); // Стандартный вызов
sort(all(X)); // Почувствуйте разницу
sort(X.rbegin(), X.rend()); // Сортировка в обратном порядке

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

deque<int> q;
...
// Упорядочим элементы в q по неубыванию
vector<int> v(all(q)); 
// то же, что vector<int> v(q.begin(), q.end());
sort(all(v));
q.assign(all(v)); 
// то же, что q = deque<int>(all(v));

Проблемы с компиляцией программ под STL
и их красивое решение в GNU C++

Следует сделать важное замечание о компиляции программ в STL. Дело в том, что STL распространяется в исходных кодах (это существенно влияет на производительность результирующего кода), поэтому зачастую строка с ошибкой будет указывать не на ваш код, а на внутренности STL. При этом строка с описанием ошибки будет занимать несколько сотен символов, что не сразу проливает свет на истинную причину её возникновения. Разберём только один простой пример.

Пусть мы передаём vector<int> как const reference параметр (как это и следует делать) в некую функцию. А в этой функции мы работаем с этим массивом посредством итераторов:

void f(const vector<int>& v) {
    for(
	    vector<int>::iterator it = v.begin(); 
        // ну что же здесь не так
        ...
        ...
}

В этом коротком участке кода есть ошибка. Вы можете её обнаружить?

Дело в том, что из немодифицируемого (const) объекта мы пытаемся получить модифицируемый (non-const) итератор при помощи функции begin(). Подобное преобразование является недопустимым. Корректный код выглядит следующим образом:

void f(const vector<int>& v) {
    int r = 0;
    // используется const_iterator
    for(vector<int>::const_iterator it = v.begin(); 
                                  it != v.end(); it++) {
        r += (*it) * (*it);
    }
    return r;
}

В свете всего вышесказанного, имеет смысл знать про одну очень интересную функцию компилятора GNU C++. Заметим, что данная функция не входит в cтандарт C++, поэтому в большинстве других компиляторов её нет.

Итак, «оператор» typeof(x). На этапе компиляции он заменяется на тип выражения в скобках. Пример:

typeof(a+b) x = (a+b);

Переменная x будет иметь тип, соответствующий типу выражения a+b. Напомним, что typeof(c.size()) -- unsigned int для всех контейнеров STL. Но наибольшую пользу можно извлечь из typeof в следующем контексте:

#define tr(container, iterator) \
  for(typeof(container.begin()) iterator=container.begin(); \
  it != container.end(); it++)

Данный макрос -- сокращение от traverse -- будет работать даже для самого сложного типа контейнера, независимо от того, каким образом этот контейнер к моменту использования определён. Для const-объектов он породит const_iterator'ы:

void f(const vector<int>& v) {
   int r = 0;
   tr(v, it) {
      r += (*it)*(*it);
   }
   return r;
}

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

void operate(const map< set< pair<int,int> >, 
  vector< pair< double, pair<int,int> > > > &object) {
   for( ... ) // MAMMA MIA!
}

Хотя, например, такая операция, как подсчитать сумму всех double из правой части map с использованием макроса tr выполняется сравнительно просто:

void operate(const map< set< pair<int,int> >, 
  vector< pair< double, pair<int,int> > > > &c) {
   double result = 0;
      tr(c, it) {
         tr(it->second, it2) {
            result += it2->first;
         }
      }
   return result;
}

Манипуляции с данными в векторах

Добавление данных в vector выполняется при помощи метода insert. У insert есть несколько форм.

vector<int> v;
...
// Добавить элемент со значением 42 
// непосредственно после первого элемента вектора
v.insert(v.begin() + 1, 42);

При выполнении такой операции:

-- вектор расширится на один элемент;

-- все элементы вектора, начиная со второго (индекс 1) по последний, сместятся вправо, освобождая место для нового элемента;;

-- новый элемент со значением 42 займёт своё место.

Если необходимо добавить много элементов в середину вектора, логично выполнить один сдвиг сразу на несколько элементов. Для этого используется интервальная форма insert: insert(iterator1 where, iterator2 what_begin, iterator2 what_end). При этом типы итераторов iterator1 и iterator2 могут не совпадать -- insert может, к примеру, вставить в vector содержимое контейнера set.

vector<int> v;
vector<int> v2;
...
// вставить содержимое v2 в обратном порядке в середину v
v.insert(v.begin() + (v.size()/2), v2.rbegin(), v2.rend());

Для удаления элементов из vector используется метод erase. У erase также есть две формы:

erase(iterator what);
erase(iterator from, iterator to);

Технология методов insert/erase так или иначе используется во всех типах контейнеров STL.

Контейнер для строк: string

В STL существует специальный контейнер для работы со строками: string. Этот контейнер не очень сильно отличается от vector<char>. Различия, в основном, сосредоточены в функциях для манипулирования строками и в политике работы с памятью. Для того, чтобы узнать длину строки, принято использовать string::length(), а не vector::size().

У строк есть метод substr для быстрого получения подстроки в виде отдельной строки. Этот метод принимает в качестве параметров только индексы, и никаких итераторов:

string s = "hello";
string 
   s1 = s.substr(0, 3), // "hel"
   s2 = s.substr(1, 3), // "ell"
   s3 = s.substr(0, s.length()-1), "hell"
   s4 = s.substr(1); // "ello"

Как и в случае с vector::size(), string::length() возвращает беззнаковый тип. Поэтому будьте аккуратны с конструкциями вроде (s.length()-1): для пустой строки s результат, скорее всего, не оправдает ваших ожиданий.

Также бывает удобным использовать метод string::find(). Он возвращает индекс начала первого вхождения символа или строки.

Кроме string::find, бывает удобно использовать метод string::find_first_of. Если передать в качестве параметра find_first_of один символ, вызов find_first_of будет полностью аналогичен вызову find. Однако, если передать в качестве параметра find_first_of строку, метод вернёт индекс первого вхождения любого символа из данной строки:

string s = "Hello, World!";
int index = s.find_first_of(' '); // поиск первого пробела
int index2 = s.find_first_of(", !"); // поиск первого пробела, 
                               //знака восклицания или запятой

Особенно find_first_of удобно использовать для того, чтобы разделить строку на множество строк. Это актуально, потому как встроенных функций для string splitting в STL, к сожалению, нет.

// разбить строку на вектор строк, 
// используя пробелы и запятые как разделители
vector<string> v;
size_t i;
while((i = s.find_first_of(", ")) != string::npos) {
    // кусок строки до первого разделителя
    v.push_back(s.substr(0, i)); 
    // вырезать вместе с разделителем
    s = s.substr(i+1); 
}
v.push_back(s); // дописать остаток строки

Строки можно складывать с помощью оператора +:

string s = "hello";
string 
    s1 = s.substr(0, 3), // "hel"
    s2 = s + s1; // " helloell"

Строки можно складывать с помощью оператора + и с символами, но нужно быть аккуратными с константными строками. Запись "jdklasj" -- это переменная типа const char*. В большинстве случаев, но не всегда, объекты типа const char* по мере необходимости приводятся к типу string напрямую. Этого не происходит лишь в одном случае: складывать две константных строки нельзя. Для этого нужно привести первую из них к типу string напрямую. Впрочем, если обе строки -- действительно константные, можно просто опустить знак +.

У string нет конструктора от одного char. Для того, чтобы создать строку, состоящую из одного символа, можно либо добавить этот символ к пустой строке (string("") + 'A'), либо использовать инициализацию в стиле vector: string(1, 'B'). Соответственно, таким же образом создаются строки, состоящие из фиксированного числа одинаковых символов.

В общем случае лучше работать с типом string, чем с const char*. Иначе может так случиться, что компилятор подумает совсем не то, что вы имели в виду:

string s = "word", s2;

s = 'S' + s + '!'; // "Sword!"	

s2 = 'A' + " and " + 'B'; 
//таких конструкций следует избегать. фактически здесь мы 
//к числу типа char прибавили указатель, а потом еще раз число

s2 = 'X' + string(" and ") + 'Y'; 
// "X and Y" √-- это корректно

string s3wrong = "p " + " and q "; // не компилируется

string s3 = "p" " and q";  // так можно, 
//но всегда проще написать string("p") +  ' ' + "and q";

Также строки можно сравнивать с помощью операторов сравнения. Таким образом, vector<string> можно упорядочивать стандартными методами. Строки сравниваются в лексикографическом порядке.

Множество элементов: set

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

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

-- добавить элемент в рассматриваемое множество, при этом исключая возможность появления дублей;

-- удалить элемент из множества;

-- узнать количество (различных) элементов в контейнере;

-- проверить, присутствует ли в контейнере некоторый элемент.

Об алгоритмической эффективности контейнера set мы поговорим позже, вначале познакомимся с его интерфейсом.

set<int> s;

for(int i = 1; i <= 100; i++) {
   s.insert(i); // добавим сто первых натуральных чисел
}

s.insert(42); // ничего не произойдёт --- 
   // элемент 42 уже присутствует в множестве

for(int i = 2; i <= 100; i += 2) {
   s.remove(i); // удалим чётные числа
}

// set::size() имеет тип unsigned int
int N = int(s.size()); // N будет равно 50

У set нет метода push_back(). Это неудивительно: ведь такого понятия, как порядок элементов или индекс элемента, в set не существует, поэтому слово «back» здесь никак не применимо.

А раз уж у set нет понятия «индекс элемента», единственный способ просмотреть данные, содержащиеся в set, заключается в использовании итераторов:

set<int> S;
...
// вычисление суммы элементов множества S
int r = 0;
for(set<int>::const_iterator it = S.begin(); 
                            it != S.end(); it++) {
   r += (*it);
}

Если вы пользуетесь GNU C++, то Traversing Macros будет весьма кстати. Показательный пример:

set< pair<string, pair< int, vector<int> > > SS;
...
int total = 0;
tr(SS, it) {
   total += it->second.first;
}

Обратите внимание на синтаксис it->second.first. Ввиду того, что it является итератором, перед использованием его необходимо разыменовать. «Верным» синтаксисом было бы (*it).second.first. Однако, в C++ есть негласное правило, что если при описании некоторого объекта есть возможность обеспечить тождественное равенство конструкций (*it). и it->, то это следует сделать, дабы не вводить пользователей в заблуждение. Разработчики STL, конечно, позаботились об этом в случае с итераторами.

Основным преимуществом set перед vector является, несомненно, быстродействие. В основном это быстродействие проявляется при выполнении операции поиска. (При добавлении операция поиска также неявно присутствует, потому как дубли в set не допускаются). Однако, с операцией поиска в set/map есть существенный нюанс.

Нюанс заключается в том, что вместо глобального алгоритма std::find(...) следует использовать метод set set::find(...).

Это не означает, что std::find(...) не будет работать с set. Дело в том, что std::find(...) ничего не знает о типе контейнера, с которым он работает. Принцип работы std::find(...) крайне прост: он просматривает все элементы до тех пор, пока либо не будет найден искомый элемент, либо не будет достигнут конец интервала. Основное преимущество set перед vector заключается в использовании нелинейной структуры данных, что существенно снижает алгоритмическую сложность операции поиска; использование же std::find(...) ануллирует все старания разработчиков STL.

Метод set::find(...) имеет всего один аргумент. Возращаемое им значение либо указывает на найденный элемент, либо равно итератору end() для данного экземпляра контейнера.

set<int> s;
...
if(s.find(42) != s.end()) {
	// 42 присутствует
}
else {
	// 42 не присутствует
}

Кроме find(...) существует также операция count(...), которую следует вызывать как метод set::count(x), а не как алгоритм std::count(begin, end, x). Ясно, что set::count(x) может вернуть только 0 или 1. Некоторые программисты считают, что вышеприведённый код лучше выглядит, если использовать count(x) вместо find(x):

if(s.count(42) != 0) {
   ...
}

Или даже

if(s.count(42)) {
   ...
}

Мнение автора заключается в том, что подобный код вводит читателя в заблуждение: сам смысл операции count() несовместим со случаями, когда элемент либо присутствует, либо нет. Если же вам предтавляется слишком длинным каждый раз писать "[некоторая форма find]" != container.end(), сделайте следующие макросы:

#define present_member(container, element) \
         (find(all(container),element) != container.end())
#define present_global(container, element) \ 
         (container.find(element) != container.end())

Здесь all(c) означает c.begin(),c.end()

Более того, в соответствии с положением cтандарта, которое называется «конкретизация шаблонов», можно написать следующий код:

template<typename T, typename T2> bool present(const T& c, 
                                            const T2& obj) {
    return find(c.begin(), c.end(), 
              (T::element_type)(obj)) != c.end();
}

template<typename T, typename T2> bool 
                   present(const set<T>& c, const T2& obj) {
    return c.find((T::element_type)(obj)) != c.end();
}

При работе с контейнером типа set present(container, element) вызовет метод set::find(element), в других случаях -- std::find(container.begin(), container.end(), element).

Для удаления элемента из set необходимо вызвать метод erase(...), передав ему один элемент -- элемент, который следует удалить, либо итератор, указывающий на удаляемый элемент.

set<int> s;
...
s.insert(54);
...
s.erase(29);
s.erase(s.find(57));

Как и полагается erase(...), set::erase(...) имеет интервальную форму.

set<int> s;
...
set<int>::iterator it1, it2;
it1 = s.find(10);
it2 = s.find(100);
// Будет работать, если как 10, так и 100 присутствуют в множестве
if(...) {
    s.erase(it1, it2); // при таком вызове будут удалены 
    // все элементы от 10 до 100 не включительно
}
else {
    // сдвинем it2 на один элемент вперёд
    // set::iterator является normal iterator
    // операция += не определена для итераторов set'а, 
    //но ++ и -- допускаются
    it2++;
    s.erase(it1, it2); // а при таком --- от 10 до 100 включительно
    // приведённый код будет работать, даже если 100 был 
    // последним элементом, входящим в set
}

Также, как и полагается контейнерам STL, у set есть интервальный конструктор:

int data[5] = { 5, 1, 4, 2, 3 };
set<int> S(data, data+5);

Кстати, данная функция set предоставляет эффективную возможность избавиться от дубликатов в vector:

vector<int> v;
...
set<int> s(all(v));
vector<int> v2(all(s));

Теперь v2 содержит те же элементы, что и v, но без дубликатов. Приятной особенностью также является тот факт, что элементы v2 упорядочены по возрастанию, но об этом мы поговорим позже.

В set можно хранить элементы любого типа, которые можно упорядочить. Об этом мы тоже поговорим позже.

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

Теперь мы можем перейти от set к map. «Введение в map для чайников» могло бы выглядеть следующим образом:

map<string, int> M;
M["One"] = 1;
M["Two"] = 2;
M["Many"] = 7;

int x = M["One"] + M["Two"];

if(M.find("Five") != M.end()) {
   M.erase("Five");
}

Очень просто, не так ли?

На самом деле, map очень похож на set, за исключением того, что вместо элементов map хранит пары элементов <ключ, значение>. Поиск при этом осуществляется только по ключу. Крайне приятно наличие оператора обращения по «индексу» (operator []).

Для того, чтобы просмотреть содержимое map, необходимо использовать итераторы. Удобнее всего это делать при помощи нашего макроса tr. Следует помнить, что итератор указывает не на элемент key, а на pair<key, value>:

map<string, int> M;
...
M["one"] = 1;
M["two"] = 2;
M["google"] = 1e100;
...
// найдём сумму всех значений --- т.е. всех правых частей 
// пар <string, int>
int r = 0;
tr(M, it) {
   r += it->second; 
   // (*it).first == [string], (*it).second == [int]
}

Как и в случае с set, элементы map хранятся упорядоченными по ключу. Поэтому не следует при работе с map::iterator модифицировать it->first: если вы нарушите правила упорядочивания элементов в map, за последствия никто отвечать не возьмётся.

В остальном контейнер map по интерфейсу практически эквивалентен контейнеру set.

Также важно помнить, что operator [] при обращении к несуществующему элементу в map создаст его. Новый элемент при этом будет инициализирован нулём (либо конструктором по умолчанию, если это не тривиальный тип данных). Данная особенность map может быть удобной, потому как выполнять операции с элементами можно не задумываясь об их присутствии в map. Существенным моментом является то, что operator [] не является константным (то есть может изменить объект, для которого вызван), поэтому им нельзя пользоваться, если map передан как const reference. Используйте map::find(element):

 
void f(const map<string, int>& M) {
   if(M["the meaning"] == 42) { 
     // Так нельзя! M передан как const reference
   }
   if(M.find("the meaning") != M.end() && 
                    M.find("the meaning")->second == 42) { 
      // А можно именно так
      cout << "Don't Panic!" << endl;
   }
}

Литература и ссылки

1. Scott Meyers, Effective STL. Addison Wesley Professional, 2001.

2. http://www.sgi.com

3. http://msdn.microsoft.com