Руководство по стандартной библиотеке шаблонов (STL) - [9]

Сложности выражений зависят от последовательностей.

Таблица 10. Требования последовательностей (в дополнение к контейнерам)

выражение	возвращаемый тип	утверждение/примечание состояние до/после
X(n, t) X a(n, t);	-	после: size()==n. создаёт последовательность с n копиями t.
X(i, j) X a(i, j);	-	после: size()==расстоянию между i и j. создаёт последовательность, равную диапазону [i, j).
a.insert(p, t)	iterator	вставляет копию t перед p. возвращаемое значение указывает на вставленную копию.
a.insert(p, n, t)	результат не используется	вставляет n копий t перед p.
a.insert(p, i, j)	результат не используется	вставляет копии элементов из диапазона [i, j) перед p.
a.erase(q)	результат не используется	удаляет элемент, указываемый q.
a.erase(ql, q2)	результат не используется	удаляет элементы в диапазоне [ql, q2).

vector (вектор), list (список) и deque (двусторонняя очередь) выдвигают программисту различные предложения сложности и должны использоваться соответственно. vectоr - тип последовательности, которая используется по умолчанию. list нужно использовать, когда имеются частые вставки и удаления из середины последовательности, deque - структура данных для выбора, когда большинство вставок и удалений происходит в начале или в конце последовательности.

Типы iterator и const_iterator для последовательностей должны быть, по крайней мере, из категории последовательных итераторов.

Таблица 11. Необязательные операции последовательностей

выражение	возвращаемый тип	семантика исполнения	контейнер
a.front()	reference; const_reference для постоянного a	*a.begin()	vector, list, deque
a.back()	reference; const_reference для постоянного a	*a.(--end())	vector, list, deque
a.push_front(t)	void	a.insert(a.begin(), t)	list, deque
a.push_back(t)	void	a.insert(a.end(), t)	vector, list, deque
a.pop_front()	void	a.erase(a.begin())	list, deque
a.pop_back()	void	a.erase(--a.end())	vector, list, deque
a[n]	reference; const_reference для постоянного a	*(a.begin() + n)	vector, deque

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

Вектор (Vector)

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

template ‹class T, template ‹class U› class Allocator = allocator›
class vector {
public:

 // определения типов (typedefs):
 typedef iterator;
 typedef const_iterator;
 typedef Allocator‹T›::pointer pointer;
 typedef Allocator‹T›::reference reference;
 typedef Allocator‹T›::const_reference const_reference;
 typedef size_type;
 typedef difference_type;
 typedef T value_type;
 typedef reverse_iterator;
 typedef const_reverse_iterator;

 // размещение/освобождение (allocation/deallocation):
 vector();
 vector(size_type n, const T& value = T());
 vector(const vector‹T, Allocator›& x);
 template ‹class InputIterator›
 vector(InputIterator first, InputIterator last);
 ~vector();
 vector‹T, Allocator›& operator=(const vector‹T, Allocator›& x);
 void reserve(size_type n);
 void swap(vector‹T, Allocator›& x);

 // средства доступа (accessors):
 iterator begin();
 const_iterator begin() const;
 iterator end();
 const_iterator end() const;
 reverse_iterator rbegin();
 const_reverse_iterator rbegin();
 reverse_iterator rend();
 const_reverse_iterator rend();
 size_type size() const;
 size_type max_size() const;
 size_type capacity() const;
 bool empty() const;
 reference operator[](size_type n);
 const_reference operator[](size_type n) const;
 reference front();
 const_reference front() const;
 reference back();
 const_reference back() const;

 // вставка/стирание (insert/irase):
 void push_back(const T& x);
 iterator insert(iterator position, const T& x = T());
 void insert(iterator position, size_type n, const T& x);
 template ‹class InputIterator›
 void insert(iterator position, InputIterator first, InputIterator last);
 void pop_back();
 void erase(iterator position);
 void erase(iterator first, iterator last);
};

template ‹class T, class Allocator›
bool operator==(const vector‹T, Allocator›& x, const vector‹T, Allocator›& y);

template ‹class T, class Allocator›
bool operator‹(const vector‹T, Allocator›& x, const vector‹T, Allocator›& y);

iterator - это итератор произвольного доступа, ссылающийся на T. Точный тип зависит от исполнения и определяется в Allocator.

const_iterator - это постоянный итератор произвольного доступа, ссылающийся на const T. Точный тип зависит от исполнения и определяется в Allocator. Гарантируется, что имеется конструктор для const_iterator из iterator.

size_type - беззнаковый целочисленный тип. Точный тип зависит от исполнения и определяется в Allocator.

difference_type - знаковый целочисленный тип. Точный тип зависит от исполнения и определяется в Allocator.

Конструктор template ‹class InputIterator› vector(InputIterator first, InputIterator last) делает только N вызовов конструктора копирования T (где N - расстояние между first и last) и никаких перераспределений, если итераторы first и last относятся к последовательной, двунаправленной или произвольного доступа категориям. Он делает, самое большее, 2N вызовов конструктора копирования T и logN перераспределений, если они - только итераторы ввода, так как невозможно определить расстояние между first и last и затем сделать копирование.