Namespaces
Variants
Actions

C++ named requirements: SequenceContainer

From cppreference.com
< cpp‎ | named req
 
 
C++ named requirements
 

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

Contents

[edit] Requirements

Given the following types and values:

Type Definition
C a sequence container class
T the element type of C
A the allocator type of C:
R (since C++23) a type that models container-compatible-range <T>
Args (since C++11) a template parameter pack
Iter C::iterator
Ref C::reference
CRef C::const_reference
Value Definition
v a value of type C
cv a value of type const C
i, j LegacyInputIterators such that [i, j) is a valid range and that the iterators refer to elements implicitly convertible to C::value_type
rg (since C++23) a value of type R
il (since C++11) a value of type std::initializer_list <C::value_type>
n a value of type C::size_type
p a valid const iterator into v
q a valid dereferenceable const iterator into v
q1, q2 const iterators into v such that [q1, q2) is a valid range
t a value(until C++11)an lvalue or const rvalue(since C++11) of type C::value_type
rv (since C++11) a non-const rvalue of type C::value_type
args (since C++11) a function parameter pack with the pattern Arg&&

C satisfies the requirements of SequenceContainer if all following conditions are satisfied:

  • C satisfies the requirements of Container.
  • The following statements and expressions are well-formed and have the specified semantics:
Basic operations
(required for all sequence containers in the standard library except std::array (since C++11))
Statement     Semantics[1]
C c(n, t); Effect Constructs the sequence container holding n copies of t.
Precondition

T is CopyInsertable into C.

(since C++11)
Postcondition  std::distance (c.begin(), c.end()) is n.
C c(i, j); Effect Constructs the sequence container equal, element-wise, to the range [i, j).
  • Each iterator in the range [i, j) is dereferenced exactly once.
Precondition

T is EmplaceConstructible into C from *i.

(since C++11)
Postcondition std::distance (c.begin(), c.end()) is std::distance (i, j).
Expression  Type  Semantics
C(std::from_range, rg)
(since C++23) 		C Effect Constructs the sequence container equal, element-wise, to the range rg.
  • Each iterator in the range rg is dereferenced exactly once.
Precondition T is EmplaceConstructible into X from *ranges::begin (rg).
Postcondition std::distance (begin(), end()) is ranges::distance (rg).
C(il)
(since C++11) 		C Equivalent to C(il.begin(), il.end()).
v = il
(since C++11) 		C& Effect Assigns the range represented by il into v.[2]
Return value *this
Precondition T is CopyInsertable into C and CopyAssignable.
Postcondition Existing elements of v are either destroyed or assigned to.
v.emplace(p, args)
(since C++11) 		Iter  Effect Insert an object of type T, constructed with std::forward <Args>(args)... before p.
Return value An iterator that points to the new element constructed from args into v.
Precondition T is EmplaceConstructible into C from args.
v.insert(p, t) Iter Effect Inserts a copy of t before p.
Return value An iterator that points to the copy of t inserted into v.
Precondition

T is CopyInsertable into C.

(since C++11)
v.insert(p, rv)
(since C++11) 		Iter Effect Inserts a copy of rv before p, possibly using move semantics.
Return value An iterator that points to the copy of rv inserted into v.
Precondition T is MoveInsertable into C.
v.insert(p, n, t) Iter Effect Inserts n copies of t before p.
Return value An iterator that points to the copy of the first element inserted into v, or p if n is ​0​.
Precondition

T is CopyInsertable into C and CopyAssignable.

(since C++11)
v.insert(p, i, j) Iter Effect Inserts copies of elements in [i, j) before p.
  • Each iterator in the range [i, j) is dereferenced exactly once.
Return value An iterator that points to the copy of the first element inserted into v, or p if i == j is true.
Precondition
(since C++11)
  • i and j are not in v.
v.insert_range(p, rg)
(since C++23) 		Iter Effect Inserts copies of elements in rg before p.
  • Each iterator in the range rg is dereferenced exactly once.
