Namespaces
Variants
Views
Actions

Difference between revisions of "cpp/named req/SequenceContainer"

From cppreference.com
< cpp‎ | named req
m (→‎Legend: Sync with N4950 ⊃ P1206R7, except §24.2.4-68, p. 883... (should the later be here?))
(Added LWG issue #2194 DR.)
 
(8 intermediate revisions by 2 users not shown)
Line 5: Line 5:
  
 
===Requirements===
 
===Requirements===
−
 
 
{{dsc begin}}
 
{{dsc begin}}
 
{{dsc h2|Legend}}
 
{{dsc h2|Legend}}
 
{{dsc|{{tt|X}}|A sequence container class}}
 
{{dsc|{{tt|X}}|A sequence container class}}
 
{{dsc|{{tt|T}}|The element type of {{tt|X}}}}
 
{{dsc|{{tt|T}}|The element type of {{tt|X}}}}
−
{{dsc|{{c|a}}|An [[cpp/language/value category|rvalue]] expression of type {{tt|X}}}}
+
{{dsc|{{c|a}}|A value of type {{tt|X}}}}
 
{{dsc|{{c|u}}|The name of a declared variable}}
 
{{dsc|{{c|u}}|The name of a declared variable}}
−
{{dsc|{{tt|A}}|The allocator type of {{tt|X}}: {{tt|X::allocator_type}} if it exists, otherwise {{c/core|std::allocator<T>}}}}
+
{{dsc|{{tt|A}}|The allocator type of {{tt|X}}:
−
{{dsc|{{range|i|j}}|{{named req|InputIterator}}s such that {{range|i|j}} is a valid range and that the iterators refer to elements implicitly convertible to {{tt|value_type}}}}
+
* {{tt|X::allocator_type}} if it exists,
−
{{dsc|{{c|rg}}<br>{{mark since c++23}}|A value of a type {{tt|R}} that models {{box|{{lti|cpp/ranges/to#container compatible range|container-compatible-range}}{{tt|<T>}}}}}}
+
* otherwise {{c/core|std::allocator<T>}}}}
−
{{dsc|{{c|il}}|An object of type {{c/core|std::initializer_list<value_type>}}}}
+
{{dsc|{{c|i}}, {{c|j}}|{{named req|InputIterator}}s such that {{range|i|j}} is a [[cpp/iterator#Ranges|valid range]] and that the iterators refer to elements implicitly convertible to {{tt|value_type}}}}
 +
{{dsc|{{c|rg}} {{mark since c++23}}|A value of a type {{tt|R}} that models {{lti|cpp/ranges/to#container compatible range|container-compatible-range}}{{tt|<T>}}}}
 +
{{dsc|{{c|il}} {{mark since c++11}}|An object of type {{c/core|std::initializer_list<value_type>}}}}
 
{{dsc|{{c|n}}|A value of type {{tt|X::size_type}}}}
 
{{dsc|{{c|n}}|A value of type {{tt|X::size_type}}}}
−
{{dsc|{{c|p}}|A valid const iterator into {{c|a}}}}
+
{{dsc|{{c|p}}|A valid [[cpp/iterator|const iterator]] into {{c|a}}}}
−
{{dsc|{{c|q}}|A valid dereferenceable const iterator into {{c|a}}}}
+
{{dsc|{{c|q}}|A [[cpp/iterator#Dereferenceability and validity|valid dereferenceable]] const iterator into {{c|a}}}}
−
{{dsc|{{range|q1|q2}}|Two const iterators into {{c|a}} such that {{range|q1|q2}} is a valid range}}
+
{{dsc|{{c|q1}}, {{c|q2}}|Two const iterators into {{c|a}} such that {{range|q1|q2}} is a valid range}}
−
{{dsc|{{c|t}}|An [[cpp/language/value category|lvalue]] or const rvalue of type {{tt|X::value_type}}}}
+
{{dsc|{{c|t}}|An [[cpp/language/value category|lvalue]]{{rev inl|since=c++11| or const rvalue}} of type {{tt|X::value_type}}}}
−
{{dsc|{{c|rv}}|A non-const rvalue of type {{tt|X::value_type}}}}
+
{{dsc|{{c|rv}} {{mark since c++11}}|A non-const rvalue of type {{tt|X::value_type}}}}
−
{{dsc|{{tt|Args}}|A template parameter pack}}
+
{{dsc|{{tt|Args}} {{mark since c++11}}|A template parameter pack}}
−
{{dsc|{{c|args}}|A function parameter pack with the pattern {{tt|Arg&&}}}}
+
{{dsc|{{c|args}} {{mark since c++11}}|A function parameter pack with the pattern {{tt|Arg&&}}}}
 
{{dsc end}}
 
{{dsc end}}
  
 
The type {{tt|X}} satisfies {{named req/core|SequenceContainer}} if
 
The type {{tt|X}} satisfies {{named req/core|SequenceContainer}} if
 
* The type {{tt|X}} satisfies {{named req|Container}}, and
 
* The type {{tt|X}} satisfies {{named req|Container}}, and
−
* The following expressions must be valid and have their specified effects for all sequence containers except {{lc|std::array}} (see [[#NotesT1|notes]]):
+
* The following statements and expressions must be valid and have their specified effects for all sequence containers{{rev inl|since=c++11| except {{lc|std::array}} (see [[#NotesT1|notes]])}}:
  
 
{|class=wikitable
 
{|class=wikitable
−
!Expression||Return type||Effects||Precondition||Postcondition
+
!colspan=2|Statement
 +
!Effects
 +
!colspan=2|{{nbsp|4}}Conditions<ref>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.</ref>
 
|-
 
|-
−
|{{c|X u(n, t)}}
+
|rowspan=2 colspan=2|{{c|X u(n, t)}}
−
|
+
|rowspan=2|Constructs the sequence container holding {{c|n}} copies of {{c|t}}
−
|Constructs the sequence container holding {{c|n}} copies of {{c|t}}
+
|Pre
 
|{{tt|T}} is {{named req|CopyInsertable}} into {{tt|X}}
 
|{{tt|T}} is {{named req|CopyInsertable}} into {{tt|X}}
−
|{{c|1=std::distance(u.begin(), u.end())
 
−
    == n}}
 
 
|-
 
|-
−
|{{c|X u(i, j)}}
+
|Post{{nbsp}}
−
|
+
|{{c multi|std::distance(u.begin(), u.end())
−
|Constructs the sequence container equal, element-wise, to the range {{range|i|j}}
+
|    {{==}} n}}
 +
|-
 +
|rowspan=2 colspan=2|{{c|X u(i, j)}}
 +
|rowspan=2|Constructs the sequence container equal, element-wise, to the range {{range|i|j}}
 +
|Pre
 
|{{tt|T}} is {{named req|EmplaceConstructible}} from {{c|*i}} into {{tt|X}}
 
|{{tt|T}} is {{named req|EmplaceConstructible}} from {{c|*i}} into {{tt|X}}
−
{{mark|std::vector}} If the iterators are not {{named req|ForwardIterator}}s, {{tt|T}} must be {{named req|CopyInsertable}}
 
−
|{{c|1=std::distance(u.begin(), u.end())
 
−
    == std::distance(i, j)}}
 
 
|-
 
|-
−
|{{c|X(std::from_range, rg)}}<br>{{mark since c++23}}
+
|Post
−
|
+
|{{c multi|std::distance(u.begin(), u.end())
−
|Constructs the sequence container equal, element-wise, to the range {{c|rg}}
+
|   {{==}} std::distance(i, j)
−
|{{tt|T}} is {{named req|EmplaceConstructible}} from {{c|*ranges::begin(rg)}} into {{tt|X}}.
+
}}
−
{{mark|std::vector}} If {{tt|R}} models neither {{c|ranges::sized_range}} nor {{c|ranges::forward_range}}, {{tt|T}} must be {{named req|MoveInsertable}} into {{tt|X}}.
+
−
|Each iterator in the range {{c|rg}} is dereferenced once.
+
−
{{c|1=std::distance(begin(), end())
+
−
    == ranges::distance(rg)}}
+
 
|-
 
|-
−
|{{c|X(il)}}
+
!Expression
−
|
+
!Type
−
|{{c|X(il.begin(), il.end())}}
+
!Effects
−
|
+
!colspan=2|Conditions
 +
|-
 +
|rowspan=2|{{c|X(std::from_range, rg)}}<br>{{mark since c++23}}
 +
|rowspan=2|{{tt|X}}
 +
|rowspan=2|Constructs the sequence container equal, element-wise, to the range {{c|rg}}
 +
|Pre
 +
|{{tt|T}} is {{named req|EmplaceConstructible}} into {{tt|X}} from {{c|*ranges::begin(rg)}}
 +
|-
 +
|Post
 
|
 
|
 +
* Each iterator in the range {{c|rg}} is dereferenced once.
 +
* {{c multi|std::distance(begin(), end())
 +
|    {{==}} ranges::distance(rg)}}
 
|-
 
|-
−
|{{c|1=a = il}}
+
|{{c|X(il)}}<br>{{mark since c++11}}
−
|{{tt|X&}}
+
|{{tt|X}}
−
|Assigns the range represented by {{c|il}} into {{c|a}}<ref>{{lc|std::array}} supports assignment from a braced-init-list, but not from an {{lc|std::initializer_list}}.</ref>
+
|Equivalent to {{c multi|X(il.begin(),
 +
|    il.end())}}
 +
|colspan=2 {{n/a|No explicit requirement}}
 +
|-
 +
|rowspan=2|{{c|1=a = il}}<br>{{mark since c++11}}
 +
|rowspan=2|{{tt|X&}}
 +
|rowspan=2|Assigns the range represented by {{c|il}} into {{c|a}}.<ref>{{lc|std::array}} supports assignment from a braced-init-list, but not from an {{lc|std::initializer_list}}.</ref>
 +
|Pre
 
|{{tt|T}} is {{named req|CopyInsertable}} and {{named req|CopyAssignable}}
 
|{{tt|T}} is {{named req|CopyInsertable}} and {{named req|CopyAssignable}}
 +
|-
 +
|Post
 
|Existing elements of {{c|a}} are destroyed or assigned to
 
|Existing elements of {{c|a}} are destroyed or assigned to
 
|-
 
|-
−
|{{c|a.emplace(p, args)}}
+
|rowspan=2|{{c|a.emplace(p, args)}}<br>{{mark since c++11}}
−
|{{tt|iterator}}
+
|rowspan=2|{{tt|iterator}}
−
|Insert an object of type {{tt|T}}, constructed with {{c|std::forward<Args>(args)}} before {{c|p}}
+
|rowspan=2|Insert an object of type {{tt|T}}, constructed with {{c|std::forward<Args>(args)}} before {{c|p}}
 +
|Pre
 
|{{tt|T}} is {{named req|EmplaceConstructible}}
 
|{{tt|T}} is {{named req|EmplaceConstructible}}
−
{{mark|std::vector, std::deque}} {{tt|T}} is {{named req|MoveAssignable}} and {{named req|MoveInsertable}}
 
−
|Returned iterator points at the element constructed from {{c|args}} into {{c|a}}
 
 
|-
 
|-
−
|{{c|a.insert(p, t)}}
+
|Post
−
|{{tt|iterator}}
+
|The returned iterator points at the element constructed from {{c|args}} into {{c|a}}
−
|Inserts a copy of {{c|t}} before {{c|p}}
+
|-
 +
|rowspan=2|{{c|a.insert(p, t)}}
 +
|rowspan=2|{{tt|iterator}}
 +
|rowspan=2|Inserts a copy of {{c|t}} before {{c|p}}
 +
|Pre
 
|{{tt|T}} is {{named req|CopyInsertable}}
 
|{{tt|T}} is {{named req|CopyInsertable}}
−
{{mark|std::vector, std::deque}} {{tt|T}} is {{named req|CopyAssignable}} or {{named req|MoveAssignable}}
 
−
|Returned iterator points at the copy of {{c|t}} inserted into {{c|a}}
 
 
|-
 
|-
−
|{{c|a.insert(p, rv)}}
+
|Post
−
|{{tt|iterator}}
+
|The returned iterator points at the copy of {{c|t}} inserted into {{c|a}}
−
|Inserts a copy of {{c|rv}} before<br>{{c|p}}, possibly using move semantics
+
|-
 +
|rowspan=2|{{c|a.insert(p, rv)}}<br>{{mark since c++11}}
 +
|rowspan=2|{{tt|iterator}}
 +
|rowspan=2|Inserts a copy of {{c|rv}} before {{c|p}}, possibly using move semantics
 +
|Pre
 
|{{tt|T}} is {{named req|MoveInsertable}}
 
|{{tt|T}} is {{named req|MoveInsertable}}
−
{{mark|std::vector, std::deque}} {{tt|T}} is {{named req|MoveAssignable}}
 
−
|Returned iterator points at the copy of {{c|rv}} inserted into {{c|a}}
 
 
|-
 
|-
−
|{{c|a.insert(p, n, t)}}
+
|Post
−
|{{tt|iterator}}
+
|The returned iterator points at the copy of {{c|rv}} inserted into {{c|a}}
−
|Inserts {{c|n}} copies of {{c|t}} before {{c|p}}
+
|-
 +
|rowspan=2|{{c|a.insert(p, n, t)}}
 +
|rowspan=2|{{tt|iterator}}
 +
|rowspan=2|Inserts {{c|n}} copies of {{c|t}} before {{c|p}}
 +
|Pre
 
|{{tt|T}} is {{named req|CopyInsertable}} and {{named req|CopyAssignable}}
 
|{{tt|T}} is {{named req|CopyInsertable}} and {{named req|CopyAssignable}}
−
|Returned iterator points at the copy of the first element inserted into {{c|a}} or is {{c|p}} for {{c|1=n == 0}}
 
 
|-
 
|-
−
|{{c|a.insert(p, i, j)}}
+
|Post
−
|{{tt|iterator}}
+
|The returned iterator points at the copy of the first element inserted into {{c|a}} or is {{c|p}} for {{c|1=n == 0}}
−
|Inserts copies of elements in<br>{{range|i|j}} before {{c|p}}
+
|-
 +
|rowspan=2|{{c|a.insert(p, i, j)}}
 +
|rowspan=2|{{tt|iterator}}
 +
|rowspan=2|Inserts copies of elements in<br>{{range|i|j}} before {{c|p}}
 +
|Pre
 
|{{tt|T}} is {{named req|EmplaceConstructible}} and {{c|i}} and {{c|j}} are not in {{c|a}}
 
|{{tt|T}} is {{named req|EmplaceConstructible}} and {{c|i}} and {{c|j}} are not in {{c|a}}
−
{{mark|std::vector}} If the iterators are not {{named req|ForwardIterator}}s, {{tt|T}} must be {{named req|MoveInsertable}} and {{named req|MoveAssignable}}
 
−
|Each iterator in {{range|i|j}} is dereferenced once. Returned iterator points at the copy of the first element inserted into {{c|a}} or is {{c|p}} for {{c|1=i == j}}
 
 
|-
 
|-
−
|{{c|a.insert_range(p, rg)}}<br>{{mark since c++23}}
+
|Post
−
|{{tt|iterator}}
+
|
−
|Inserts copies of elements in {{c|rg}} before {{c|p}}
+
* Each iterator in {{range|i|j}} is dereferenced once.
−
|{{tt|T}} is {{named req|EmplaceConstructible}} into {{tt|X}} from {{c|*ranges::begin(rg)}}.
+
* The returned iterator points at the copy of the first element inserted into {{c|a}} or is {{c|p}} for {{c|1=i == j}}
−
{{mark|std::vector, std::deque}} {{tt|T}} is also {{named req|MoveInsertable}} into {{tt|X}}, and {{tt|T}} is {{named req|MoveConstructible}}, {{named req|MoveAssignable}}, and {{named req|Swappable}}.
+
−
{{c|rg}} and {{c|a}} do not overlap.
+
−
|Each iterator in the range {{c|rg}} is dereferenced once. Returned iterator points at the copy of the first element inserted into {{c|a}} or at {{c|p}} if {{c|rg}} is empty
+
 
|-
 
|-
−
|{{c|a.insert(p, il)}}
+
|rowspan=2|{{c|a.insert_range(p, rg)}}<br>{{mark since c++23}}
−
|{{tt|iterator}}
+
|rowspan=2|{{tt|iterator}}
−
|{{c|a.insert(p,
+
|rowspan=2|Inserts copies of elements in {{c|rg}} before {{c|p}}
−
        il.begin(),
+
|Pre
−
        il.end())}}
+
 
|
 
|
−
|Returned iterator points at the copy of the first element inserted into {{c|a}} or is {{c|p}} if {{c|il}} is empty.
+
* {{tt|T}} is {{named req|EmplaceConstructible}} into {{tt|X}} from {{c|*ranges::begin(rg)}}
 +
* {{c|rg}} and {{c|a}} do not overlap
 
|-
 
|-
−
|{{c|a.erase(q)}}
+
|Post
−
|{{tt|iterator}}
+
|
−
|Erases the element pointed to by {{c|q}}
+
* Each iterator in the range {{c|rg}} is dereferenced once
−
|{{mark|std::vector, std::deque}} {{tt|T}} is {{named req|MoveAssignable}}
+
* The returned iterator points at the copy of the first element inserted into {{c|a}} or at {{c|p}} if {{c|rg}} is empty
−
|Returned iterator points at the element that was immediately following {{c|q}} prior to erasure, or {{c|a.end()}} if no such element exists.
+
 
|-
 
|-
−
|{{c|a.erase(q1, q2)}}
+
|rowspan=2|{{c|a.insert(p, il)}}<br>{{mark since c++11}}
−
|{{tt|iterator}}
+
|rowspan=2|{{tt|iterator}}
−
|Erases elements in<br>{{range|q1|q2}}
+
|rowspan=2|Equivalent to {{c multi
−
|{{mark|std::vector, std::deque}} {{tt|T}} is {{named req|MoveAssignable}}
+
|a.insert(p,
−
|Returned iterator points at the element that was pointed by {{c|q2}} prior to any erasure, or {{c|a.end()}} if no such element exists.
+
|        il.begin(),
 +
|        il.end())
 +
}}
 +
|Pre
 +
|{{n/a|No explicit requirement}}
 
|-
 
|-
−
|{{c|a.clear()}}
+
|Post
−
|{{c/core|void}}
+
|The returned iterator points at the copy of the first element inserted into {{c|a}} or is {{c|p}} if {{c|il}} is empty
−
|Destroys all elements in {{c|a}}
+
|-
 +
|rowspan=2|{{c|a.erase(q)}}
 +
|rowspan=2|{{tt|iterator}}
 +
|rowspan=2|Erases the element pointed to by {{c|q}}
 +
|Pre
 +
|{{n/a|No explicit requirement}}
 +
|-
 +
|Post
 +
|The returned iterator points at the element that was immediately following {{c|q}} prior to erasure, or {{c|a.end()}} if no such element exists
 +
|-
 +
|rowspan=2|{{c|a.erase(q1, q2)}}
 +
|rowspan=2|{{tt|iterator}}
 +
|rowspan=2|Erases elements in {{range|q1|q2}}
 +
|Pre
 +
|{{n/a|No explicit requirement}}
 +
|-
 +
|Post
 +
|The returned iterator points at the element that was pointed by {{c|q2}} prior to any erasure, or {{c|a.end()}} if no such element exists
 +
|-
 +
|rowspan=2|{{c|a.clear()}}
 +
|rowspan=2|{{c/core|void}}
 +
|rowspan=2|Destroys all elements in {{c|a}}
 +
|Pre
 +
|{{n/a|No explicit requirement}}
 +
|-
 +
|Post
 
|
 
|
−
|All references, pointers, and iterators are invalidated, including the end iterator. {{c|1=a.empty() == true}}
+
* All references, pointers, and iterators are invalidated, including the end iterator
 +
* {{c|a.empty()}} is {{c|true}}
 
|-
 
|-
−
|{{c|a.assign(i, j)}}
+
|rowspan=2|{{c|a.assign(i, j)}}
−
|{{c/core|void}}
+
|rowspan=2|{{c/core|void}}
−
|Replaces elements in {{c|a}} with a copy of {{range|i|j}}
+
|rowspan=2|Replaces elements in {{c|a}} with a copy of {{range|i|j}}
−
|{{tt|T}} is {{named req|EmplaceConstructible}} and {{c|i}}, {{c|j}} are not in {{c|a}}.
+
|Pre
−
{{mark|std::vector}} If the iterators are not {{named req|ForwardIterator}}s, {{tt|T}} must be {{named req|MoveInsertable}}.
+
|
−
|Each iterator in {{range|i|j}} is dereferenced once
+
* {{tt|T}} is {{named req|EmplaceConstructible}}
 +
* {{c|i}} and {{c|j}} are not in {{c|a}}
 
|-
 
|-
−
|{{c|a.assign_range(rg)}}<br>{{mark since c++23}}
+
|Post
−
|{{c/core|void}}
+
|Each iterator in {{range|i|j}} is dereferenced once.
−
|Replaces elements in {{c|a}} with a copy of each element in {{c|rg}}
+
−
|{{tt|T}}<ref>{{tt|T}} and {{tt|R}} are such that {{c|ranges::assignable_from<T&, ranges::range_reference_t<R>>}} is modeled.</ref> is {{named req|EmplaceConstructible}} into {{tt|X}} from {{c|*ranges::begin(rg)}}. {{c|rg}} and {{c|a}} do not overlap.
+
−
{{mark|std::vector}} If {{tt|R}} models neither {{c|ranges::sized_range}} nor {{c|ranges::forward_range}}, {{tt|T}} is also {{named req|MoveInsertable}} into {{tt|X}}.
+
−
|Each iterator in the range {{c|rg}} is dereferenced once. All references, pointers, and iterators are invalidated.
+
−
{{mark|std::vector, std::deque}} Also invalidates the end iterator.
+
 
|-
 
|-
−
|{{c|a.assign(il)}}
+
|rowspan=2|{{c|a.assign_range(rg)}}<br>{{mark since c++23}}
−
|{{c/core|void}}
+
|rowspan=2|{{c/core|void}}
−
|{{c|a.assign(il.begin(),
+
|rowspan=2|Replaces elements in {{c|a}} with a copy of each element in {{c|rg}}
−
        il.end())}}
+
|Pre
 
|
 
|
 +
* {{tt|T}}<ref>{{tt|T}} and {{tt|R}} are types such that {{c/core|std::assignable_from<T&, ranges::range_reference_t<R>>}} is modeled.</ref> is {{named req|EmplaceConstructible}} into {{tt|X}} from {{c|*ranges::begin(rg)}}
 +
* {{c|rg}} and {{c|a}} do not overlap.
 +
|-
 +
|Post
 
|
 
|
 +
* Each iterator in the range {{c|rg}} is dereferenced once.
 +
* All references, pointers, and iterators are invalidated.
 
|-
 
|-
−
|{{c|a.assign(n, t)}}
+
|{{c|a.assign(il)}}<br>{{mark since c++11}}
 
|{{c/core|void}}
 
|{{c/core|void}}
−
|Replaces elements in {{c|a}} with {{c|n}} copies of {{c|t}}
+
|Equivalent to<br>
 +
{{c multi
 +
|a.assign(il.begin(),
 +
|        il.end())}}
 +
|colspan=2 {{n/a|No explicit requirement}}
 +
|-
 +
|rowspan=2|{{c|a.assign(n, t)}}
 +
|rowspan=2|{{c/core|void}}
 +
|rowspan=2|Replaces elements in {{c|a}} with {{c|n}} copies of {{c|t}}
 +
|Pre
 
|{{tt|T}} is {{named req|CopyInsertable}} and {{named req|CopyAssignable}}
 
|{{tt|T}} is {{named req|CopyInsertable}} and {{named req|CopyAssignable}}
−
|
+
|-
 +
|Post
 +
|{{n/a|No explicit requirement}}
 
|-
 
|-
 
!colspan=5|Notes {{anchor|NotesT1}}
 
!colspan=5|Notes {{anchor|NotesT1}}
Line 174: Line 239:
  
 
{|class=wikitable
 
{|class=wikitable
−
!Expression||Return type||Effects||Preconditions||Containers
+
!Expression||Type||Effects||{{nbsp|4}}Preconditions<ref>For an expression whose effect is equivalent to some other operations, the preconditions of the expressions inside those operations are inherited on top of the preconditions listed in the table.</ref>||Containers
 
|-
 
|-
 
|{{c|a.front()}}
 
|{{c|a.front()}}
−
|{{tt|reference}},
+
|{{tt|reference}}, or
−
{{tt|const_reference}} for {{c|const}} {{c|a}}
+
{{tt|const_reference}} for {{c/core|const}} {{c|a}}
−
|Equivalent to {{c|*a.begin()}}
+
|Returns {{c|*a.begin()}}
−
|
+
|{{n/a|No explicit requirement}}
−
|(all)
+
|{{lc|std::basic_string}}, {{lc|std::array}}, {{lc|std::deque}}, {{lc|std::forward_list}}, {{lc|std::inplace_vector}}, {{lc|std::list}}, {{lc|std::vector}}
 
|-
 
|-
 
|{{c|a.back()}}
 
|{{c|a.back()}}
−
|{{tt|reference}},
+
|{{tt|reference}}, or
−
{{tt|const_reference}} for {{c|const}} {{c|a}}
+
{{tt|const_reference}} for {{c/core|const}} {{c|a}}
−
|Equivalent to {{c|1=
+
|Equivalent to {{c multi|auto tmp {{=}} a.end();|--tmp;|return *tmp;}}
−
{ auto tmp = a.end();
+
|{{n/a|No explicit requirement}}
−
  --tmp;
+
|{{lc|std::basic_string}}, {{lc|std::array}}, {{lc|std::deque}}, {{lc|std::inplace_vector}}, {{lc|std::list}}, {{lc|std::vector}}
−
  return *tmp; }<!---->}}
+
−
|
+
−
|{{lc|std::basic_string}} {{lc|std::array}} {{lc|std::deque}} {{lc|std::list}} {{lc|std::vector}}
+
 
|-
 
|-
−
|{{c|a.emplace_front(args)}}
+
|{{c|a.emplace_front(args)}}<br>{{mark since c++11}}
 
|{{c/core|void}}
 
|{{c/core|void}}
−
|Prepends a {{tt|T}} constructed with {{c|std::forward<Args>(args)...}}
+
|Prepends a {{tt|T}} constructed with {{c multi
 +
|std::forward<Args>
 +
|    (args)...
 +
}}
 
|{{tt|T}} is {{named req|EmplaceConstructible}} into {{tt|X}} from {{c|args}}
 
|{{tt|T}} is {{named req|EmplaceConstructible}} into {{tt|X}} from {{c|args}}
−
|{{lc|std::deque}} {{lc|std::forward_list}} {{lc|std::list}}
+
|{{lc|std::deque}}, {{lc|std::forward_list}}, {{lc|std::list}}
 
|-
 
|-
−
|{{c|a.emplace_back(args)}}
+
|{{c|a.emplace_back(args)}}<br>{{mark since c++11}}
 
|{{c/core|void}}
 
|{{c/core|void}}
−
|Appends a {{tt|T}} constructed with {{c|std::forward<Args>(args)...}}
+
|Appends a {{tt|T}} constructed with {{c multi
 +
|std::forward<Args>
 +
|    (args)...
 +
}}
 
|{{tt|T}} is {{named req|EmplaceConstructible}} into {{tt|X}} from {{c|args}}
 
|{{tt|T}} is {{named req|EmplaceConstructible}} into {{tt|X}} from {{c|args}}
−
{{mark|std::vector}} {{tt|T}} is {{named req|MoveInsertable}} into {{tt|X}}
+
|{{lc|std::deque}}, {{lc|std::inplace_vector}}, {{lc|std::list}}, {{lc|std::vector}}
−
|{{lc|std::deque}} {{lc|std::list}} {{lc|std::vector}}
+
 
|-
 
|-
 
|{{c|a.push_front(t)}}
 
|{{c|a.push_front(t)}}
Line 210: Line 277:
 
|Prepends a copy of {{c|t}}
 
|Prepends a copy of {{c|t}}
 
|{{tt|T}} is {{named req|CopyInsertable}} into {{tt|X}}
 
|{{tt|T}} is {{named req|CopyInsertable}} into {{tt|X}}
−
|{{lc|std::deque}} {{lc|std::forward_list}} {{lc|std::list}}
+
|rowspan="2" style="text-align:left;"|{{lc|std::deque}}, {{lc|std::forward_list}}, {{lc|std::list}}
 
|-
 
|-
−
|{{c|a.push_front(rv)}}
+
|{{c|a.push_front(rv)}}<br>{{mark since c++11}}
 
|{{c/core|void}}
 
|{{c/core|void}}
 
|Prepends a copy of {{c|rv}}, possibly using move semantics
 
|Prepends a copy of {{c|rv}}, possibly using move semantics
 
|{{tt|T}} is {{named req|MoveInsertable}} into {{tt|X}}
 
|{{tt|T}} is {{named req|MoveInsertable}} into {{tt|X}}
−
|{{lc|std::deque}} {{lc|std::forward_list}} {{lc|std::list}}
 
 
|-
 
|-
 
|{{c|a.prepend_range(rg)}}<br>{{mark since c++23}}
 
|{{c|a.prepend_range(rg)}}<br>{{mark since c++23}}
 
|{{c/core|void}}
 
|{{c/core|void}}
−
|Inserts<ref name="range">Insertion order, relative to order of elements in {{c|rg}}, is non-reversing.</ref> copies of elements in {{c|rg}} before {{c|begin()}} dereferencing each iterator in {{c|rg}} once.
+
|Inserts<ref name="range">Insertion order, relative to order of elements in {{c|rg}}, is non-reversing.</ref> copies of elements in {{c|rg}} before {{c|begin()}}, each iterator in {{c|rg}} is dereferenced once
−
|{{tt|T}} is {{named req|EmplaceConstructible}} into {{tt|X}} from {{c|*ranges::begin(rg)}}<br>
+
|{{tt|T}} is {{named req|EmplaceConstructible}} into {{tt|X}} from {{c|*ranges::begin(rg)}}
−
{{mark|std::deque}} {{tt|T}} is also {{named req|MoveInsertable}} into {{tt|X}}, and {{tt|T}} is {{named req|MoveConstructible}}, {{named req|MoveAssignable}}, and {{named req|Swappable}}
+
|{{lc|std::deque}}, {{lc|std::forward_list}}, {{lc|std::list}}
−
|{{lc|std::deque}} {{lc|std::forward_list}} {{lc|std::list}}
+
 
|-
 
|-
 
|{{c|a.push_back(t)}}
 
|{{c|a.push_back(t)}}
Line 229: Line 294:
 
|Appends a copy of {{c|t}}
 
|Appends a copy of {{c|t}}
 
|{{tt|T}} is {{named req|CopyInsertable}} into {{tt|X}}
 
|{{tt|T}} is {{named req|CopyInsertable}} into {{tt|X}}
−
|{{lc|std::basic_string}} {{lc|std::deque}} {{lc|std::list}} {{lc|std::vector}}
+
|rowspan="2" style="text-align:left;"|{{lc|std::basic_string}}, {{lc|std::deque}}, {{lc|std::inplace_vector}}, {{lc|std::list}}, {{lc|std::vector}}
 
|-
 
|-
−
|{{c|a.push_back(rv)}}
+
|{{c|a.push_back(rv)}}<br>{{mark since c++11}}
 
|{{c/core|void}}
 
|{{c/core|void}}
 
|Appends a copy of {{c|rv}}, possibly using move semantics
 
|Appends a copy of {{c|rv}}, possibly using move semantics
 
|{{tt|T}} is {{named req|MoveInsertable}} into {{tt|X}}
 
|{{tt|T}} is {{named req|MoveInsertable}} into {{tt|X}}
−
|{{lc|std::basic_string}} {{lc|std::deque}} {{lc|std::list}} {{lc|std::vector}}
 
 
|-
 
|-
 
|{{c|a.append_range(rg)}}<br>{{mark since c++23}}
 
|{{c|a.append_range(rg)}}<br>{{mark since c++23}}
 
|{{c/core|void}}
 
|{{c/core|void}}
−
|Inserts<ref name="range"/> copies of elements in {{c|rg}} before {{c|end()}} dereferencing each iterator in {{c|rg}} once.
+
|Inserts<ref name="range"/> copies of elements in {{c|rg}} before {{c|end()}} dereferencing each iterator in {{c|rg}} once
−
|{{tt|T}} is {{named req|EmplaceConstructible}} into {{tt|X}} from {{c|*ranges::begin(rg)}}<br>
+
|{{tt|T}} is {{named req|EmplaceConstructible}} into {{tt|X}} from {{c|*ranges::begin(rg)}}
−
{{mark|std::vector}} {{tt|T}} is also {{named req|MoveInsertable}} into {{tt|X}}
+
|{{lc|std::deque}}, {{lc|std::inplace_vector}}, {{lc|std::list}}, {{lc|std::vector}}
−
|{{lc|std::deque}} {{lc|std::list}} {{lc|std::vector}}
+
 
|-
 
|-
 
|{{c|a.pop_front()}}
 
|{{c|a.pop_front()}}
 
|{{c/core|void}}
 
|{{c/core|void}}
−
|Destroys the first element.
+
|Destroys the first element
−
|{{c|1=a.empty()
+
|{{c|a.empty()}} is {{c|false}}
−
    == false}}
+
|{{lc|std::deque}}, {{lc|std::forward_list}}, {{lc|std::list}}
−
|{{lc|std::deque}} {{lc|std::forward_list}} {{lc|std::list}}
+
 
|-
 
|-
 
|{{c|a.pop_back()}}
 
|{{c|a.pop_back()}}
 
|{{c/core|void}}
 
|{{c/core|void}}
 
|Destroys the last element
 
|Destroys the last element
−
|{{c|1=a.empty()
+
|{{c|a.empty()}} is {{c|false}}
−
    == false}}
+
|{{lc|std::basic_string}}, {{lc|std::deque}}, {{lc|std::inplace_vector}}, {{lc|std::list}}, {{lc|std::vector}}
−
|{{lc|std::basic_string}} {{lc|std::deque}} {{lc|std::list}} {{lc|std::vector}}
+
 
|-
 
|-
 
|{{c|a[n]}}
 
|{{c|a[n]}}
−
|{{tt|reference}},
+
|{{tt|reference}}, or
−
{{tt|const_reference}} for {{c|const}} {{c|a}}
+
{{tt|const_reference}} for {{c/core|const}} {{c|a}}
−
|Equivalent to {{c|*(n + a.begin())}}
+
|Returns {{c|*(a.begin() + n)}}
−
|
+
|{{n/a|No explicit requirement}}
−
|{{lc|std::basic_string}} {{lc|std::array}} {{lc|std::deque}} {{lc|std::vector}}
+
|rowspan="2" style="text-align:left;"|{{lc|std::basic_string}}, {{lc|std::array}}, {{lc|std::deque}}, {{lc|std::inplace_vector}}, {{lc|std::vector}}
 
|-
 
|-
 
|{{c|a.at(n)}}
 
|{{c|a.at(n)}}
−
|{{tt|reference}},
+
|{{tt|reference}}, or
−
{{tt|const_reference}} for {{c|const}} {{c|a}}
+
{{tt|const_reference}} for {{c/core|const}} {{c|a}}
−
|Equivalent to {{c|*(n + a.begin())}}, except that {{lc|std::out_of_range}} is thrown if {{c|1=n >= size()}}
+
|Returns {{c|*(a.begin() + n)}}, throws {{lc|std::out_of_range}} if {{c|1=n >= size()}}
−
|
+
|{{n/a|No explicit requirement}}
−
|{{lc|std::basic_string}} {{lc|std::array}} {{lc|std::deque}} {{lc|std::vector}}
+
 
|-
 
|-
 
!colspan=5|Notes
 
!colspan=5|Notes
Line 277: Line 337:
 
|}
 
|}
  
−
Additionally, for every sequence container, the constructor template that takes two input iterators and the member function template overloads of {{tt|insert()}}, {{tt|append()}}, {{tt|assign()}}, {{tt|replace()}} that take two input iterators do not participate in overload resolution if the corresponding template argument does not satisfy {{named req|InputIterator}}.
+
Additionally, for every sequence container:
 +
* A constructor template that takes two input iterators and the member function template overloads of {{tt|insert}}, {{tt|append}}, {{tt|assign}}, {{tt|replace}} that take two input iterators do not participate in overload resolution if the corresponding template argument does not satisfy {{named req|InputIterator}}.
 +
{{rrev|since=c++17|
 +
* A deduction guide that has either a {{named req|InputIterator}} or an {{tt|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.
 +
}}
  
 
===Sequence containers in the standard library===
 
===Sequence containers in the standard library===
Line 284: Line 348:
 
{{dsc inc|cpp/container/dsc array}}
 
{{dsc inc|cpp/container/dsc array}}
 
{{dsc inc|cpp/container/dsc vector}}
 
{{dsc inc|cpp/container/dsc vector}}
 +
{{dsc inc|cpp/container/dsc inplace_vector}}
 
{{dsc inc|cpp/container/dsc deque}}
 
{{dsc inc|cpp/container/dsc deque}}
 
{{dsc inc|cpp/container/dsc forward_list}}
 
{{dsc inc|cpp/container/dsc forward_list}}
Line 291: Line 356:
 
====Trade-offs / usage notes====
 
====Trade-offs / usage notes====
 
{{dsc begin}}
 
{{dsc begin}}
−
{{dsc|{{lc|std::vector}}|Fast access but mostly inefficient insertions/deletions}}
+
{{dsc|{{lc|std::vector}}|Fast access, but mostly inefficient insertions/deletions.}}
−
{{dsc|{{lc|std::array}}|Fast access but fixed number of elements}}
+
{{dsc|{{lc|std::inplace_vector}}|Fast access, inplace contiguous storage, but fixed capacity and mostly inefficient insertions/deletions.}}
−
{{dsc|{{lc|std::list}}<br>{{lc|std::forward_list}}|Efficient insertion/deletion in the middle of the sequence}}
+
{{dsc|{{lc|std::array}}|Fast access, inplace contiguous storage, but fixed number of elements and no insertion/deletion.}}
−
{{dsc|{{lc|std::deque}}|Efficient insertion/deletion at the beginning and at the end of the sequence}}
+
{{dsc|{{lc|std::deque}}|Fast access, efficient insertion/deletion at the beginning/end but not in the middle of the sequence.}}
 +
{{dsc|{{lc|std::list}}<br>{{lc|std::forward_list}}|Efficient insertion/deletion in the middle of the sequence, but mostly linear-time access.}}
 
{{dsc end}}
 
{{dsc end}}
  
Line 301: Line 367:
 
{{dr list item|wg=lwg|dr=139|std=C++98|before=the optional operations were not required to<br>be implemented for the designated containers|after=required with<br>amortized time}}
 
{{dr list item|wg=lwg|dr=139|std=C++98|before=the optional operations were not required to<br>be implemented for the designated containers|after=required with<br>amortized time}}
 
{{dr list item|wg=lwg|dr=149|std=C++98|before={{c|a.insert(p, t)}} returned {{tt|iterator}} while<br>{{c|a.insert(p, n, t)}} and {{c|a.insert(p, n, t)}} returned {{c/core|void}}|after=they all return<br>{{tt|iterator}}}}
 
{{dr list item|wg=lwg|dr=149|std=C++98|before={{c|a.insert(p, t)}} returned {{tt|iterator}} while<br>{{c|a.insert(p, n, t)}} and {{c|a.insert(p, n, t)}} returned {{c/core|void}}|after=they all return<br>{{tt|iterator}}}}
−
{{dr list item|wg=lwg|dr=151|std=C++98|before={{c|q1}} was dereferenceable<ref>It is a defect because it makes the behavior of {{c|a.erase(a.begin(), a.end())}} undefined is {{c|a}} is an empty container.</ref>|after=it can be non-dereferenceable}}
+
{{dr list item|wg=lwg|dr=151|std=C++98|before={{c|q1}} was required to be dereferenceable<ref>It is a defect because it makes the behavior of {{c|a.erase(a.begin(), a.end())}} undefined is {{c|a}} is an empty container.</ref>|after=it can be non-dereferenceable}}
−
{{dr list item|wg=lwg|dr=355|std=C++98|before=calling {{c|a.back()}} or {{c|a.pop_back()}} would<br>execute {{c|--a.end()}}, which is dangerous<ref>If the type of {{c|a.end()}} is a fundamental type, {{c|--a.end()}} is ill-formed. It is dangerous when the type of {{c|a}} is templated, in this case this bug can be difficult to be found.</ref>|after=decrements a copy of<br>{{c|a.end()}} instead}}
+
{{dr list item|wg=lwg|dr=355|std=C++98|before=calling {{c|a.back()}} or {{c|a.pop_back()}} would<br>execute {{c|--a.end()}}, which is dangerous<ref>If the type of {{c|a.end()}} is a fundamental type, {{c|--a.end()}} is ill-formed. It is dangerous when the type of {{c|a}} is templated, in this case this bug can be difficult to be found.</ref>|after=decrements a copy<br>of {{c|a.end()}} instead}}
 
{{dr list item|wg=lwg|dr=589|std=C++98|before=the elements that {{c|i}} and {{c|j}} refer to<br>might not be convertible to {{tt|value_type}}|after=they are implicitly<br>convertible to {{tt|value_type}}}}
 
{{dr list item|wg=lwg|dr=589|std=C++98|before=the elements that {{c|i}} and {{c|j}} refer to<br>might not be convertible to {{tt|value_type}}|after=they are implicitly<br>convertible to {{tt|value_type}}}}
 +
{{dr list item|wg=lwg|dr=2194|std=C++11|before={{lc|std::queue}}, {{lc|std::priority_queue}} and<br>{{lc|std::stack}} were also {{named req/core|SequenceContainer}}s<ref>They were not documented as {{named req/core|SequenceContainer}}s in C++98.</ref>|after=they are not {{named req/core|SequenceContainer}}s}}
 +
{{dr list item|wg=lwg|dr=3927|std=C++98|before={{c/core|operator[]}} had no implicit requirement|after=added the implicit requirement}}
 
{{dr list end}}
 
{{dr list end}}
 
<references/>
 
<references/>
  
 
{{langlinks|de|es|fr|it|ja|pt|ru|zh}}
 
{{langlinks|de|es|fr|it|ja|pt|ru|zh}}

Latest revision as of 00:50, 12 November 2024

 
C++
 
C++ named requirements
 

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

Contents

[edit] Requirements

Legend
X A sequence container class
T The element type of X
a A value of type X
u The name of a declared variable
A The allocator type of X:
i, j LegacyInputIterators such that [i, j) is a valid range and that the iterators refer to elements implicitly convertible to value_type
rg (since C++23) A value of a type R that models container-compatible-range<T>
il (since C++11) An object of type std::initializer_list<value_type>
n A value of type X::size_type
p A valid const iterator into a
q A valid dereferenceable const iterator into a
q1, q2 Two const iterators into a such that [q1, q2) is a valid range
t An lvalue or const rvalue(since C++11) of type X::value_type
rv (since C++11) A non-const rvalue of type X::value_type
Args (since C++11) A template parameter pack
args (since C++11) A function parameter pack with the pattern Arg&&

The type X satisfies SequenceContainer if

  • The type X satisfies Container, and
  • The following statements and expressions must be valid and have their specified effects for all sequence containers except std::array (see notes)(since C++11):
Statement Effects     Conditions[1]
X u(n, t) Constructs the sequence container holding n copies of t Pre T is CopyInsertable into X
Post  std::distance(u.begin(), u.end())
    == n
X u(i, j) Constructs the sequence container equal, element-wise, to the range [i, j) Pre T is EmplaceConstructible from *i into X
Post std::distance(u.begin(), u.end())
    == std::distance(i, j)
Expression Type Effects Conditions
X(std::from_range, rg)
(since C++23) 		X Constructs the sequence container equal, element-wise, to the range rg Pre T is EmplaceConstructible into X from *ranges::begin(rg)
Post
X(il)
(since C++11) 		X Equivalent to X(il.begin(),
    il.end()) 		No explicit requirement
a = il
(since C++11) 		X& Assigns the range represented by il into a.[2] Pre T is CopyInsertable and CopyAssignable
Post Existing elements of a are destroyed or assigned to
a.emplace(p, args)
(since C++11) 		iterator Insert an object of type T, constructed with std::forward<Args>(args) before p Pre T is EmplaceConstructible
Post The returned iterator points at the element constructed from args into a
a.insert(p, t) iterator Inserts a copy of t before p Pre T is CopyInsertable
Post The returned iterator points at the copy of t inserted into a
a.insert(p, rv)
(since C++11) 		iterator Inserts a copy of rv before p, possibly using move semantics Pre T is MoveInsertable
Post The returned iterator points at the copy of rv inserted into a
a.insert(p, n, t) iterator Inserts n copies of t before p Pre T is CopyInsertable and CopyAssignable
Post The returned iterator points at the copy of the first element inserted into a or is p for n == 0
a.insert(p, i, j) iterator Inserts copies of elements in
[i, j) before p 		Pre T is EmplaceConstructible and i and j are not in a
Post
  • Each iterator in [i, j) is dereferenced once.
  • The returned iterator points at the copy of the first element inserted into a or is p for i == j
a.insert_range(p, rg)
(since C++23) 		iterator Inserts copies of elements in rg before p Pre
Post
  • Each iterator in the range rg is dereferenced once
  • The returned iterator points at the copy of the first element inserted into a or at p if rg is empty
a.insert(p, il)
(since C++11) 		iterator Equivalent to a.insert(p,
         il.begin(),
         il.end()) 		Pre No explicit requirement
Post The returned iterator points at the copy of the first element inserted into a or is p if il is empty
a.erase(q) iterator Erases the element pointed to by q Pre No explicit requirement
Post The 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) iterator Erases elements in [q1, q2) Pre No explicit requirement
Post The 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() void Destroys all elements in a Pre No explicit requirement
Post
  • All references, pointers, and iterators are invalidated, including the end iterator
  • a.empty() is true
a.assign(i, j) void Replaces elements in a with a copy of [i, j) Pre
Post Each iterator in [i, j) is dereferenced once.
a.assign_range(rg)
(since C++23) 		void Replaces elements in a with a copy of each element in rg Pre
Post
  • Each iterator in the range rg is dereferenced once.
  • All references, pointers, and iterators are invalidated.
a.assign(il)
(since C++11) 		void Equivalent to

a.assign(il.begin(),
         il.end())

No explicit requirement
a.assign(n, t) void Replaces elements in a with n copies of t Pre T is CopyInsertable and CopyAssignable
Post No explicit requirement
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 braced-init-list, but not from an std::initializer_list.
  3. ↑ T and R are types such that std::assignable_from<T&, ranges::range_reference_t<R>> is modeled.

[edit] Optional operations

The following expressions must be valid and have their specified effects for the sequence containers named, all operations except prepend_range and append_range(since C++23) take amortized constant time:

Expression Type Effects     Preconditions[1] Containers
a.front() reference, or

const_reference for const a

Returns *a.begin() No explicit requirement std::basic_string, std::array, std::deque, std::forward_list, std::inplace_vector, std::list, std::vector
a.back() reference, or

const_reference for const a

Equivalent to auto tmp = a.end();
--tmp;
return *tmp; 		No explicit requirement std::basic_string, std::array, std::deque, std::inplace_vector, std::list, std::vector
a.emplace_front(args)
(since C++11) 		void Prepends a T constructed with std::forward<Args>
    (args)... 		T is EmplaceConstructible into X from args std::deque, std::forward_list, std::list
a.emplace_back(args)
(since C++11) 		void Appends a T constructed with std::forward<Args>
    (args)... 		T is EmplaceConstructible into X from args std::deque, std::inplace_vector, std::list, std::vector
a.push_front(t) void Prepends a copy of t T is CopyInsertable into X std::deque, std::forward_list, std::list
a.push_front(rv)
(since C++11) 		void Prepends a copy of rv, possibly using move semantics T is MoveInsertable into X
a.prepend_range(rg)
(since C++23) 		void Inserts[2] copies of elements in rg before begin(), each iterator in rg is dereferenced once T is EmplaceConstructible into X from *ranges::begin(rg) std::deque, std::forward_list, std::list
a.push_back(t) void Appends a copy of t T is CopyInsertable into X std::basic_string, std::deque, std::inplace_vector, std::list, std::vector
a.push_back(rv)
(since C++11) 		void Appends a copy of rv, possibly using move semantics T is MoveInsertable into X
a.append_range(rg)
(since C++23) 		void Inserts[2] copies of elements in rg before end() dereferencing each iterator in rg once T is EmplaceConstructible into X from *ranges::begin(rg) std::deque, std::inplace_vector, std::list, std::vector
a.pop_front() void Destroys the first element a.empty() is false std::deque, std::forward_list, std::list
a.pop_back() void Destroys the last element a.empty() is false std::basic_string, std::deque, std::inplace_vector, std::list, std::vector
a[n] reference, or

const_reference for const a

Returns *(a.begin() + n) No explicit requirement std::basic_string, std::array, std::deque, std::inplace_vector, std::vector
a.at(n) reference, or

const_reference for const a

Returns *(a.begin() + n), throws std::out_of_range if n >= size() No explicit requirement
Notes
  1. ↑ For an expression whose effect is equivalent to some other operations, the preconditions of the expressions inside those operations are inherited on top of the preconditions listed in the table.
  2. ↑ 2.0 2.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] Sequence containers in the standard library

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

[edit] Trade-offs / usage notes

std::vector Fast access, but mostly inefficient insertions/deletions.
std::inplace_vector Fast access, inplace contiguous storage, but fixed capacity and mostly inefficient insertions/deletions.
std::array Fast access, inplace contiguous storage, but fixed number of elements and no insertion/deletion.
std::deque Fast access, efficient insertion/deletion at the beginning/end but not in the middle of the sequence.
std::list
std::forward_list 		Efficient insertion/deletion in the middle of the sequence, but mostly linear-time access.

[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 a.insert(p, t) returned iterator while
a.insert(p, n, t) and a.insert(p, n, t) returned void 		they all return
iterator
LWG 151 C++98 q1 was required to be dereferenceable[1] it can be non-dereferenceable
LWG 355 C++98 calling a.back() or a.pop_back() would
execute --a.end(), which is dangerous[2] 		decrements a copy
of a.end() instead
LWG 589 C++98 the elements that i and j refer to
might not be convertible to value_type 		they are implicitly
convertible to value_type
LWG 2194 C++11 std::queue, std::priority_queue and
std::stack were also SequenceContainers[3] 		they are not SequenceContainers
LWG 3927 C++98 operator[] had no implicit requirement added the implicit requirement
  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.
  3. ↑ They were not documented as SequenceContainers in C++98.
Retrieved from "https://en.cppreference.com/mwiki/index.php?title=cpp/named_req/SequenceContainer&oldid=177614"