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 и затем сделать копирование.