Структура стандартной библиотеки шаблонов (stl)

Стандартная библиотека шаблонов (Standard Template Library) – это существенная часть стандартной библиотеки С++. Использование STL дает возможность создавать более надежные, более переносимые и более универсальные программы, а также сократить расходы на их разработку.

Ядро стандартной библиотеки шаблонов включает три основных элемента:

контейнеры,

алгоритмы,

итераторы.

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

Контейнеры – это объекты, которые могут хранить множество элементов – объектов некоторого типа.

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

Алгоритмы обрабатывают содержимое контейнеров. Их возмож-ности включают средства инициализации, сортировки, поиска и преобразования содержимого контейнеров.

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

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

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

Вектор – единственный в STL обратносовместимый с чистым C-контейнером. Это означает, что вектор, по сути, дела является обычным динамическим массивом, но с рядом дополнительных функций.

Для доступа к его элементам можно использовать стандартное обозначение индексации массивов. Объектами вектора могут быть как базовые типы переменных (int, float, char и т. д.), так и строки.

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

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

Чтобы использовать вектор в программе, необходимо включить в нее заголовочный файл <vector>:

#include <vector>

Объявление вектора выглядит следующим образом:

vector<тип_элемента> имя; Например,

vector<int> n; n – вектор, который может хранить целые числа.

При объявлении вектора его можно одновременно и инициализировать (табл. 1).

Таблица 1

Способы инициализации векторов

Операция	Описание
vector <Type> v	Создает пустой вектор, не содержащий ни одного элемента
vector<Type> v1(v2)	Создает копию другого вектора того же типа (с копированием всех элементов)
vector<Type> v(n)	Создает вектор из n элементов, создаваемых конструктором по умолчанию
vector<Type> v(n,elem)	Создает вектор, инициализируемый n копиями элемента elem

Здесь Type – тип элементов вектора.

Пример 2

#include <vector>

void main()

{ setlocale(LC_ALL,"rus_rus.1251");

vector<int> v; // Создаем пустой вектор

vector<int> v1(10); // Cоздаем вектор из десяти элементов,

// начальные значения которых равны нулю

for(int i = 0; i < 10; i++) v1[i] = (i+1)*(i+1);//Заполняем вектор v1

vector<int>v3(v1);// Копируем вектор v1 в вектор v3;

v=v3;// Присваиваем элементам вектора v значения элеметов

// вектора v3

cout<<"\nЭлементы вектора v"<<endl;

for(int i = 0; i < 10; i++) cout<<setw(5)<<v[i];

}

Результат

Элементы вектора v

1 4 9 16 25 36 49 64 81 100

Одной из самых замечательных особенностей контейнеров STL является автоматическое наращивание памяти в соответствии с объемом внесенных данных. Чтобы разобраться с этим вопросом, остановимся более подробно на функциях size, capacity и reserve(n) (табл. 2).

Таблица 2

Немодифицирующие операции над векторами

Операция	Описание
v.size()	Возвращает фактическое количество элементов
v.empty()	Возвращает true, если контейнер пуст, и false в противном случае
v.max_size()	Возвращает максимально возможное количество элементов
v.capacity()	Возвращает количество зарезервированной (выделенной) памяти
v.reserve(n)	Резервирует память, необходимую для добавления n элементов в вектор

Функция size возвращает текущее количество элементов в контейнере. Она не сообщает, сколько памяти контейнер выделил для хранящихся в нем элементов.

Функция capacity сообщает, сколько элементов поместится в выделенной памяти. Речь идет об общем количестве элементов, а не о том, сколько еще элементов можно разместить без расширения контейнера. Если size и capacity возвращают одинаковые значения, значит, в контейнере не осталось свободного места, и следующая вставка (insert, push_back и т. д., см. пример 6) даже одного элемента вызовет процедуру перераспределения памяти, которая порой обходится довольно дорого (при больших объемах). Естественно, эту операцию хотелось бы выполнять как можно реже, тем более что при каждом выполнении перечисленных операций все итераторы, указатели и ссылки на содержимое vector становятся недействительными. Для решения этой проблемы надо использовать функцию reserve( n).

