Przejdź do głównej zawartości

C++ named requirements: SequenceContainer

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

Requirements

The type X satisfies SequenceContainer if

Given

  • T, the element type of X
  • A, the allocator type of X: X::allocator_type if it exists, otherwise std::allocator<T>
  • a, an rvalue expression of type X
  • p, a valid const iterator into a
  • q, a valid dereferenceable const iterator into a
  • q1 and q2, two const iterators into a such that [q1, q2) is a valid range
  • i and j, LegacyInputIterators such that [i, j) is a valid range and that the iterators refer to elements implicitly convertible to value_type
  • il, an object of type std::initializer_list<value_type>
  • n, a value of type X::size_type
  • t, an lvalue or const rvalue of type X::value_type
  • rv, a non-const rvalue of type X::value_type
  • Args, a template parameter pack
  • args, a function parameter pack with the pattern Arg&&

The following expressions must be valid and have their specified effects for all sequence containers except std::array:

ExpressionReturn typeEffectsPreconditionPostcondition
X(n, t)
X a(n, t)
Constructs the sequence container holding n copies of tT is CopyInsertable into Xstd::distance(begin(), end())
    == n
X(i, j)
X a(i, j)
Constructs the sequence container equal, element-wise, to the range [i, j)T is EmplaceConstructible from i into X (only for std::vector) If the iterators are not LegacyForwardIterators, T must be CopyInsertablestd::distance(begin(), end())
    == std::distance(i, j)
X(il)X(il.begin(), il.end())
a = ilX&Assigns the range represented by il into a[1]T is CopyInsertable and CopyAssignableExisting elements of a are destroyed or assigned to
a.emplace(p, args)iteratorInsert an object of type T, constructed with std::forward<Args>(args) before pT is EmplaceConstructible
(for std::vector and std::deque) T is MoveAssignable and MoveInsertable
Returned iterator points at the element constructed from args into a
a.insert(p, t)iteratorInserts a copy of t before pT is CopyInsertable
(for std::vector and std::deque) T is CopyAssignable or MoveAssignable
Returned iterator points at the copy of t inserted into a
a.insert(p, rv)iteratorInserts a copy of rv before p, possibly using move semanticsT is MoveInsertable
(for std::vector and std::deque) T is MoveAssignable
Returned iterator points at the copy of rv inserted into a
a.insert(p, n, t)iteratorInserts n copies of t before pT is CopyInsertable and CopyAssignableReturned iterator points at the copy of the first element inserted into a or is p for n == 0
a.insert(p, i, j)iteratorInserts copies of elements in [i, j) before pT is EmplaceConstructible and i and j are not in a
(only for std::vector) If the iterators are not LegacyForwardIterators, T must be MoveInsertable and MoveAssignable
Each iterator in [i, j) is dereferenced once. Returned iterator points at the copy of the first element inserted into a or is p for i == j
a.insert(p, il)iteratora.insert(p,
    il.begin(),
    il.end())
Returned iterator points at the copy of the first element inserted into a or is p if il is empty.
a.erase(q)iteratorErases the element pointed to by q(std::deque, std::vector)
T is MoveAssignable
Returned iterator points at the element that was immediately following q prior to erasure, or a.end() if no such element exists.
a.erase(q1, q2)iteratorErases elements in [q1, q2)(std::deque, std::vector)
T is MoveAssignable
Returned iterator points at the element that was pointed by q2 prior to any erasure, or a.end() if no such element exists.
a.clear()voidDestroys all elements in aAll references, pointers, and iterators are invalidated, including the end iterator. a.empty() == true.
a.assign(i, j)voidReplaces elements in a with a copy of [i, j)T is EmplaceConstructible and i, j not in a
(std::vector) If not LegacyForwardIterator. T is MoveInsertable
Each iterator in [i, j) is dereferenced once
a.assign(il)voida.assign(il.begin(),
    il.end())
a.assign(n, t)voidReplaces elements in a with n copies of tT is CopyInsertable and CopyAssignable

Notes

1 std::array supports assignment from a braced-init-list, but not from an std::initializer_list

Optional operations

The following expressions must be valid and have their specified effects for the sequence containers named, all operations take amortized constant time:

