Именованные требования C++: SequenceContainer (Контейнер последовательности)

Контейнер последовательности (SequenceContainer) — это контейнер, который хранит объекты одного типа в линейном порядке.

Требования

Учитывая следующие типы и значения:

Тип	Определение
`C`	класс контейнера последовательности
`T`	тип элементов `C`
`A`	тип аллокатора `C`: `C::allocator_type`, если он существует, иначе std::allocator<T>
`R` (начиная с C++23)	тип, который моделирует `container-compatible-range` `<T>`
`Args` (начиная с C++11)	пакет параметров шаблона
`Iter`	`C::iterator`
`Ref`	`C::reference`
`CRef`	`C::const_reference`
Значение	Определение
`v`	значение типа `C`
`cv`	значение типа constC
`i`, `j`	LegacyInputIterators такие, что `[i,` `j)` является допустимым диапазоном, и итераторы ссылаются на элементы, неявно преобразуемые в `C::value_type`
`rg` (начиная с C++23)	значение типа `R`
`il` (начиная с C++11)	значение типа std::initializer_list<C::value_type>
`n`	значение типа `C::size_type`
`p`	допустимый константный итератор в `v`
`q`	допустимый разыменуемый константный итератор в `v`
`q1`, `q2`	константные итераторы в `v` такие, что `[q1,` `q2)` является допустимым диапазоном
`t`	значение(до C++11)lvalue или константное rvalue(начиная с C++11) типа `C::value_type`
`rv` (начиная с C++11)	неконстантное rvalue типа `C::value_type`
`args` (начиная с C++11)	пакет параметров функции с шаблоном `Arg&&`

C удовлетворяет требованиям SequenceContainer, если выполнены все следующие условия:

C удовлетворяет требованиям Container.
Следующие выражения и операторы хорошо сформированы (well-formed) и имеют указанную семантику:

Основные операции
(требуются для всех контейнеров последовательности в стандартной библиотеке, за исключением std::array(начиная с C++11))

Оператор (Statement) Семантика^[1]

C c(n, t); Эффект Конструирует контейнер последовательности, содержащий n копий t.

Предпосылка (Precondition)

T является CopyInsertable в C.

(начиная с C++11)

Постусловие std::distance(c.begin(), c.end()) равно n.

C c(i, j);

Эффект

Конструирует контейнер последовательности, равный по элементам диапазону [i, j).

Каждый итератор в диапазоне [i, j) разыменовывается ровно один раз.

Предпосылка (Precondition)

T является EmplaceConstructible в C из *i.

(начиная с C++11)

Постусловие std::distance(c.begin(), c.end()) равно std::distance(i, j).

Выражение Тип Семантика

C(std::from_range, rg)
(начиная с C++23)

C

Эффект

Конструирует контейнер последовательности, равный по элементам диапазону rg.

Каждый итератор в диапазоне rg разыменовывается ровно один раз.

Предпосылка (Precondition) T является EmplaceConstructible в X из *ranges::begin(rg).

Постусловие std::distance(begin(), end()) равно ranges::distance(rg).

C(il)
(начиная с C++11) C Эквивалентно C(il.begin(), il.end()).

v = il
(начиная с C++11) C& Эффект Присваивает диапазон, представленный il, в v.^[2]

Возвращаемое значение *this

Предпосылка (Precondition) T является CopyInsertable в C и CopyAssignable.

Постусловие Существующие элементы v либо уничтожаются, либо им присваиваются новые значения.

v.emplace(p, args)
(начиная с C++11) Iter Эффект Вставляет объект типа T, сконструированный из std::forward<Args>(args)..., перед p.

Возвращаемое значение Итератор, указывающий на новый элемент, сконструированный из args в v.

Предпосылка (Precondition) T является EmplaceConstructible в C из args.

v.insert(p, t) Iter Эффект Вставляет копию t перед p.

Возвращаемое значение Итератор, указывающий на копию t, вставленную в v.

Предпосылка (Precondition)

T является CopyInsertable в C.

(начиная с C++11)

v.insert(p, rv)
(начиная с C++11) Iter Эффект Вставляет копию rv перед p, возможно, используя семантику перемещения.

Возвращаемое значение Итератор, указывающий на копию rv, вставленную в v.

Предпосылка (Precondition) T является MoveInsertable в C.

v.insert(p, n, t) Iter Эффект Вставляет n копий t перед p.

Возвращаемое значение Итератор, указывающий на копию первого вставленного элемента в v, или p, если n равно 0.

Предпосылка (Precondition)

T является CopyInsertable в C и CopyAssignable.

(начиная с C++11)

v.insert(p, i, j)

Iter

Эффект

Вставляет копии элементов из [i, j) перед p.

Каждый итератор в диапазоне [i, j) разыменовывается ровно один раз.

Возвращаемое значение Итератор, указывающий на копию первого вставленного элемента в v, или p, если i == j равно true.

Предпосылка (Precondition)

T является EmplaceConstructible в C из *i.

(начиная с C++11)

i и j не находятся в v.