Return value An iterator that points to the copy of the first element inserted into v, or p if rg is empty.
Precondition
v.insert(p, il)
(since C++11) 		Iter Equivalent to v.insert(p, il.begin(), il.end()).
v.erase(q) Iter Effect Erases the element pointed to by q.
Return value An iterator that points to the element immediately following q prior to the element being erased, or v.end() if no such element exists.
v.erase(q1, q2) Iter Effect Erases elements in [q1, q2).
Return value An iterator that points to the element pointed to by q2 prior to any elements being erased, or v.end() if no such element exists.
v.clear() void Effect Destroys all elements in v.
  • Invalidates all references, pointers, and iterators referring to the elements of v and may invalidate the past-the-end iterator.
Postcondition v.empty() is true.
Complexity Linear.
v.assign(i, j) void Effect Replaces elements in v with a copy of [i, j).
  • Invalidates all references, pointers and iterators referring to the elements of v.
  • Each iterator in [i, j) is dereferenced exactly once.
Precondition
(since C++11)
  • i and j are not in v.
v.assign_range(rg)
(since C++23) 		void Effect Replaces elements in v with a copy of each element in rg.
  • If std::assignable_from
        <T&, ranges::range_reference_t <R>>     is not modeled, the program is ill-formed.
  • Invalidates all references, pointers and iterators referring to the elements of v.
  • Each iterator in the range rg is dereferenced exactly once.
Precondition
v.assign(il)
(since C++11) 		void Equivalent to v.assign(il.begin(), il.end()).
v.assign(n, t) void Effect Replaces elements in v with n copies of t.
Precondition

T is CopyInsertable into C and CopyAssignable.

(since C++11)
    Extra operations[3]
(only required for specified sequence containers, omitting std::)
Expression  Type  Semantics
v.front() Ref Containers basic_string, array, vector, inplace_vector, deque, list, forward_list
Return value *v.begin()
cv.front() CRef Containers basic_string, array, vector, inplace_vector, deque, list, forward_list
Return value *cv.begin()
v.back() Ref Containers basic_string, array, vector, inplace_vector, deque, list
Equivalent to auto tmp = v.end(); --tmp; return *tmp;[4] .
cv.back() CRef Containers basic_string, array, vector, inplace_vector, deque, list
Equivalent to auto tmp = cv.end(); --tmp; return *tmp;[5] .
v.emplace_front(args)
(since C++11) 		void Containers deque, list, forward_list
Effect Prepends an object of type T constructed with std::forward <Args>(args)....
Return value v.front()
Precondition T is EmplaceConstructible into C from args.
v.emplace_back(args)
(since C++11) 		void Containers vector, inplace_vector, deque, list
Effect Appends an object of type T constructed with std::forward <Args>(args)....
Return value v.back()
Precondition T is EmplaceConstructible into C from args.
v.push_front(t) void Containers deque, list, forward_list
Effect Prepends a copy of t.
Precondition

T is CopyInsertable into C.

(since C++11)
v.push_front(rv)
(since C++11) 		void Containers deque, list, forward_list
Effect Prepends a copy of rv, possibly using move semantics.
Precondition T is MoveInsertable into C.
v.prepend_range(rg)
(since C++23) 		void Containers deque, list, forward_list
Effect Inserts[6] copies of elements in rg before v.begin().
  • Each iterator in the range rg is dereferenced exactly once.
Precondition T is EmplaceConstructible into C from *ranges::begin (rg).
v.push_back(t) void Containers basic_string, vector, inplace_vector, deque, list
Effect Appends a copy of t.
Precondition

T is CopyInsertable into C.

(since C++11)
v.push_back(rv)
(since C++11) 		void Containers basic_string, vector, inplace_vector, deque, list
Effect Appends a copy of rv, possibly using move semantics.
Precondition T is MoveInsertable into C.
v.append_range(rg)
(since C++23) 		void Containers vector, inplace_vector, deque, list
Effect Inserts[6] copies of elements in rg before v.end().
  • Each iterator in the range rg is dereferenced exactly once.