ExpressionReturn typeEffectsPreconditionsContainers
a.front()reference
const_reference for const a
Equivalent to *a.begin()(all)
a.back()reference
const_reference for const a
Equivalent to
{
auto tmp = a.end();
--tmp;
return *tmp;
}
std::basic_string
std::array
std::deque
std::list
std::vector
a.emplace_front(args)voidPrepends a T constructed with std::forward<Args>(args)...T is EmplaceConstructible into X from argsstd::deque
std::forward_list
std::list
a.emplace_back(args)voidAppends a T constructed with std::forward<Args>(args)...T is EmplaceConstructible into X from args (std::vector only) T is MoveInsertable into Xstd::deque
std::list
std::vector
a.push_front(t)voidPrepends a copy of tT is CopyInsertable into Xstd::deque
std::forward_list
std::list
a.push_front(rv)voidPrepends a copy of rv, possibly using move semanticsT is MoveInsertable into Xstd::deque
std::forward_list
std::list
a.push_back(t)voidAppends a copy of tT is CopyInsertable into Xstd::basic_string
std::deque
std::list
std::vector
a.push_back(rv)voidAppends a copy of rv, possibly using move semanticsT is MoveInsertable into Xstd::basic_string
std::deque
std::list
std::vector
a.pop_front()voidDestroys the first element.a.empty() == falsestd::deque
std::forward_list
std::list
a.pop_back()voidDestroys the last elementa.empty() == falsestd::basic_string
std::deque
std::list
std::vector
a[n]reference
const_reference for const a
Equivalent to *(n + a.begin())std::basic_string
std::array
std::deque
std::vector
a.at(n)reference
const_reference for const a
Equivalent to *(n + a.begin()), except that std::out_of_range is thrown if n >= size()std::basic_string
std::array
std::deque
std::vector

Additionally, for every sequence container, the 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.

Sequence containers in the standard library

pubbasic_stringstores and manipulates sequences of characters
pubarray(C++11)static contiguous array
pubvectordynamic contiguous array
pubdequedouble-ended queue
pubforward_list(C++11)singly-linked list
publistdoubly-linked list

Trade-offs / usage notes

pubstd::vectorFast access but mostly inefficient insertions/deletions
pubstd::arrayFast access but fixed number of elements
pubstd::list
std::forward_list
Efficient insertion/deletion in the middle of the sequence
pubstd::dequeEfficient insertion/deletion at the beginning and at the end of the sequence

Defect reports

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

DRApplied toBehavior as publishedCorrect behavior
LWG 139C++98the optional operations were not required to be implemented for the designated containersrequired with amortized time
LWG 149C++98a.insert(p, t) returned iterator while a.insert(p, n, t) and a.insert(p, n, t) returned voidthey all return iterator
LWG 151C++98q1 was dereferenceable[1]it can be non-dereferenceable
LWG 355C++98calling a.back() or a.pop_back() would execute --a.end(), which is dangerous[2]decrements a copy of a.end() instead
LWG 589C++98the elements that i and j refer to might not be convertible to value_typethey are implicitly convertible to value_type

1 It is a defect because it makes the behavior of a.erase(a.begin(), a.end()) undefined is a is an empty container.
2 If the type of a.end() is a fundamental type, --a.end() is ill-formed. It is dangerous when the type of a is templated, in this case this bug can be difficult to be found.

C++ named requirements: SequenceContainer

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

Requirements

The type X satisfies SequenceContainer if

Given

  • T, the element type of X
  • A, the allocator type of X: X::allocator_type if it exists, otherwise std::allocator<T>
  • a, an rvalue expression of type X
  • p, a valid const iterator into a
  • q, a valid dereferenceable const iterator into a
  • q1 and q2, two const iterators into a such that [q1, q2) is a valid range
  • i and j, LegacyInputIterators such that [i, j) is a valid range and that the iterators refer to elements implicitly convertible to value_type
  • il, an object of type std::initializer_list<value_type>
  • n, a value of type X::size_type
  • t, an lvalue or const rvalue of type X::value_type
  • rv, a non-const rvalue of type X::value_type
  • Args, a template parameter pack
  • args, a function parameter pack with the pattern Arg&&

The following expressions must be valid and have their specified effects for all sequence containers except std::array:

ExpressionReturn typeEffectsPreconditionPostcondition
X(n, t)
X a(n, t)
Constructs the sequence container holding n copies of tT is CopyInsertable into Xstd::distance(begin(), end())
    == n
X(i, j)
X a(i, j)
Constructs the sequence container equal, element-wise, to the range [i, j)T is EmplaceConstructible from i into X (only for std::vector) If the iterators are not LegacyForwardIterators, T must be CopyInsertablestd::distance(begin(), end())
    == std::distance(i, j)
X(il)X(il.begin(), il.end())
a = ilX&Assigns the range represented by il into a[1]T is CopyInsertable and CopyAssignableExisting elements of a are destroyed or assigned to
a.emplace(p, args)iteratorInsert an object of type T, constructed with std::forward<Args>(args) before pT is EmplaceConstructible
(for std::vector and std::deque) T is MoveAssignable and MoveInsertable
Returned iterator points at the element constructed from args into a
a.insert(p, t)iteratorInserts a copy of t before pT is CopyInsertable
(for std::vector and std::deque) T is CopyAssignable or MoveAssignable
Returned iterator points at the copy of t inserted into a
a.insert(p, rv)iteratorInserts a copy of rv before p, possibly using move semanticsT is MoveInsertable
(for std::vector and std::deque) T is MoveAssignable
Returned iterator points at the copy of rv inserted into a
a.insert(p, n, t)iteratorInserts n copies of t before pT is CopyInsertable and CopyAssignableReturned iterator points at the copy of the first element inserted into a or is p for n == 0
a.insert(p, i, j)iteratorInserts copies of elements in [i, j) before pT is EmplaceConstructible and i and j are not in a
(only for std::vector) If the iterators are not LegacyForwardIterators, T must be MoveInsertable and MoveAssignable
Each iterator in [i, j) is dereferenced once. Returned iterator points at the copy of the first element inserted into a or is p for i == j
a.insert(p, il)iteratora.insert(p,
    il.begin(),
    il.end())
