Namespaces
Variants

C++ named requirements: SequenceContainer

From cppreference.net
C++
C++ named requirements

SequenceContainer — это Container , который хранит объекты одного типа в линейном расположении.

Содержание

Требования

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

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

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

  • C удовлетворяет требованиям Container .
  • Следующие операторы и выражения являются корректными и имеют указанную семантику:
Базовые операции
(требуются для всех контейнеров последовательностей в стандартной библиотеке кроме std::array (начиная с C++11) )
Утверждение Семантика [1]
C c ( n, t ) ; Эффект Создает контейнер-последовательность, содержащий n копий элемента t .
Предусловие

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

(начиная с C++11)
Постусловие std:: distance ( c. begin ( ) , c. end ( ) ) равно n .
C c ( i, j ) ; Эффект Создает контейнер-последовательность, равный, поэлементно, диапазону [ i , j ) .
  • Каждый итератор в диапазоне [ i , j ) разыменовывается ровно один раз.
Предусловие

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 разыменовывается ровно один раз.
Предусловие 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
Предусловие T является CopyInsertable в C и CopyAssignable .
Постусловие Существующие элементы v либо уничтожаются, либо присваиваются.
v. emplace ( p, args )
(начиная с C++11) 		Iter Эффект Вставляет объект типа T , созданный с помощью std:: forward < Args > ( args ) ... перед p .
Возвращаемое значение Итератор, указывающий на новый элемент, созданный из args в v .
Предусловие T является EmplaceConstructible в C из args .
v. insert ( p, t ) Iter Эффект Вставляет копию t перед p .
Возвращаемое значение Итератор, указывающий на копию t , вставленную в v .
Предусловие

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

(начиная с C++11)
v. insert ( p, rv )
(начиная с C++11) 		Iter Эффект Вставляет копию rv перед p , возможно используя семантику перемещения.
Возвращаемое значение Итератор, указывающий на копию rv , вставленную в v .
Предусловие T является MoveInsertable в C .
v. insert ( p, n, t ) Iter Эффект Вставляет n копий t перед p .
Возвращаемое значение Итератор, указывающий на копию первого элемента, вставленного в v , или p , если n равно ​ 0 ​ .
Предусловие

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

(начиная с C++11)
v. insert ( p, i, j ) Iter Эффект Вставляет копии элементов из диапазона [ i , j ) перед p .
  • Каждый итератор в диапазоне [ i , j ) разыменовывается ровно один раз.
Возвращаемое значение Итератор, указывающий на копию первого элемента, вставленного в v , или p , если i == j равно true .
Предусловие
(начиная с C++11)
  • i и j не находятся в v .
v. insert_range ( p, rg )
(начиная с C++23) 		Iter Эффект Вставляет копии элементов из rg перед p .
  • Каждый итератор в диапазоне rg разыменовывается ровно один раз.
Возвращаемое значение Итератор, указывающий на копию первого элемента, вставленного в v , или p , если rg пуст.
Предусловие
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 и может сделать недействительным итератор, указывающий за последний элемент.
Постусловие v. empty ( ) является true .
Сложность Линейная.
v. assign ( i, j ) void Эффект Заменяет элементы в v копией элементов из диапазона [ i , j ) .
  • Инвалидирует все ссылки, указатели и итераторы, ссылающиеся на элементы v .
  • Каждый итератор в диапазоне [ i , j ) разыменовывается ровно один раз.
Предусловие
  • 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 разыменовывается ровно один раз.
Предусловие
v. assign ( il )
(начиная с C++11) 		void Эквивалентно v. assign ( il. begin ( ) , il. end ( ) ) .
v. assign ( n, t ) void Эффект Заменяет элементы в v на n копий t .
Предусловие

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 ( )
Предусловие T является EmplaceConstructible в C из args .
v. emplace_back ( args )
(начиная с C++11) 		void Контейнеры vector , inplace_vector , deque , list
Эффект Добавляет объект типа T , созданный с помощью std:: forward < Args > ( args ) ... .
Возвращаемое значение v. back ( )
Предусловие T является EmplaceConstructible в C из args .
v. push_front ( t ) void Контейнеры deque , list , forward_list
Эффект Добавляет копию t в начало.
Предусловие

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