Функция reserve( n) устанавливает минимальную емкость контейнера равной n при условии, что n не меньше текущего размера. Таким образом, для предотвращения лишних затрат следует установить достаточно большую емкость контейнера функцией reserve, причем сделать это нужно как можно раньше – желательно сразу же после конструирования контейнера.

Чтобы разобраться с этими тонкостями, рассмотрим пример (пример 3).

Пример 3

vector<int> v; // Создаем пустой вектор

cout<<"Пустой вектор"<<endl;

cout<<"Емкость вектора "<<v.capacity()<<"\nКоличество элементов"

<<v.size()<<endl;

int s = 0;

// Заполняем вектор

for (int i=1; i<=1000; ++i)

{ if(v.size()==v.capacity()) s++;

v.push_back(i);}

cout<<"\nПосле заполнения вектора"<<endl;

cout<<"Емкость вектора "<<v.capacity()<<"\nКоличество элементов" <<v.size()<<endl;

cout<<"Число перерасределения памяти = "<<s<<endl;

cout<<"\nДобавим в конец вектора еще 67 элементов"<<endl;

v.insert(v.end(),67,1);

cout<<"Емкость вектора "<<v.capacity()<<"\nКоличество элементов" <<v.size()<<endl;

Результат

Пустой вектор

Емкость вектора 0

Количество элементов 0

После заполнения вектора

Емкость вектора 1066

Количество элементов 1000

Число перераспределений памяти 18

Добавим в конец вектора еще 67 элементов

Емкость вектора 1599

Количество элементов 1067

Анализ

Как и ожидалось, в пустом векторе число элементов, как и его размер, равны нулю. В процессе заполнения вектора 18 раз произошло перераспределение памяти, т. е. 18 раз происходила процедура, опи-санная выше. В результате размер (емкость) вектора превысил коли-чество элементов в нем на 66 элементов. Предположим, что нам нужно добавить в вектор еще 67 элементов, т. е. необходимое количество элементов в векторе превышает его текущий объем всего на один элемент. В этом случае опять происходит перераспределение памяти и объем памяти увеличивается в 1,5 раза. Таким образом, вместо нужного объема 1067 мы получили 1599.

При известном, количестве элементов вектора возникшие труд-ности (большое количество перераспределений памяти и избыточный размер вектора) можно решить просто:

vector<int> v ;

v.reserve(1067);

Тогда число перераспределений памяти будет равно нулю, а емкость – 1067, т. е. равной количеству элементов. Но ведь вектор – это динамический массив и размеры массива заранее не известны. Тогда можно подстраховаться и зарезервировать заведомо больший размер вектора (например, v.reserve(2000)). А чтобы вектор не удержи-вал ненужную память (2000 – 1067), необходимо сократить емкость от максимальной (2000) до используемой в настоящий момент (1067). Подобное сокращение емкости обычно называется «сжатием по размеру». Это сжатие в векторе v можно выполнить с помощью оператора:

vector<int>(v).swap(v); (табл. 3).

Таблица 3

Операции присваивания для векторов

Операция	Описание
v1 = v2	Присваивает v1 все элементы v2
v.assign(n,elem)	Присваивает n копий заданного элемента
v.assign(v1.beg,v1.end)	Присваивает элементы интервала [beg,end)
v1.swap(v2)	Меняет местами содержимое v1 и v2

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

Пример 4

vector<int> v1;

for( int i = 0; i < 10; i++ ) v1.push_back( i ); // Заполнение вектора

vector<int> v2;

// Копирование вектора v1 в вектор v2

v2.assign( v1.begin(), v1.end() );

for( int i = 0; i < v2.size(); i++ ) cout << v2[i] << " ";

Результат

0 1 2 3 4 5 6 7 8 9

В табл. 4 перечислены все операции прямого обращения к элементам векторов. Как принято в С и C++, первому элементу вектора соответствует индекс 0, а последнему – индекс size()-1. Таким образом, n-му элементу соответствует индекс n – 1.

