Стандартная библиотека шаблонов

Цель.

Освоить технологию обобщенного программирования с использованием библиотеки стандартных шаблонов (STL) языка C++.

6.2 Основное содержание работы.

Написать три программы с использованием STL. Первая и вторая программы должны демонстрировать работу с контейнерами STL, третья - использование алгоритмов STL.

Основные теоретические сведения.

Стандартная библиотека шаблонов (STL).

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

STL строится на основе шаблонов классов, и поэтому входящие в неё алгоритмы и структуры применимы почти ко всем типам данных.

Состав STL.

Ядро библиотеки образуют три элемента: контейнеры, алгоритмы и итераторы.

Контейнеры (containers) – это объекты, предназначенные для хранения других элементов. Например, вектор, линейный список, множество.

Ассоциативные контейнеры (associative containers) позволяют с помощью ключей получить быстрый доступ к хранящимся в них значениям.

В каждом классе-контейнере определен набор функций для работы с ними. Например, список содержит функции для вставки, удаления и слияния элементов.

Алгоритмы (algorithms) выполняют операции над содержимым контейнера. Существуют алгоритмы для инициализации, сортировки, поиска, замены содержимого контейнеров. Многие алгоритмы предназначены для работы с последовательностью (sequence), которая представляет собой линейный список элементов внутри контейнера.

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

С итераторами можно работать так же, как с указателями. К ним можно применить операции *, инкремента, декремента. Типом итератора объявляется тип iterator, который определен в различных контейнерах.

 

Существует пять типов итераторов:

1. Итераторы ввода (input_iterator) поддерживают операции равенства, разыменования и инкремента.

==,!=, *i, ++i, i++, *i++

Специальным случаем итератора ввода является istream_iterator.

2. Итераторы вывода (output_iterator) поддерживают операции разыменования, допустимые только с левой стороны присваивания, и инкремента.

++i, i++, *i=t, *i++=t

Специальным случаем итератора вывода является ostream_iterator.

3. Однонаправленные итераторы (forward_iterator) поддерживают все операции итераторов ввода/вывода и, кроме того, позволяют без ограничения применять присваивание.

==,!=, =, *i, ++i, i++, *i++

4. Двунаправленные итераторы (biderectional_iterator) обладают всеми свойствами forward-итераторов, а также имеют дополнительную операцию декремента (--i, i--, *i--), что позволяет им проходить контейнер в обоих направлениях.

5. Итераторы произвольного доступа (random_access_iterator) обладают всеми свойствами biderectional-итераторов, а также поддерживают операции сравнения и адресной арифметики, то есть непосредственный доступ по индексу.

i+=n, i+n, i-=n, i-n, i1-i2, i[n], i1<i2, i1<=i2, i1>i2, i1>=i2

 

В STL также поддерживаются обратные итераторы (reverse iterators). Обратными итераторами могут быть либо двунаправленные итераторы, либо итераторы произвольного доступа, но проходящие последовательность в обратном направлении.

Вдобавок к контейнерам, алгоритмам и итераторам в STL поддерживается ещё несколько стандартных компонентов. Главными среди них являются распределители памяти, предикаты и функции сравнения.

У каждого контейнера имеется определенный для него распределитель памяти (allocator), который управляет процессом выделения памяти для контейнера.

По умолчанию распределителем памяти является объект класса allocator. Можно определить собственный распределитель.

В некоторых алгоритмах и контейнерах используется функция особого типа, называемая предикатом. Предикат может быть унарным и бинарным. Возвращаемое значение: истина либо ложь. Точные условия получения того или иного значения определяются программистом. Тип унарных предикатов UnPred, бинарных – BinPred. Тип аргументов соответствует типу хранящихся в контейнере объектов.

Определен специальный тип бинарного предиката для сравнения двух элементов. Он называется функцией сравнения (comparison function). Функция возвращает истину, если первый элемент меньше второго. Типом функции является тип Comp.

Особую роль в STL играют объекты-функции.

Объекты-функции - это экземпляры класса, в котором определена операция «круглые скобки» (). В ряде случаев удобно заменить функцию на объект-функцию. Когда объект-функция используется в качестве функции, то для ее вызова используется operator ().

Пример 1.

class less{

public:

bool operator()(int x,int y)

{ return x< y;}

};

 