v.insert_range(p, rg)
(начиная с C++23)

Iter

Эффект

Вставляет копии элементов из rg перед p.

Каждый итератор в диапазоне rg разыменовывается ровно один раз.

Возвращаемое значение Итератор, указывающий на копию первого вставленного элемента в v, или p, если rg пуст.

Предпосылка (Precondition)

T является EmplaceConstructible в C из *ranges::begin(rg).
rg и v не пересекаются.

v.insert(p, il)
(начиная с C++11) Iter Эквивалентно v.insert(p, il.begin(), il.end()).

v.erase(q) Iter Эффект Удаляет элемент, на который указывает q.

Возвращаемое значение Итератор, указывающий на элемент, непосредственно следующий за q до удаления элемента, либо v.end(), если такого элемента не существует.

v.erase(q1, q2) Iter Эффект Удаляет элементы в [q1, q2).

Возвращаемое значение Итератор, указывающий на элемент, на который указывал q2 до удаления каких-либо элементов, либо v.end(), если такого элемента не существует.

v.clear()

void

Эффект

Уничтожает все элементы в v.

Делает недействительными все ссылки, указатели и итераторы, ссылающиеся на элементы v, и может сделать недействительным итератор, следующий за концом (past-the-end iterator).

Постусловие v.empty() равно true.

Сложность Линейная.

v.assign(i, j)

void

Эффект

Заменяет элементы в v копией элементов из [i, j).

Делает недействительными все ссылки, указатели и итераторы, ссылающиеся на элементы v.
Каждый итератор в [i, j) разыменовывается ровно один раз.

Предпосылка (Precondition)

T является EmplaceConstructible в C из *i.
T доступен для присваивания из *i.

(начиная с C++11)

i и j не находятся в v.

v.assign_range(rg)
(начиная с C++23)

void

Эффект

Заменяет элементы в v копией каждого элемента из rg.

Если std::assignable_from <T&, ranges::range_reference_t<R>> не смоделирован, программа сформирована некорректно.
Делает недействительными все ссылки, указатели и итераторы, ссылающиеся на элементы v.
Каждый итератор в диапазоне rg разыменовывается ровно один раз.

Предпосылка (Precondition)

T является EmplaceConstructible в C из *ranges::begin(rg).
rg и v не пересекаются.

v.assign(il)
(начиная с C++11) void Эквивалентно v.assign(il.begin(), il.end()).

v.assign(n, t) void Эффект Заменяет элементы в v на n копий t.

Предпосылка (Precondition)

T является CopyInsertable в C и CopyAssignable.

(начиная с C++11)

Дополнительные операции^[3]
(требуются только для указанных контейнеров последовательности, за исключением std::)

Выражение Тип Семантика

v.front() Ref Контейнеры basic_string, array, vector, inplace_vector, deque, list, forward_list

Возвращаемое значение *v.begin()

cv.front() CRef Контейнеры basic_string, array, vector, inplace_vector, deque, list, forward_list

Возвращаемое значение *cv.begin()

v.back() Ref Контейнеры basic_string, array, vector, inplace_vector, deque, list

Эквивалентно auto tmp = v.end(); --tmp; return *tmp;^[4].

cv.back() CRef Контейнеры basic_string, array, vector, inplace_vector, deque, list

Эквивалентно auto tmp = cv.end(); --tmp; return *tmp;^[5].

v.emplace_front(args)
(начиная с C++11) void Контейнеры deque, list, forward_list

Эффект Добавляет в начало объект типа T, сконструированный с использованием std::forward<Args>(args)....

Возвращаемое значение v.front()

Предпосылка (Precondition) T является EmplaceConstructible в C из args.

v.emplace_back(args)
(начиная с C++11) void Контейнеры vector, inplace_vector, deque, list

Эффект Добавляет в конец объект типа T, сконструированный с использованием std::forward<Args>(args)....

Возвращаемое значение v.back()

Предпосылка (Precondition) T является EmplaceConstructible в C из args.

v.push_front(t) void Контейнеры deque, list, forward_list

Эффект Добавляет в начало копию t.

Предпосылка (Precondition)

T является CopyInsertable в C.

(начиная с C++11)

v.push_front(rv)
(начиная с C++11) void Контейнеры deque, list, forward_list

Эффект Добавляет в начало копию rv, возможно, используя семантику перемещения.

Предпосылка (Precondition) T является MoveInsertable в C.

v.prepend_range(rg)
(начиная с C++23) void Контейнеры deque, list, forward_list

Эффект

Вставляет^[6] копии элементов из rg перед v.begin().

Каждый итератор в диапазоне rg разыменовывается ровно один раз.

Предпосылка (Precondition) T является EmplaceConstructible в C из *ranges::begin(rg).

v.push_back(t) void Контейнеры basic_string, vector, inplace_vector, deque, list

Эффект Добавляет в конец копию t.

Предпосылка (Precondition)

T является CopyInsertable в C.

(начиная с C++11)

v.push_back(rv)
(начиная с C++11) void Контейнеры basic_string, vector, inplace_vector, deque, list