Таблица 4

Операции обращения к элементам вектора

Операция	Описание
v.at(idx)	Возвращает элемент с индексом idx (при недопустимом значении индекса генерируется исключение out_of_range)
v[idx]	Возвращает элемент с индексом idx (без интервальной проверки!)
v.front()	Возвращает первый элемент (без проверки его существования!)
v.back()	Возвращает последний элемент (без проверки его существования!)

Векторы поддерживают стандартный набор операций для получения итераторов (табл. 5). Итераторы векторов относятся к категории итераторов произвольного доступа. Это означает, что с векторами в принципе могут использоваться все алгоритмы STL.

Таблица 5

Операции получения итераторов

Операция	Описание
v.begin()	Возвращает итератор произвольного доступа для первого элемента
v.end()	Возвращает итератор произвольного доступа для позиции за последним элементом

Пример 5

vector<char> v; // Создание массива нулевой длины

//Помещаем значения в вектор

for (int i = 0; i < 10; i++) v.push_back('A' + i);

// Получаем доступ к содержимому вектора с помощью итератора

vector<char>::iterator it;

for (it = v.begin(); it != v.end(); it++) cout << *it <<" ";

Результат

A B C D E F G H I J

v.end() возвращает итератор, указывающий не на последний элемент контейнера, а на непосредственно следующий за ним элемент. Это часто бывает удобно. Например, для любого контейнера v разность (v.end() - v.begin()) всегда равна v.size() (табл. 6).

Таблица 6

Операции вставки и удаления для векторов

Операция	Описание
v.insert(pos,elem)	Вставляет в позицию итератора pos копию элемента elem и возвращает позицию нового элемента
v.insert(pos,n,elem)	Вставляет в позицию итератора pos n копий элемента elem (и не возвращает значения)
v.insert(pos,beg,end)	Вставляет копию всех элементов интервала [beg,end) в позицию итератора pos (и не возвращает значения)

Окончание табл. 6

Операция	Описание
v.push_back(elem)	Присоединяет копию elem в конец вектора
v.pop_back()	Удаляет последний элемент (не возвращая его)
v.erase(pos)	Удаляет элемент в позиции итератора pos и возвращает позицию следующего элемента
v.erase(beg,end)	Удаляет все элементы из интервала [beg,end) и возвращает позицию следующего элемента
v.cleаr()	Удаляет все элементы (контейнер остается пустым)

Пример 6

vector<char> v;

for (int i=0; i<10; i++) v.push_back('A' + i);

// Отображаем исходное содержимое вектора.

cout << "Размер = " << v.size() << endl;

cout << "Исходное содержимое вектора:\n";

for (int i=0; i<v.size(); i++) cout << v[i] << " ";

cout << endl << endl;

//Вводим итератор it и присваиваем ему адрес первого элемента

//в векторе

vector<char>:: iterator it= v.begin();

it += 2; // указатель на 3-й элемент вектора

// Вставляем 10 символов 'X' в вектор v.

v.insert(it, 10, 'X');

// Отображаем содержимое вектора после вставки символов

cout << "Размер вектора после вставки = "<< v.size() << endl;

cout << "Содержимое вектора после вставки:\n";

for (i=0; i<v.size(); i++) cout << v[i] << " ";

cout << endl << endl;

// Удаление вставленных элементов.

it = v.begin();

it += 2; // Указатель на 3-й элемент вектора

v.erase(it, it+10); // Удаляем 10 элементов подряд

// Отображаем содержимое вектора после удаления символов

cout << "Размер вектора после удаления символов = " << v.size() << endl;

cout << Содержимое вектора после удаления символов:\n";

for (i=0; i<v.size(); i++) cout << v[i] << " ";

Результат

Размер = 10

Исходное содержание вектора:

A B C D E F G H I J

Размер вектора после вставки = 20

Содержимое вектора после вставки:

A B X X X X X X X X X X C D E F G H I J

Размер вектора после удаления символов = 10

Содержимое вектора после удаления символов:

A B C D E F G H I J