Precondition T is EmplaceConstructible into C from *ranges::begin (rg).
v.pop_front() void Containers deque, list, forward_list
Effect Destroys the first element.
Precondition a.empty() is false.
v.pop_back() void Containers basic_string, vector, inplace_vector, deque, list
Effect Destroys the last element.
Precondition a.empty() is false.
v[n] Ref Containers basic_string, array, vector, inplace_vector, deque
Equivalent to return *(v.begin() + n);.
cv[n] CRef Containers basic_string, array, vector, inplace_vector, deque
Equivalent to return *(cv.begin() + n);.
v.at(n) Ref Containers basic_string, array, vector, inplace_vector, deque
Return value *(v.begin() + n)
Exceptions Throws std::out_of_range if n >= v.size() is true.
cv.at(n) CRef Containers basic_string, array, vector, inplace_vector, deque
Return value *(cv.begin() + n)
Exceptions Throws std::out_of_range if n >= cv.size() is true.
Notes
  1. ↑ For an expression whose effect is equivalent to some other operations, the conditions of the expressions inside those operations are inherited on top of the conditions listed in the table.
  2. ↑ std::array supports assignment from a brace-enclosed initializer list, but not from an std::initializer_list .
  3. ↑ All operations below except prepend_range and append_range(since C++23) take amortized constant time.
  4. ↑ In C++98, tmp was declared to have type C::iterator.
  5. ↑ In C++98, tmp was declared to have type C::const_iterator.
  6. ↑ 6.0 6.1 Insertion order, relative to order of elements in rg, is non-reversing.

Additionally, for every sequence container:

  • A constructor template that takes two input iterators and the member function template overloads of insert, append, assign, replace that take two input iterators do not participate in overload resolution if the corresponding template argument does not satisfy LegacyInputIterator.
  • A deduction guide that has either a LegacyInputIterator or an Allocator template parameter does not participate in overload resolution if the type that does not qualify as an input iterator or an allocator respectively is deduced for that parameter.
(since C++17)

[edit] Standard library

The following standard library string types and containers satisfy the SequenceContainer requirements:

stores and manipulates sequences of characters
(class template) [edit]
(C++11)
fixed-sized inplace contiguous array
(class template) [edit]
resizable contiguous array
(class template) [edit]
resizable, fixed capacity, inplace contiguous array
(class template) [edit]
double-ended queue
(class template) [edit]
singly-linked list
(class template) [edit]
doubly-linked list
(class template) [edit]

[edit] Usage notes

Container Pros Cons
std::vector Fast access, contiguous storage Mostly inefficient insertions/deletions
std::inplace_vector Fast access, inplace contiguous storage Fixed capacity and mostly inefficient insertions/deletions
std::array Fast access, inplace contiguous storage Fixed number of elements and no insertion/deletion
std::deque Fast access, efficient insertion/deletion at the beginning/end Inefficient insertion/deletion in the middle of the sequence
std::list
std::forward_list 		Efficient insertion/deletion in the middle of the sequence Access is mostly linear-time

[edit] Defect reports

The following behavior-changing defect reports were applied retroactively to previously published C++ standards.

DR Applied to Behavior as published Correct behavior
LWG 139 C++98 the optional operations were not required to
be implemented for the designated containers 		required with amortized time
LWG 149 C++98 v.insert(p, t) returned Iter while
v.insert(p, n, t) and v.insert(p, n, t)
returned void 		they all return Iter
LWG 151 C++98 q1 was required to be dereferenceable[1] it can be non-dereferenceable
LWG 355 C++98 calling v.back() or v.pop_back() would
execute --v.end(), which is dangerous[2] 		decrements a copy
of v.end() instead
LWG 589 C++98 the elements that i and j refer to
might not be convertible to C::value_type 		they are implicitly
convertible to C::value_type
LWG 2194 C++11 std::queue , std::priority_queue and
std::stack were also SequenceContainers[3] 		they are not SequenceContainers
LWG 2231 C++11 the complexity requirement of v.clear()
was mistakenly omitted in C++11 		complexity reaffirmed as linear
LWG 3927 C++98 operator[] had no implicit requirement added the implicit requirement
  1. ↑ It is a defect because it makes the behavior of v.erase(v.begin(), v.end()) undefined is v is an empty container.
  2. ↑ If the type of v.end() is a fundamental type, --v.end() is ill-formed. It is dangerous when the type of v is templated, in this case this bug can be difficult to be found.
  3. ↑ They were not documented as SequenceContainers in C++98.

AltStyle によって変換されたページ (->オリジナル) /