Эффект Добавляет в конец копию rv, возможно, используя семантику перемещения.

Предпосылка (Precondition) T является MoveInsertable в C.

v.append_range(rg)
(начиная с C++23) void Контейнеры vector, inplace_vector, deque, list

Эффект

Вставляет^[6] копии элементов из rg перед v.end().

Каждый итератор в диапазоне rg разыменовывается ровно один раз.

Предпосылка (Precondition) T является EmplaceConstructible в C из *ranges::begin(rg).

v.pop_front() void Контейнеры deque, list, forward_list

Эффект Уничтожает первый элемент.

Предпосылка (Precondition) a.empty() не пусто (равно false).

v.pop_back() void Контейнеры basic_string, vector, inplace_vector, deque, list

Эффект Уничтожает последний элемент.

Предпосылка (Precondition) a.empty() не пусто (равно false).

v[n] Ref Контейнеры basic_string, array, vector, inplace_vector, deque

Эквивалентно return *(v.begin() + n);.

cv[n] CRef Контейнеры basic_string, array, vector, inplace_vector, deque

Эквивалентно return *(cv.begin() + n);.

v.at(n) Ref Контейнеры basic_string, array, vector, inplace_vector, deque

Возвращаемое значение *(v.begin() + n)

Исключения Выбрасывает std::out_of_range, если n >= v.size() выходит за пределы (равно true).

cv.at(n) CRef Контейнеры basic_string, array, vector, inplace_vector, deque

Возвращаемое значение *(cv.begin() + n)

Исключения Выбрасывает std::out_of_range, если n >= cv.size() выходит за пределы (равно true).

Примечания

Для выражения, чей эффект эквивалентен некоторым другим операциям, условия для выражений внутри этих операций наследуются в дополнение к условиям, перечисленным в таблице.
std::array поддерживает присваивание из списка инициализации в фигур скобках, но не из std::initializer_list.
Все приведенные ниже операции, за исключением prepend_range и append_range(начиная с C++23), выполняются за амортизированное константное время.
В C++98 тип tmp был объявлен как C::iterator.
В C++98 тип tmp был объявлен как C::const_iterator.
Порядок вставки относительно порядка элементов в rg сохраняется (не обращается).

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

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

Гид по выведению (deduction guide), имеющий либо параметр шаблона LegacyInputIterator, либо Allocator, не участвует в разрешении перегрузки, если для этого параметра выводится тип, который не квалифицируется соответственно как входной итератор или аллокатор.

(начиная с C++17)

Стандартная библиотека

Следующие типы строк и контейнеры стандартной библиотеки удовлетворяют требованиям SequenceContainer:

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

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

Контейнер	Преимущества	Недостатки
`std::vector`	Быстрый доступ, непрерывное хранение данных	Вставка и удаление в большинстве случаев неэффективны
std::inplace_vector	Быстрый доступ, непрерывное хранение данных во встроенном хранилище	Фиксированная ёмкость; вставка и удаление в большинстве случаев неэффективны
`std::array`	Быстрый доступ, непрерывное хранение данных во встроенном хранилище	Фиксированное количество элементов; вставка и удаление невозможны
`std::deque`	Быстрый доступ, эффективная вставка и удаление в начале и в конце	Вставка и удаление в середине последовательности неэффективны
`std::list` `std::forward_list`	Эффективная вставка и удаление в середине последовательности	Доступ в большинстве случаев выполняется за линейное время

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

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

DR	Применён к	Опубликованное поведение	Корректное поведение
LWG 139	C++98	не требовалось реализовывать необязательные операции для указанных контейнеров	требуется амортизированное время выполнения
LWG 149	C++98	`v.insert(p, t)` возвращал `Iter`, тогда как `v.insert(p, n, t)` и `v.insert(p, n, t)` возвращали void	все они возвращают `Iter`
LWG 151	C++98	`q1` должен был допускать разыменование^[1]	он может не допускать разыменования
LWG 355	C++98	вызов `v.back()` или `v.pop_back()` выполнял `--v.end()`, что небезопасно^[2]	вместо этого декрементируется копия `v.end()`
LWG 589	C++98	элементы, на которые ссылаются `i` и `j`, могли быть не преобразуемы в `C::value_type`	они неявно преобразуются в `C::value_type`
LWG 2194	C++11	`std::queue`, `std::priority_queue` и `std::stack` также являлись контейнерами-последовательностями^[3]	они не являются контейнерами-последовательностями
LWG 2231	C++11	требование к сложности `v.clear()` было случайно пропущено в C++11	подтверждена линейная сложность
LWG 3927	C++98	для operator[] не было неявного требования	добавлено неявное требование

Это является ошибкой, поскольку поведение v.erase(v.begin(), v.end()) не определено, если v — пустой контейнер.
Если тип v.end() является фундаментальным типом, --v.end() некорректно сформирован. Это опасно, когда тип v является шаблонным: в таком случае эту ошибку бывает трудно обнаружить.
В C++98 они не были указаны в документации как контейнеры-последовательности.

© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/cpp/named_req/SequenceContainer