C++ named requirements: SequenceContainer

A SequenceContainer is a Container that stores objects of the same type in a linear arrangement.

Requirements

Легенда
`X`	Класс контейнера последовательности
`T`	Тип элементов `X`
`a`	Значение типа `X`
`u`	Имя объявленной переменной
`A`	Тип аллокатора `X`: `X::allocator_type` если он существует, в противном случае std::allocator<T>
`i`, `j`	LegacyInputIterators такие, что `[i,` `j)` является корректным диапазоном и итераторы ссылаются на элементы, неявно преобразуемые в `value_type`
`rg` (с C++23)	Значение типа `R`, которое моделирует `container-compatible-range<T>`
`il` (с C++11)	Объект типа std::initializer_list<value_type>
`n`	Значение типа `X::size_type`
`p`	Действительный постоянный итератор в `a`
`q`	действительный доступный постоянный итератор в `a`
`q1`, `q2`	Два постоянных итератора в `a` таких, что `[q1,` `q2)` является допустимым диапазоном
`t`	lvalue или постоянное rvalue(с C++11) типа `X::value_type`
`rv` (с C++11)	Непостоянное rvalue типа `X::value_type`
`Args` (с C++11)	Упакованный параметр шаблона
`args` (с C++11)	Упакованный параметр функции с шаблоном `Arg&&`

Тип X удовлетворяет SequenceContainer, если

Тип X удовлетворяет Container, и
Следующие утверждения и выражения должны быть валидными и иметь указанные эффекты для всех контейнеров последовательностей за исключением std::array (см. примечания)(с C++11):