Returned iterator points at the copy of the first element inserted into a or is p if il is empty.
a.erase(q)iteratorErases the element pointed to by q(std::deque, std::vector)
T is MoveAssignable
Returned iterator points at the element that was immediately following q prior to erasure, or a.end() if no such element exists.
a.erase(q1, q2)iteratorErases elements in [q1, q2)(std::deque, std::vector)
T is MoveAssignable
Returned iterator points at the element that was pointed by q2 prior to any erasure, or a.end() if no such element exists.
a.clear()voidDestroys all elements in aAll references, pointers, and iterators are invalidated, including the end iterator. a.empty() == true.
a.assign(i, j)voidReplaces elements in a with a copy of [i, j)T is EmplaceConstructible and i, j not in a
(std::vector) If not LegacyForwardIterator. T is MoveInsertable
Each iterator in [i, j) is dereferenced once
a.assign(il)voida.assign(il.begin(),
    il.end())
a.assign(n, t)voidReplaces elements in a with n copies of tT is CopyInsertable and CopyAssignable

Notes

1 std::array supports assignment from a braced-init-list, but not from an std::initializer_list

Optional operations

The following expressions must be valid and have their specified effects for the sequence containers named, all operations take amortized constant time:

ExpressionReturn typeEffectsPreconditionsContainers
a.front()reference
const_reference for const a
Equivalent to *a.begin()(all)
a.back()reference
const_reference for const a
Equivalent to
{
auto tmp = a.end();
--tmp;
return *tmp;
}
std::basic_string
std::array
std::deque
std::list
std::vector
a.emplace_front(args)voidPrepends a T constructed with std::forward<Args>(args)...T is EmplaceConstructible into X from argsstd::deque
std::forward_list
std::list
a.emplace_back(args)voidAppends a T constructed with std::forward<Args>(args)...T is EmplaceConstructible into X from args (std::vector only) T is MoveInsertable into Xstd::deque
std::list
std::vector
a.push_front(t)voidPrepends a copy of tT is CopyInsertable into Xstd::deque
std::forward_list
std::list
a.push_front(rv)voidPrepends a copy of rv, possibly using move semanticsT is MoveInsertable into Xstd::deque
std::forward_list
std::list
a.push_back(t)voidAppends a copy of tT is CopyInsertable into Xstd::basic_string
std::deque
std::list
std::vector
a.push_back(rv)voidAppends a copy of rv, possibly using move semanticsT is MoveInsertable into Xstd::basic_string
std::deque
std::list
std::vector
a.pop_front()voidDestroys the first element.a.empty() == falsestd::deque
std::forward_list
std::list
a.pop_back()voidDestroys the last elementa.empty() == falsestd::basic_string
std::deque
std::list
std::vector
a[n]reference
const_reference for const a
Equivalent to *(n + a.begin())std::basic_string
std::array
std::deque
std::vector
a.at(n)reference
const_reference for const a
Equivalent to *(n + a.begin()), except that std::out_of_range is thrown if n >= size()std::basic_string
std::array
std::deque
std::vector

Additionally, for every sequence container, the 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.

Sequence containers in the standard library

pubbasic_stringstores and manipulates sequences of characters
pubarray(C++11)static contiguous array
pubvectordynamic contiguous array
pubdequedouble-ended queue
pubforward_list(C++11)singly-linked list
publistdoubly-linked list

Trade-offs / usage notes

pubstd::vectorFast access but mostly inefficient insertions/deletions
pubstd::arrayFast access but fixed number of elements
pubstd::list
std::forward_list
Efficient insertion/deletion in the middle of the sequence
pubstd::dequeEfficient insertion/deletion at the beginning and at the end of the sequence

Defect reports

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

DRApplied toBehavior as publishedCorrect behavior
LWG 139C++98the optional operations were not required to be implemented for the designated containersrequired with amortized time
LWG 149C++98a.insert(p, t) returned iterator while a.insert(p, n, t) and a.insert(p, n, t) returned voidthey all return iterator
LWG 151C++98q1 was dereferenceable[1]it can be non-dereferenceable
LWG 355C++98calling a.back() or a.pop_back() would execute --a.end(), which is dangerous[2]decrements a copy of a.end() instead
LWG 589C++98the elements that i and j refer to might not be convertible to value_typethey are implicitly convertible to value_type

1 It is a defect because it makes the behavior of a.erase(a.begin(), a.end()) undefined is a is an empty container.
2 If the type of a.end() is a fundamental type, --a.end() is ill-formed. It is dangerous when the type of a is templated, in this case this bug can be difficult to be found.