Классы-контейнеры.

В STL определены два типа контейнеров: последовательности и ассоциативные.

Ключевая идея для стандартных контейнеров заключается в том, что когда это представляется разумным, они должны быть логически взаимозаменяемыми. Пользователь может выбирать между ними, основываясь на соображениях эффективности и потребности в специализированных операциях. Например, если часто требуется поиск по ключу, можно воспользоваться map (ассоциативным массивом). С другой стороны, если преобладают операции, характерные для списков, можно воспользоваться контейнером list. Если добавление и удаление элементов часто производится в концы контейнера, следует подумать об использовании очереди queue, очереди с двумя концами deque, стека stack. По умолчанию пользователь должен использовать vector; он реализован, чтобы хорошо работать для самого широкого диапазона задач.

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

В STL определены следующие классы-контейнеры (в угловых скобках указаны заголовочные файлы, где определены эти классы):

 

bitset               множество битов <bitset.h>

vector                  динамический массив <vector.h>

list                   линейный список <list.h>

deque                  двусторонняя очередь <deque.h>

stack               стек <stack.h>

queue                  очередь <queue.h>

priority_ queue   очередь с приоритетом <queue.h>

map                     ассоциативный список для хранения пар ключ / значение, где с каждым ключом связано одно значение <map.h>

multimap         с каждым ключом связано два или более значений <map.h>

set                         множество <set.h>

multiset            множество, в котором каждый элемент не обязательно уникален <set.h>

 

Обзор операций

Типы

value_ type       тип элемента

allocator_type тип распределителя памяти

size_type          тип индексов, счетчика элементов и т.д.

iterator             ведет себя как value_type*

reverse_iterator   просматривает контейнер в обратном порядке  

reference          ведет себя как value_type&

key_type                тип ключа (только для ассоциативных контейнеров)

key_compare тип критерия сравнения (только для ассоциативных контейнеров)

mapped_type тип отображенного значения

Итераторы

begin()                   указывает на первый элемент

end()                         указывает на элемент, следующий за последним

rbegin()           указывает на первый элемент в обратной последовательности

rend()           указывает на элемент, следующий за последним в обратной последовательности

Доступ к элементам

front()             ссылка на первый элемент

back()                  ссылка на последний элемент

operator[] (i)   доступ по индексу без проверки

at (i)                     доступ по индексу с проверкой

Включение элементов

insert( p,x )             добавление х перед элементом, на который указывает р

insert( p,n,x )          добавление n копий х перед р

insert( p,first,last ) добавление элементов из [first:last] перед р

push_back( x )    добавление х в конец

push_front( x )   добавление нового первого элемента (только для списков и очередей с двумя концами)

Удаление элементов

pop_back()             удаление последнего элемента

pop_front()         удаление первого элемента (только для списков и очередей с двумя концами)

erase( p )                 удаление элемента в позиции р

erase( first,last )       удаление элементов из [first:last]

clear()                       удаление всех элементов

Другие операции

size()                  число элементов

empty()              контейнер пуст?

capacity()           память, выделенная под вектор (только для векторов)

reserve( n )              выделяет память для контейнера под n элементов

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

swap( x )                      обмен местами двух контейнеров

==, !=, <                        операции сравнения

Операции присваивания

operator=( x )        контейнеру присваиваются элементы контейнера х

assign( n,x )            присваивание контейнеру n копий элементов х (не для ассоциативных контейнеров)

assign( first,last ) присваивание элементов из диапазона [first:last]

Ассоциативные операции

operator[]( k )      доступ к элементу с ключом k

find( k )                 находит элемент с ключом k

lower_bound( k ) находит первый элемент с ключом k

upper_bound( k ) находит первый элемент с ключом, большим k

equal_range( k ) находит lower_bound (нижнюю границу) и upper_bound (верхнюю границу) элементов с ключом k

 

Контейнера vector -вектор.

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

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

где T – тип предназначенных для хранения данных.

 

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

В классе vector определены следующие конструкторы:

explicit vector (const Allocator& a=Allocator());

explicit vector (size_type число, const T&значение= T(), const Allocator&a= =Allocator());

vector (const vector<T,Allocator>&объект);

template<class InIter> vector (InIter начало, InIter конец, const Allocator&a= =Allocator());

