Лекция 14. 14/05/2004.
Стандартная библиотека шаблонов.
(Standard Template Library – STL)
Рассмотрим теоретические основы теории библиотеки и её построения.
Ядро библиотеки стандартных шаблонов образуют три компонента: контейнеры, алгоритмы и итераторы. Эти элементы функционируют в тесной взаимосвязи друг с другом.
Контейнеры.
Контейнер – шаблонный класс для хранения объектов какого-либо одного и того же типа. Контейнеры бывают различных типов. Например, в классе vector определяется динамический массив, queue – очередь, list – линейный список. Помимо таких базовых контейнеров, в библиотеке стандартных шаблонов определены и ассоциативные контейнеры, которые позволяют получать хранящиеся в них значения. Например, в классе map определён ассоциативный список, доступ к элементам которого осуществляется с помощью уникальных ключей. Т.е. в таком списке элемент – это пара «значение-ключ».
Контейнеры STL:
Vector – динамический массив.
List – линейный список.
Stack – стек.
Queue – очередь.
Deque – двусторонняя очередь.
Priority_queue – очередь с приоритетом.
Set – множество с уникальными элементами.
Bitset – множество битов.
Multiset – множество не обязательно с уникальными элементами.
Map – ассоциативный список, в котором хранятся пары ключ/значение, с каждым ключом связано одно значение.
Multimap – ассоциативный список, в котором хранятся пары ключ/значение, с каждым ключом связано не обязательно одно значение.
Если сразу создать класс, а в качестве указателя – указатель на базовый класс, тогда фактически эти указатели будут указателями на разные объекты.
Функции.
В каждом контейнере определён некоторый набор функций для работы с тем, что хранится в контейнере.
Схожие функции имеют во всех контейнерах одинаковые названия.
push_back ( ); - положить в конец контейнера
size ( ); - определяет текущую длину контейнера
Таких функций существует приблизительно 15-20.
Для всех классов общими являются не все функции, а только те, которые одинаково эффективно реализуются для каждого контейнера.
Например, к функции “vector [ ]” можно обращаться по номеру, а к “list ” (списку) – нельзя.
Основные типы.
Следующие типы определены в public-части для каждого контейнера.
value_type
allocator_type - распределитель памяти
size_type
iterator, const_iterator
reverse_iterator, const_reverse_iterator
pointer, const_pointer - указатель на элементы
reference, const_reference - ссылка на элементы
Тела функций скрыты от пользователя, при программировании с помощью STL об их содержимом можно не заботиться.
Распределитель памяти.
У каждого контейнера есть свой распределитель памяти allocator, который управляет процессом выделения памяти для объектов контейнера. По умолчанию распределитель памяти – это объект класса allocator. Также можно написать свой распределитель памяти и использовать его в программах, если STL не используем.
Рассматриваем только интерфейс функций:
template class allocator {
………………………………………
public:
typedef T*pointer;
typedef T&reference;
………………………………………
allocator( ) throw( );
//- конструктор по умолчанию
………………………………………
pointer allocate (size_type n);
}
По умолчанию берётся стандартный распределитель памяти, он берёт память из области динамической памяти.
Алгоритмы.
В STL имеется 60 алгоритмов.
Алгоритмы реализуют некоторые распространённые операции с контейнерами, которые не включены в контейнер.
Т.е алгоритм – шаблонная функция, поэтому их можно использовать с контейнерами любых типов..
Алгоритмы подразделяются на 3 группы:
-
немодифицирующий алгоритм – действия сводятся к просмотру контейнера или выделению из него какой-либо функции
find ( ); - поиск элемента, выдаёт место, на котором находится элемент.
count ( ); - подсчёт
for_each( );
transform ( );
reverse ( );
copy ( ); - копируется содержимое одного контейнера в другой
sort ( ); - простая сортировка
stable_sort( ); - сортировка, гарантирующая сохранение относительно порядка
элементов
merge( ); - слияние двух списков.
Итераторы.
Итераторы – это что-то вроде указателей на элементы контейнера.
Типы итераторов перечислены в контейнере. В public-части контейнера есть итераторные функции с одинаковыми именами.
Объекты класса итератора играют роль указателей для контейнера. Итераторы используются для доступа к содержимому контейнера примерно так же, как указатели для доступа к элементам массива.
Итераторный класс определяется внутри контейнера.
Следует обратить внимание, что при использовании нужно писать оператор расширения видимости, чтобы знать, к какому итератору относится написанное:
list :: iterator
Пример.
iterator begin ( ) [const];
iterator end ( ) [const];
или
const_iterator begin ( ) [const];
const_iterator end ( ) [const];
Т.е. возвращается значение либо типа iterator, либо типа const_iterator.
Для итераторов нет константы NULL, обозначающей пустой указатель.
end ( ) – возвращает следующий после этого элемент итератора (т.е. уже элемент следующего итератора).
reverse_iterator rbegin( ) [const];
reverse_iterator rend( ) [const];
или
const_reverse_iterator rbegin( ) [const];
const_reverse_iterator rend( ) [const];
- обратный итератор, выдаёт последовательность в обратном порядке.
Различие между этими итераторами:
begin A B C .
end
rbegin C B A .
rend
Типы итераторов:
Существуют следующие типы операторов, которые позволяют соответствующие функции:
-
Итераторы вывода.
*p_ , p++
-
Итераторы ввода.
*=p, ->, ++, ==, !=
-
Однонаправленные.
*p=, =*p, ->, ++, ==, !=
- положить в контейнер
- взять из контейнера
-
Двунаправленные.
*p=, =*p, -> , ++, ==, !=, --
-
C произвольным доступом.
*p=, =*p, -> , ++, ==, !=, --, [ ], +, -, +=, -=, <, >, <=, >=
С 1 до 5 увеличивается мощность итераторов.
Пример. Шаблонная функция find.
Для работы нужны итераторы, которые указывают место начала поиска, место конца поиска, искомый элемент.
Нужно ввести итератор ввода.
template
input Iterator find (InputIterator first,
InputIterator last,
const T& value)
{
while (first!=last && *first != value)
first++;
return first;
}
Используются такие имена шаблонов, чтобы было понятно, к какому итератору он относится.
Пример. Контейнер vector. (схематично)
template > class vector {
- параметр распределения памяти, по умолчанию берётся
стандартный распределитель памяти
……………………………………………..
public:
//типы
//итераторные функции
//доступ к элементам
/*const*/reference operator [ ] (size_type n); //доступ без контроля выхода за
диапазон вектора
/*const*/reference at (size_type n); //с контролем
/*const*/reference front ( ); //указатель на первый элемент контейнера
/*const*/reference back ( ); // указатель на последний элемент контейнера
explicit vector (const A& = A( ));
// - здесь опускается имя формального параметра, работает
конструктор по умолчанию
// explicit vector - вектор нулевой длины (когда данные записываются в вектор,
// сначала создаётся такой вектор)
explicit vector (site_type n; const T& value = T( ); const A& = A( ));
………………………… // здесь определён конструктор копирования, оператор
// присваивания и др.
// функции – члены класса, частые в использовании
iterator erase (iterator i);
iterator insert (iterator i, const T& value = T( ));
// - вставка перед этим элементом, возвращает итератор вставленного
элемента
void push_back ( );
void pop_back ( ); // - удаляем последнюю запись вставленного элемента
sizetype size ( ) const;
bool empty ( ) const;
void clear ( ); // - очищаем вектор
………………………….
}
Пример. Контейнер – список.
template > class list {
public:
//типы
//итераторные функции
/*const*/reference front ( ); //указатель на первый элемент контейнера
/*const*/reference back ( ); // указатель на последний элемент контейнера
explicit list (const A& = A( ));
explicit list (site_type n; const T& value = T( ); const A& = A( ));
//explicit – для безопасности, не позволяет делать присваивание векторов.
…………………………
iterator erase (iterator i);
iterator insert (iterator i, const T& value = T( ));
// - вставка перед этим элементом, возвращает итератор вставленного
элемента
void push_back ( );
void pop_back ( ); // - удаляем последнюю запись вставленного элемента
sizetype size ( ) const;
bool empty ( ) const;
void clear ( ); // - очищаем вектор
………………………….
}
Пример. Написать функцию, формирующую вектор.
#include
#include
#include
using name_space std;
void g (vector &v, list lst) {
// - ставить здесь ссылку является хорошим стилем
int i;
for (i=0; i
// функция size для вектора v
if (!(v[i]%2)) lst.push_back (v[i]);
lst :: const_iterator p=lst.begin( );
// - показываем на первый элемент
while (p!=lst.end( )) {
cout << *p << endl;
p++;
}
}
Для этой функции напишем функцию main.
int main ( ) {
vector v (20);
list lst;
//- первый конструктор без параметров, создающий список 0 длины
int i;
for (i=0; i<20; i++) v[i]=i;
g (v,lst);
return 0;
}
|