Выражение		Эффекты	Условия^[1]
`X u(n, t)`		Создаёт контейнер последовательности, содержащий `n` копий `t`.	Пре	`T` является CopyInsertable в `X`.
`X u(n, t)`			Пост	`std::distance(u.begin(), u.end()) == n` является `true`.
`X u(i, j)`		Создаёт контейнер последовательности, равный, элемент за элементом, диапазону `[i,` `j)`.	Пре	`T` является EmplaceConstructible из `*i` в `X`.
`X u(i, j)`			Пост	`std::distance(u.begin(), u.end()) == std::distance(i, j)` является `true`.
Выражение	Тип	Эффекты	Условия
`X(std::from_range, rg)` (с C++23)	`X`	Создаёт контейнер последовательности, равный, элемент за элементом, диапазону `rg`.	Пре	`T` является EmplaceConstructible в `X` из `*ranges::begin(rg)`.
`X(std::from_range, rg)` (с C++23)	`X`		Пост	Каждый итератор в диапазоне `rg` обращается к элементу один раз. `std::distance(begin(), end()) == ranges::distance(rg)` является `true`.
`X(il)` (с C++11)	`X`	Эквивалентно `X(il.begin(), il.end())`.	Нет явных требований
`a = il` (с C++11)	`X&`	Присваивает диапазон, представленный `il` в `a`.^[2]	Пре	`T` является CopyInsertable и CopyAssignable.
`a = il` (с C++11)	`X&`	Присваивает диапазон, представленный `il` в `a`.^[2]	Пост	Существующие элементы `a` уничтожаются или присваиваются.
`a.emplace(p, args)` (с C++11)	`iterator`	Вставляет объект типа `T`, созданный с помощью `std::forward<Args>(args)` перед `p`.	Пре	`T` является EmplaceConstructible.
`a.emplace(p, args)` (с C++11)	`iterator`		Пост	Возвращаемый итератор указывает на элемент, созданный из `args` в `a`.
`a.insert(p, t)`	`iterator`	Вставляет копию `t` перед `p`.	Пре	`T` является CopyInsertable.
`a.insert(p, t)`	`iterator`	Вставляет копию `t` перед `p`.	Пост	Возвращаемый итератор указывает на копию `t` вставленной в `a`.
`a.insert(p, rv)` (с C++11)	`iterator`	Вставляет копию `rv` перед `p`, возможно, используя семантику перемещения.	Пре	`T` является MoveInsertable.
`a.insert(p, rv)` (с C++11)	`iterator`		Пост	Возвращаемый итератор указывает на копию `rv` вставленной в `a`.
`a.insert(p, n, t)`	`iterator`	Вставляет `n` копий `t` перед `p`.	Пре	`T` является CopyInsertable и CopyAssignable.
`a.insert(p, n, t)`	`iterator`	Вставляет `n` копий `t` перед `p`.	Пост	Возвращаемый итератор указывает на копию первого вставленного элемента в `a` или является `p` для `n == 0`.
`a.insert(p, i, j)`	`iterator`	Вставляет копии элементов в `[i,` `j)` перед `p`.	Пре	`T` является EmplaceConstructible и `i` и `j` не находятся в `a`.
`a.insert(p, i, j)`	`iterator`	Вставляет копии элементов в `[i,` `j)` перед `p`.	Пост	Каждый итератор в `[i,` `j)` обращается к элементу один раз. Возвращаемый итератор указывает на копию первого вставленного элемента в `a` или является `p` для `i == j`.
`a.insert_range(p, rg)` (с C++23)	`iterator`	Вставляет копии элементов в `rg` перед `p`.	Пре	`T` является EmplaceConstructible в `X` из `*ranges::begin(rg)`. `rg` и `a` не перекрываются.
`a.insert_range(p, rg)` (с C++23)	`iterator`	Вставляет копии элементов в `rg` перед `p`.	Пост	Каждый итератор в диапазоне `rg` обращается к элементу один раз. Возвращаемый итератор указывает на копию первого вставленного элемента в `a` или на `p` если `rg` пустой.
`a.insert(p, il)` (с C++11)	`iterator`	Эквивалентно `a.insert(p, il.begin(), il.end())`.	Пре	Нет явных требований
`a.insert(p, il)` (с C++11)	`iterator`	Эквивалентно `a.insert(p, il.begin(), il.end())`.	Пост	Возвращаемый итератор указывает на копию первого вставленного элемента в `a` или является `p` если `il` пустой.
`a.erase(q)`	`iterator`	Удаляет элемент, на который указывает `q`.	Пре	Нет явных требований
`a.erase(q)`	`iterator`	Удаляет элемент, на который указывает `q`.	Пост	Возвращаемый итератор указывает на элемент, непосредственно следующий за `q` перед удалением, или `a.end()` если такого элемента не существует.
`a.erase(q1, q2)`	`iterator`	Удаляет элементы в `[q1,` `q2)`.	Пре	Нет явных требований
`a.erase(q1, q2)`	`iterator`	Удаляет элементы в `[q1,` `q2)`.	Пост	Возвращаемый итератор указывает на элемент, на который указывал `q2` до любого удаления, или `a.end()` если такого элемента не существует.
`a.clear()`	void	Уничтожает все элементы в `a`.	Пре	Нет явных требований
`a.clear()`	void	Уничтожает все элементы в `a`.	Пост	Все ссылки, указатели и итераторы становятся недействительными, включая конечный итератор. `a.empty()` является `true`.
`a.assign(i, j)`	void	Заменяет элементы в `a` копией `[i,` `j)`.	Пре	`T` является EmplaceConstructible. `i` и `j` не находятся в `a`.
`a.assign(i, j)`	void	Заменяет элементы в `a` копией `[i,` `j)`.	Пост	Каждый итератор в `[i,` `j)` обращается к элементу один раз.
`a.assign_range(rg)` (с C++23)	void	Заменяет элементы в `a` копией каждого элемента в `rg`.	Пре	`T`^[3] является EmplaceConstructible в `X` из `*ranges::begin(rg)`. `rg` и `a` не перекрываются.
`a.assign_range(rg)` (с C++23)	void	Заменяет элементы в `a` копией каждого элемента в `rg`.	Пост	Каждый итератор в диапазоне `rg` обращается к элементу один раз. Все ссылки, указатели и итераторы становятся недействительными.
`a.assign(il)` (с C++11)	void	Эквивалентно `a.assign(il.begin(), il.end())`.	Нет явных требований
`a.assign(n, t)`	void	Заменяет элементы в `a` на `n` копий `t`.	Пре	`T` является CopyInsertable и CopyAssignable.
`a.assign(n, t)`	void	Заменяет элементы в `a` на `n` копий `t`.	Пост	Нет явных требований
Примечания
Для выражения, чьи эффекты эквивалентны другим операциям, условия выражений внутри этих операций наследуются поверх условий, указанных в таблице. `std::array` поддерживает присваивание из списка инициализации, но не из `std::initializer_list`. `T` и `R` - типы такие, что `ranges::assignable_from<T&, ranges::range_reference_t<R>>` моделируется.

Дополнительные операции

Следующие выражения должны быть валидными и иметь указанные эффекты для последовательных контейнеров, все операции кроме prepend_range и append_range(с C++23) занимают амортизированное постоянное время:

