Контейнеры

Библиотека STL имеет в своем арсенале элементы, называемые контейнерами. Контейнеры — это объекты, хранящие в себе другие объекты. В STL таких контейнеров десять:

vector — массив с произвольным доступом, чаще всего применяемый в тех случаях, когда надо последовательно добавлять данные в конец цепочки;

list — похож на вектор, но эффективен при добавлении и удалении данных в любое место цепочки;

deque — дек;

set — набор уникальных элементов, отсортированных в определенном порядке (множество);

multiset — то же, что и set, но может содержать повторяющиеся копии;

map — обеспечивает доступ к значениям по ключам;

multimap — то же, что и map, но допускающий повторяющиеся ключи;

stack — стек;

queue — очередь;

priority queue — приоритетная очередь.

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

Функциональные объекты

Функциональные объекты — это объекты, у которых задан перегруженный оператор вызова функции "operator ()()". Все операторы обычно пишутся как inline, что дает дополнительный выигрыш в скорости.

Функциональными объектами являются все арифметические операторы: сложения (plus), вычитания (addition), умножения (times), деления (divides), взятия остатка (modulus) и обращения знака (negate). Имеются функциональные объекты для вычисления равенства (equal_to), неравенства (not_equal_to), операции "больше" (greater), операции "меньше" (less), операции "больше или равно" (greater_equal), операции "меньше или равно" (less_equal). Для логических операторов имеются свои функциональные объекты: логическое "и" (logical_and), логическое "или" (logical_or) и логическое "не" (logical_not).

Пример. Работа с контейнером vector

Определяем пустой вектор:

vector< int > arr;

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

int i;

for (i=1; i<9; i++) {

arr.push_back(i);

// ...

}

Хотя мы можем использовать операцию взятия индекса для перебора элементов вектора:

cout << "считаны числа: \n";

for ( int ix =0; ix < arr.size(); ++ix )

cout << arr [ ix ] << ' ';

cout << endl;

удобнее использовать итераторы:

cout << "считаны числа: \n";

for ( vector<int>::iterator it = arr.begin();

it != arr.end(); ++it )

cout << *it << ' ';

cout << endl;

Итератор — это класс стандартной библиотеки, фактически являющийся указателем на элемент массива.

Выражение

*it;

разыменовывает итератор и дает сам элемент вектора. Инструкция

++it;

сдвигает указатель на следующий элемент. Не нужно смешивать эти два подхода. Если следовать идиоме STL при определении пустого вектора:

vector<int> ivec;

будет ошибкой написать:

ivec[0] = 1024;

У нас еще нет ни одного элемента вектора ivec; количество элементов выясняется с помощью функцииsize().

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

vector<int> ia( 10 );

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

const int size = 7;

int ia[ size ] = { 0, 1, 1, 2, 3, 5, 8 };

vector< int > ivec( size );

for ( int ix = 0; ix < size; ++ix )

ivec.push_back( ia[ ix ] );

Имелась в виду инициализация вектора ivecзначениями элементовia, вместо чего получился векторivecразмера14.