(начиная с C++11)
v. push_front ( rv )
(начиная с C++11) 		void Контейнеры deque , list , forward_list
Эффект Добавляет копию rv в начало, возможно используя семантику перемещения.
Предусловие T является MoveInsertable в C .
v. prepend_range ( rg )
(начиная с C++23) 		void Контейнеры deque , list , forward_list
Эффект Вставляет [6] копии элементов из rg перед v. begin ( ) .
  • Каждый итератор в диапазоне rg разыменовывается ровно один раз.
Предусловие T является EmplaceConstructible в C из * ranges:: begin ( rg ) .
v. push_back ( t ) void Контейнеры basic_string , vector , inplace_vector , deque , list
Эффект Добавляет копию t .
Предусловие

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

(начиная с C++11)
v. push_back ( rv )
(начиная с C++11) 		void Контейнеры basic_string , vector , inplace_vector , deque , list
Эффект Добавляет копию rv , возможно используя семантику перемещения.
Предусловие T является MoveInsertable в C .
v. append_range ( rg )
(начиная с C++23) 		void Контейнеры vector , inplace_vector , deque , list
Эффект Вставляет [6] копии элементов из rg перед v. end ( ) .
  • Каждый итератор в диапазоне rg разыменовывается ровно один раз.
Предусловие T является EmplaceConstructible в C из * ranges:: begin ( rg ) .
v. pop_front ( ) void Контейнеры deque , list , forward_list
Эффект Уничтожает первый элемент.
Условие a. empty ( ) имеет значение false .
v. pop_back ( ) void Контейнеры basic_string , vector , inplace_vector , deque , list
Эффект Уничтожает последний элемент.
Условие 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 .
Примечания
  1. ↑ Для выражения, эффект которого эквивалентен некоторым другим операциям, условия выражений внутри этих операций наследуются поверх условий, перечисленных в таблице.
  2. ↑ std::array поддерживает присваивание из списка инициализации в фигурных скобках , но не из std::initializer_list .
  3. ↑ Все операции ниже кроме prepend_range и append_range (since C++23) занимают амортизированное постоянное время.
  4. ↑ В C++98, tmp объявлялся как имеющий тип C::iterator .
  5. ↑ В C++98, tmp объявлялся как имеющий тип C::const_iterator .
  6. ↑ 6.0 6.1 Порядок вставки относительно порядка элементов в rg является необращающим.

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

  • Шаблон конструктора, принимающий два итератора ввода, и перегруженные шаблоны функций-членов insert , append , assign , replace , принимающие два итератора ввода, не участвуют в разрешении перегрузки, если соответствующий аргумент шаблона не удовлетворяет требованиям LegacyInputIterator .
  • Руководство по выводу, которое имеет либо параметр шаблона LegacyInputIterator , либо параметр шаблона Allocator , не участвует в разрешении перегрузки, если для этого параметра выводится тип, который не соответствует требованиям входного итератора или аллокатора соответственно.
(начиная с C++17)

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

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

хранит и манипулирует последовательностями символов
(class template)
(C++11)
массив фиксированного размера с непрерывным расположением элементов
(class template)
изменяемый массив с непрерывным расположением элементов
(class template)
(C++26)
изменяемый массив с фиксированной ёмкостью и inplace расположением элементов
(class template)
двусторонняя очередь
(class template)
(C++11)
односвязный список
(class template)
двусвязный список
(class template)

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

Контейнер Преимущества Недостатки
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 также считались SequenceContainer s [3] 		они не являются SequenceContainer s
LWG 2231 C++11 требование сложности для v. clear ( )
было ошибочно опущено в C++11 		сложность подтверждена как линейная
LWG 3927 C++98 operator [ ] не имел неявного требования добавлено неявное требование
  1. ↑ Это является дефектом, поскольку делает поведение v. erase ( v. begin ( ) , v. end ( ) ) неопределённым, если v является пустым контейнером.
  2. ↑ Если тип v. end ( ) является фундаментальным типом, -- v. end ( ) является некорректной конструкцией. Это становится опасным, когда тип v шаблонизирован — в этом случае данную ошибку может быть сложно обнаружить.
  3. ↑ Они не были задокументированы как SequenceContainer в стандарте C++98.