FreeSource : Статьи / Кратко Обо Всём / Clang / part 2 / part 8

Это старая версия Статьи/КраткоОбоВсём/Clang/part2/part8 за 2007-08-30 09:16:25..

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

STL представляет собой большую библиотеку шаблонов включающую в себя три ключевых компонента: контейнеры, итераторы, алгоритмы. Кроме того, STL является расширяемой библиотекой. STL избегает операторов new и delete и использует распределители памяти(allocators) для выделения и высвобождения памяти. Существует возможность создавать пользовательские распределители памяти. Типы исключений в STL:

out_of_range – индекс находится вне диапазона;
invalid_argument – передача недопустимого аргумента функции;
length_error – создание слишком длинного контейнера;
bad_alloc – неудачная попытка выделения области памяти.

2.8.1 Контейнеры

Контейнеры делятся на три основных категории: контейнеры последовательностей, ассоциативные контейнеры и адаптеры контейнеров. Контейнеры последовательностей (sequence containers) и Ассоциативные контейнеры имеют общее название – контейнеры первого класса (first-class containers). Существует ещё четыре типа контейнеров, которые считаются «почти контейнерами» («near-containers») – С-подобные массивы, string, bitset и valarray.

Контейнерные заголовочные файлы стандартной библиотеки:

<vector>
<list>
<deque>
<queue> – cодержит как queue, так и priority_queue;
<stack>
<map> – Содержит как map, так и multimap;
<set> – Содержит как set, так и multiset;
<bitset>

Общие имена типа typedef имеющиеся в контейнерах первого класса:

value_type – тип элемента, хранимого в контейнере;
reference – ссылка на тип элемента, хранимого в контейнере;
const_reference – ссылка-константа на тип элемента, хранимого в контейнере;
pointer – указатель на тип элемента, хранимого в контейнере;
iterator – итератор; указывает на тип элемента, хранимого в контейнере;
const_iterator – констатный итератор; указывает на тип элемента, хранимого в контейнере;
reverse_iterator – обратный итератор; указывает на тип элемента, хранимого в контейнере;
const_reverse_iterator – константный обратный итератор, который указывает на тип элемента, хранимого в контейнере;
difference_type – тип результата вычитания двух итераторов, которые ссылаются на один и тот же контейнер;
size_type – тип, используемый для подсчёта элементов в контейнере и для индексации в контейнере последовательности.

Таблица 11. Контейнерные классы STL

Имя	Назначение	Тип итератора
Контейнеры последовательностей
vector	Быстрые вставки и удаление в конец контейнера, прямой доступ к любому элементу.	произв. доступ
deque	Быстрые вставки и удаления в начало и конец контейнера, прямой доступ к любому элементу.	произв. доступ
list	Двухсвязный список, быстрая вставка и удаление элементов везде.	двунапр.
Ассоциативные контейнеры
set	Быстрый поиск, дубликаты (одинаковые ключи)не допускаются.	двунапр.
multiset	Быстрый поиск, допускаются дубликаты.	двунапр.
map	Взаимно однозначное соответствие, дубликаты не допускаются, быстрый поиск значения по ключу.	двунапр.
multimap	Соответствие «один ко многим», дублирование ключей допускается, быстрый поиск значения по ключу.	двунапр.
Адаптеры контейнеров
stack	«Последним пришел, первым вышел» (LIFO)	не поддерж.
queue	«Первым пришел, первым вышел» (FIFO)	не поддерж.
priority_ queue	Элемент с наивысшим приоритетом всегда достигает выхода из очереди первым.	не поддерж.

Таблица 12. Общие для всех STL-контейнеров функции

