11. Контейнеры stl: понятие, виды, основные операции, приемы использования.

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

Контейнер	Описание	Треб.заголовок
deque	Двунаправленная очередь	<deque>
list	Линейный список	<list>
map	Хранит пары “ключ/значение”, где каждый ключ ассоциирован только с одним значением	<map>
multimap	Хранит пары “ключ/значение”, где каждый ключ может быть ассоциирован с двумя или более значениями	<map>
multiset	Мн-во в котором каждый эл-нт не обязательн уникален	<set>
priority_queue	Очередь с приоритетами	<deque>
queue	Очередь	<deque>
set	Множество уникальных элементов	<set>
stack	Стек	<stack>
vector	Динамический массив	<vector>

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

Классы stack, queue и priority_queue называются адаптерами контейнеров, потому что используют один из последовательных контейнеров, содержащий их элементы. Таким образом, для последовательных контейнеров подчеркивается функциональность, предоставленная stack, queue и priority_queue.

Контейнер vector. Вектор vector в STL определен как динамический массив с доступом к его элементам по индексу.

template<class T,class Allocator=allocator<T>>class std::vector{…};

где T – тип предназначенных для хранения данных. Allocator задает распределитель памяти, который по умолчанию является стандартным. Пример:

vector<int> a; vector<double> x(5); vector<char> c(5,’*’); vector<int> b(a);

Для любого объекта, который будет храниться в векторе, должен быть определен конструктор по умолчанию,и должны быть определены операторы < и ==.

Для класса вектор определены следующие операторы сравнения: ==, <, <=, !=, >, >=. Кроме этого, для класса vector определяется оператор индекса []. Новые элементы могут включаться с помощью функций insert(), push_back(), resize(), assign(). Существующие элементы могут удаляться с помощью функций erase(), pop_back(), resize(), clear(). Доступ к элементам осуществляется с помощью итераторов begin(), end(), rbegin(), rend(). Манипулирование контейнером, сортировка, поиск в нем и тому подобное возможно с помощью глобальных функций <algorithm.h>. Пример:

#include<iostream.h> #include<vector.h> using namespace std;

void main(){vector<int> v; int i; for(i=0;i<10;i++) v.push_back(i); for(i=0;i<10;i++)v[i]=v[i]+v[i];

for(i=0;i<v.size();i++) cout<<v[i]<<“ ”; cout<<endl; }

Ассоциативные контейнеры – это обобщение понятия ассоциативного массива. Ассоциативный контейнер map  это последовательность пар (ключ, значение), которая обеспечивает быстрое получение значения по ключу. Контейнер map предоставляет двунаправленные итераторы. Ассоциативный контейнер map требует, чтобы для типов ключа существовала операция “<”. Он хранит свои элементы отсортированными по ключу так, что перебор происходит по порядку.

Спецификация шаблона для класса map: template<class Key,classT,class Comp=less<Key>, class Allocator=allocator<pair> > class std::map

Определена операция присваивания: map& operator=(const map&);

Определены следующие операции: ==, <, <=, !=, >, >=.

В map хранятся пары ключ/значение в виде объектов типа pair.

Типичная операция для ассоциативного контейнера – это ассоциативный поиск при помощи операции индексации ([]). mapped_type& operator[](const key_type& K);

Множества set можно рассматривать как ассоциативные массивы, в которых значения не играют роли, так что мы отслеживаем только ключи.

template<classT,class Cmp=less<T>, class Allocator=allocator<T>>class std::set{…};