Руководство по стандартной библиотеке шаблонов

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

Таблица 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.