Александр Степанов - РУКОВОДСТВО ПО СТАНДАРТНОЙ БИБЛИОТЕКЕ ШАБЛОНОВ (STL)

Если тип итератора контейнера принадлежит к категории двунаправленных итераторов или итераторов произвольного доступа, то контейнер называется reversible (обратимым) и удовлетворяет следующим дополнительным требованиям:

Таблица 9. Требования обратимых контейнеров (в дополнение к контейнерам)

Последовательность - это вид контейнера, который организует конечное множество объектов одного и того же типа в строгом линейном порядке. Библиотека обеспечивает три основных вида последовательных контейнеров: vector (вектор), list (список) и deque (двусторонняя очередь). Она также предоставляет контейнерные адаптеры, которые облегчают создание абстрактных типов данных, таких как стеки или очереди, из основных видов последовательностей (или из других видов последовательностей, которые пользователь может сам определить).

В следующих двух таблицах X - последовательный класс, a - значение X, i и j удовлетворяют требованиям итераторов ввода, [i, j) - допустимый диапазон, n - значение X::size_type, p - допустимый итератор для a, q - разыменовываемый итератор для a, [q1, q2) - допустимый диапазон в a, t - значение X::value_type.

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

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

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

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

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

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

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.