Первая форма представляет собой конструктор пустого вектора.

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

Третья форма конструктора вектор – это конструктор копирования.

Четвертая форма – это конструктор вектора, содержащего диапазон элементов, заданный итераторами начало и конец.

Пример 2.

vector<int> a;

vector<double> x(5);

vector<char> c(5,’*’);

vector< int> b(a); // b= a

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

Для класса вектор определены следующие операторы сравнения:

==, <, <=,!=, >, >=.

Кроме этого, для класса vector определяется оператор индекса [].

Новые элементы могут включаться с помощью функций

insert(), push_back(), resize(), assign().

Существующие элементы могут удаляться с помощью функций

erase(), pop_back(), resize(), clear().

Доступ к отдельным элементам осуществляется с помощью итераторов

begin(), end(), rbegin(), rend(),

Манипулирование контейнером, сортировка, поиск в нем и тому подобное возможно с помощью глобальных функций файла - заголовка <algorithm.h>.

Пример 3.

#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);

cout<<“size=”<<v.size()<<“\n”;

for(i=0;i<10;i++)cout<<v[i]<<“ ”;

cout<<endl;

for(i=0;i<10;i++)v[i]=v[i]+v[i];

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

cout<< endl;

}

Пример 4. Доступ к вектору через итератор.

#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);

cout<<“size=”<<v.size()<<“\n”;

vector<int>::iterator p=v.begin();

while(p!=v.end())

{cout<<*p<<” “;p++;}

}

Пример 5. Вставка и удаление элементов.

#include<iostream.h>

#include<vector.h>

using namespace std;

void main()

{vector<int> v(5,1);

int i;

//вывод

for(i=0;i<5;i++)cout<<v[i]<<“ ”;

cout<<endl;

vector<int>::iterator p=v.begin();

p+=2;

//вставить 10 элементов со значением 9

v.insert(p,10,9);

//вывод

p=v.begin();

while(p!=v.end())

{ cout<<* p<<” “; p++;}

//удалить вставленные элементы

p=v.begin();

p+=2;

v.erase(p,p+10);

//вывод

p=v.begin();

while(p!=v.end())

{ cout<<* p<<” “; p++;}

}

Пример 6. Вектор содержит объекты пользовательского класса.

#include<iostream.h>

#include<vector.h>

#include”student.h”

using namespace std;

void main()

{vector<STUDENT> v(3);

int i;

v[0]=STUDENT(“Иванов”,45.9);

v[1]= STUDENT(“Петров”,30.4);

v[0]= STUDENT(“Сидоров”,55.6);

//вывод

for(i=0;i<3;i++)cout<<v[i]<<“ ”;

cout<< endl;

}

 

Ассоциативные контейнеры (массивы).

Ассоциативный массив содержит пары значений. Зная одно значение, называемое ключом (key), мы можем получить доступ к другому, называемому отображенным значением (mapped value).

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

V& operator[](const K&) возвращает ссылку на V, соответствующий K.

Ассоциативные контейнеры – это обобщение понятия ассоциативного массива.

Ассоциативный контейнер map - это последовательность пар (ключ, значение), которая обеспечивает быстрое получение значения по ключу. Контейнер map предоставляет двунаправленные итераторы.

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

 

Спецификация шаблона для класса map:

template<class Key,classT,class Comp=less<Key>,class Allocator=allocator<pair> >

class std::map

В классе map определены следующие конструкторы:

explicit map (const Comp& c=Comp(),const Allocator& a=Allocator());

map (const map<Key,T,Comp,Allocator>& ob);

template<class InIter> map (InIter first,InIter last,const Comp& c=Comp(),const Allocator& a=Allocator());

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

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

map& operator= (const map&);

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

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

Создавать пары ключ/значение можно не только с помощью конструкторов класса pair, но и с помощью функции make_pair, которая создает объекты типа pair, используя типы данных в качестве параметров.

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

mapped_type& operator[] (const key_type& K);

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

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

Множество, как и ассоциативный массив, требует, чтобы для типа T существовала операция “меньше” (<). Оно хранит свои элементы отсортированными, так что перебор происходит по порядку.

Алгоритмы.

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

 

Алгоритмы определены в заголовочном файле <algorithm.h>.

Ниже приведены имена некоторых наиболее часто используемых функций-алгоритмов STL.