Имя	Назначение
default constructor	Конструктор для обеспечения инициализации по умолчанию.
copy constructor	Конструктор, который инициализирует контейнер в качестве копии существующего контейнера.
destructor	Деструктор контейнера.
empty	Проверка контейнера на пустоту.
max_size	Возвращает максимальное число элементов в контейнере.
size	Возвращает число элементов в контейнере.
=	Присваивает один контейнер другому.
<, <=, >, >=, ==, !=	Сравнивает два контейнера.
swap	Поменять местами элементы двух контейнеров.
Только в контейнерах первого класса
begin	Возвращает iterator, либо const_iterator который ссылается на первый элемент контейнера.
end	Возвращает iterator, либо const_iterator который ссылается на последний элемент контейнера.
rbegin	Возвращает reverse_iterator, либо const_reverse_iterator который ссылается на последний элемент контейнера.
rend	Возвращает reverse_iterator, либо const_reverse_iterator который ссылается на позицию перед первым элементом контейнера.
erase	Удаляет один или несколько элементов из контейнера.
clear	Удаляет все элементы из контейнера.

Контейнеры последовательностей

Классы vector и deque реализованы на базе массивов. Класс list реализует связанный список. Дополнительные операции характерные для контейнеров последовательностей:

front
front();
Возвращает ссылку на первый элемент в контейнере.

back
back();
Возвращает ссылку на последний элемент в контейнере.

push_back
push_back();
Вставляет новый элемент в конец контейнера.

pop_back
pop_back();
Выталкивает последний элемент контейнера.

Контейнер vector обеспечивает структуру данных непрерывной областью памяти. Это позволяет обеспечивает эффективный прямой доступ к любому элементу контейнера vector посредством операции индексирования []. Все алгоритмы STL могут работать с контейнером vector. Итераторы для vector обычно реализуются как указатели на элементы контейнера vector.


std::vector<int> v;
v.push_back(2);
cout << "\nРазмер вектора v: " << v.size();

std::vector<int>::const_iterator p1;
for(p1 = v.begin(); p1 != v.end(); p1  ) cout << *p1 << ' ';
std::vector<int>::reverse_iterator p2;
for(p2 = v.rbegin(); p2 != v.rend();   p2) cout << *p2 << ' ';

int a[ 6 ] = { 1, 2, 3, 4, 5, 6 };
std::vector<int> v1(a, a 6);
std::ostream_iterator<int> output(cout," ");
std::copy(v1.begin(), v1.end(), out); //печать вектора
try
{
  v1.at(100) = 777;   //доступ вне массива
} 
catch(std::out_of_range e)
{ cout << "\nИсключение" << e.what(); }
v1.erase(v.begin());

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

inplace_merge
void inplace_merge(_BidirectionalIter first, _BidirectionalIter middle, _BidirectionalIter last, _Compare comp);
Объединяет две возростающие последовательности в одном и том же контейнере.

splice
splice();
Вырезает элементы из одного контейнера и помещает их в другой.

push_front
push_front();
Вставить элемент в начало контейнера.

pop_front
pop_front();
Вытолкнуть элемент с начала контейнера.

*
6a51
*remov
1000
e**
remove();
Удалить элемент из начала контейнера.

merge
_OutputIter merge(_InputIter1 first1, _InputIter1 last1, _InputIter2 first2, _InputIter2 last2, _OutputIter result)
Объединяет две возростающие последовательности в одну.

sort
void sort(_RandomAccessIter first, _RandomAccessIter last);
Сортировка элементов в возрастающем порядке.


std::list<int> Values, otherValues;
Values.push_front(1);
Values.push_back(2);
values.sort();

Контейнер deque объединяет многие возможности классов vector и list. Реализуется на основе очереди с двумя концами и обеспечивает эффективный индексный доступ с эффективной операцией вставки в начало и конец контейнера. Класс deque обеспечивает поддержку итераторов произвольного доступа. Наиболее часто deque используется в качестве очереди FIFO.


std::deque<double> values;
std::ostream_iterator<double> output(cout," ");
values.push_front(2.2);
values.push_back(1.1);
for(int i=0; i < values.size();   i) 
  cout << values[i] << ' ';
values.pop_front();
values[1]=5.4;

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

Ассоциативные контейнеры STL предназначены для обеспечения прямого доступа с целью сохранения и выборки элементов с помощью ключей (ключи поиска). Имеется четыре ассоциативных контейнера: multiset, set, multimap, map. В каждом контейнере ключи сохраняются упорядоченными. Ассоциативные контейнеры поддерживают дополнительные функции:

equal_range
//pair<_ForwardIter, _ForwardIter> equal_range(_ForwardIter first, _ForwardIter last, const _Tp