Выражение	Тип	Эффекты	Предварительные условия^[1]	Контейнеры
`a.front()`	`reference`, или `const_reference` для const `a`	Возвращает `*a.begin()`.	Нет явного требования	`std::basic_string` `std::array` `std::deque` `std::forward_list` `std::list` `std::vector`
`a.back()`	`reference`, или `const_reference` для const `a`	Эквивалентно `auto tmp = a.end();--tmp;return *tmp;`.	Нет явного требования	`std::basic_string` `std::array` `std::deque` `std::list` `std::vector`
`a.emplace_front(args)` (с C++11)	void	Добавляет в начало `T` с помощью `std::forward<Args> (args)...`.	`T` является EmplaceConstructible в `X` из `args`.	`std::deque` `std::forward_list` `std::list`
`a.emplace_back(args)` (с C++11)	void	Добавляет в конец `T` с помощью `std::forward<Args> (args)...`.	`T` является EmplaceConstructible в `X` из `args`.	`std::deque` `std::list` `std::vector`
`a.push_front(t)`	void	Добавляет в начало копию `t`.	`T` является CopyInsertable в `X`.	`std::deque` `std::forward_list` `std::list`
`a.push_front(rv)` (с C++11)	void	Добавляет в начало копию `rv`, возможно, с использованием семантики перемещения.	`T` является MoveInsertable в `X`.	`std::deque` `std::forward_list` `std::list`
`a.prepend_range(rg)` (с C++23)	void	Вставляет^[2] копии элементов в `rg` перед `begin()`, каждый итератор в `rg` дериференцируется один раз.	`T` является EmplaceConstructible в `X` из `*ranges::begin(rg)`.	`std::deque` `std::forward_list` `std::list`
`a.push_back(t)`	void	Добавляет в конец копию `t`.	`T` является CopyInsertable в `X`.	`std::basic_string` `std::deque` `std::list` `std::vector`
`a.push_back(rv)` (с C++11)	void	Добавляет в конец копию `rv`, возможно, с использованием семантики перемещения.	`T` является MoveInsertable в `X`.	`std::basic_string` `std::deque` `std::list` `std::vector`
`a.append_range(rg)` (с C++23)	void	Вставляет^[2] копии элементов в `rg` перед `end()`, каждый итератор в `rg` дериференцируется один раз.	`T` является EmplaceConstructible в `X` из `*ranges::begin(rg)`.	`std::deque` `std::list` `std::vector`
`a.pop_front()`	void	Удаляет первый элемент.	`a.empty()` является `false`.	`std::deque` `std::forward_list` `std::list`
`a.pop_back()`	void	Удаляет последний элемент.	`a.empty()` является `false`.	`std::basic_string` `std::deque` `std::list` `std::vector`
`a[n]`	`reference`, или `const_reference` для const `a`	Эквивалентно `return *(a.begin() + n);`.	Нет явного требования	`std::basic_string` `std::array` `std::deque` `std::vector`
`a.at(n)`	`reference`, или `const_reference` для const `a`	Возвращает `*(a.begin() + n)`, выбрасывает `std::out_of_range` если `n >= size()`.	Нет явного требования	`std::basic_string` `std::array` `std::deque` `std::vector`
Примечания
Для выражения, эффект которого эквивалентен другим операциям, предварительные условия выражений внутри этих операций наследуются поверх предварительных условий, перечисленных в таблице. Порядок вставки, относительно порядка элементов в `rg`, не изменяется.

Кроме того, для каждого последовательного контейнера:

Шаблон конструктора, принимающий два итератора ввода, и перегруженные шаблоны-члены функций insert, append, assign, replace принимающие два итератора ввода, не участвуют в разрешении перегрузки, если соответствующий шаблонный аргумент не удовлетворяет LegacyInputIterator.

Руководство по выводу, имеющее либо LegacyInputIterator, либо Allocator шаблонный параметр, не участвует в разрешении перегрузки, если для этого параметра выводится тип, не соответствующий итератору ввода или аллокатору соответственно.

(с C++17)

Последовательные контейнеры в стандартной библиотеке

basic_string	хранит и обрабатывает последовательности символов (шаблон класса)
array (C++11)	статический непрерывный массив (шаблон класса)
vector	динамический непрерывный массив (шаблон класса)
deque	двустороннюю очередь (шаблон класса)
forward_list (C++11)	односвязный список (шаблон класса)
list	двусвязный список (шаблон класса)

Компромиссы/Примечания по использованию

`std::vector`	Быстрый доступ, но вставки/удаления в основном неэффективны
`std::array`	Быстрый доступ, но фиксированное число элементов
`std::list` `std::forward_list`	Эффективные вставки/удаления в середине последовательности
`std::deque`	Эффективные вставки/удаления в начале и в конце последовательности

Отчеты об ошибках

Следующие отчеты об ошибках, изменяющих поведение, были применены ретроактивно к ранее опубликованным стандартам C++.

DR	Применимо к	Поведение, как опубликовано	Корректное поведение
LWG 139	C++98	необязательные операции не были обязательными для реализации для указанных контейнеров	требуются с амортизированным временем
LWG 149	C++98	`a.insert(p, t)` вернул `iterator` , в то время как `a.insert(p, n, t)` и `a.insert(p, n, t)` вернули void	они все возвращают `iterator`
LWG 151	C++98	`q1` должно быть разыменовываемым^[1]	он может быть не разыменовываемым
LWG 355	C++98	вызов `a.back()` или `a.pop_back()` будет выполнять `--a.end()`, что опасно^[2]	уменьшает копию `a.end()` вместо
LWG 589	C++98	элементы, на которые ссылаются `i` и `j`, могут не быть преобразуемы в `value_type`	они неявно преобразуются в `value_type`
LWG 3927	C++98	оператор[] не имел неявного требования	добавлено неявное требование

Это ошибка, потому что она делает поведение a.erase(a.begin(), a.end()) неопределенным, если a является пустым контейнером.
Если тип a.end() является фундаментальным типом, --a.end() некорректно сформирован. Это опасно, когда тип a является шаблонным, в этом случае эту ошибку может быть сложно найти.