Namespaces
Variants
Views
Actions

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

From cppreference.com
< cpp‎ | named req
m (T. Canens moved page cpp/concept/SequenceContainer to cpp/named req/SequenceContainer without leaving a redirect: Text replace - "cpp/concept" to "cpp/named req")
m (Text replace - "{{concept" to "{{named req")
Line 2: Line 2:
 
{{cpp/named req/navbar}}
 
{{cpp/named req/navbar}}
  
−
A {{ttb|SequenceContainer}} is a {{concept|Container}} that stores objects of the same type in a linear arrangement.
+
A {{ttb|SequenceContainer}} is a {{named req|Container}} that stores objects of the same type in a linear arrangement.
  
 
===Requirements===
 
===Requirements===
Line 8: Line 8:
 
The type {{tt|X}} satisfies {{tt|SequenceContainer}} if
 
The type {{tt|X}} satisfies {{tt|SequenceContainer}} if
  
−
* The type {{tt|X}} satisfies {{concept|Container}}, and
+
* The type {{tt|X}} satisfies {{named req|Container}}, and
 
<!-- already listed in Container (Table 96), even though 23.2.3[sequence.reqmts]/5 repeats that for sequence containers, we don't have to repeat here
 
<!-- already listed in Container (Table 96), even though 23.2.3[sequence.reqmts]/5 repeats that for sequence containers, we don't have to repeat here
  
−
* The type {{tt|X::iterator}} satisfies {{concept|ForwardIterator}}, and
+
* The type {{tt|X::iterator}} satisfies {{named req|ForwardIterator}}, and
−
* The type {{tt|X::const_iterator}} satisfies {{concept|ForwardIterator}}, and -->
+
* The type {{tt|X::const_iterator}} satisfies {{named req|ForwardIterator}}, and -->
  
 
Given
 
Given
Line 21: Line 21:
 
* {{tt|q}}, a valid dereferenceable const iterator into {{tt|a}}
 
* {{tt|q}}, a valid dereferenceable const iterator into {{tt|a}}
 
* {{tt|q1}} and {{tt|q2}}, two const iterators into {{tt|a}} such that {{c|[q1, q2)}} is a valid range
 
* {{tt|q1}} and {{tt|q2}}, two const iterators into {{tt|a}} such that {{c|[q1, q2)}} is a valid range
−
* {{tt|i}} and {{tt|j}}, {{concept|InputIterator}}s such that {{c|[i, j)}} is a valid range and that the iterators refer to elements implicitly convertible to {{tt|value_type}}
+
* {{tt|i}} and {{tt|j}}, {{named req|InputIterator}}s such that {{c|[i, j)}} is a valid range and that the iterators refer to elements implicitly convertible to {{tt|value_type}}
 
* {{tt|il}}, an object of type {{c|std::initializer_list<value_type>}}
 
* {{tt|il}}, an object of type {{c|std::initializer_list<value_type>}}
 
* {{tt|n}}, a value of type {{c|X::size_type}}
 
* {{tt|n}}, a value of type {{c|X::size_type}}
Line 38: Line 38:
 
|
 
|
 
|Constructs the sequence container holding {{ttb|n}} copies of {{ttb|t}}
 
|Constructs the sequence container holding {{ttb|n}} copies of {{ttb|t}}
−
|{{tt|T}} {{concept|CopyInsertable}} into {{tt|X}}
+
|{{tt|T}} {{named req|CopyInsertable}} into {{tt|X}}
 
|{{c|std::distance(begin(),end()) {{==}} n}}
 
|{{c|std::distance(begin(),end()) {{==}} n}}
 
|-
 
|-
Line 45: Line 45:
 
|
 
|
 
|Constructs the sequence container equal, element-wise, to the range {{tt|[i,j)}}
 
|Constructs the sequence container equal, element-wise, to the range {{tt|[i,j)}}
−
| {{tt|T}} is {{concept|EmplaceConstructible}} from {{tt|*i}} into {{tt|X}}
+
| {{tt|T}} is {{named req|EmplaceConstructible}} from {{tt|*i}} into {{tt|X}}
−
{{mark|only for std::vector}} If the iterators are not {{concept|ForwardIterator}}s, T must be {{concept|CopyInsertable}}
+
{{mark|only for std::vector}} If the iterators are not {{named req|ForwardIterator}}s, T must be {{named req|CopyInsertable}}
 
|{{c|1=std::distance(begin(),end()) == std::distance(i,j)}}
 
|{{c|1=std::distance(begin(),end()) == std::distance(i,j)}}
 
|-
 
|-
Line 52: Line 52:
 
|-
 
|-
 
|{{c|1=a = il}}||{{c|X&}}||Assigns the range represented by {{ttb|il}} into {{ttb|a}}<ref>{{lc|std::array}} supports assignment from a braced-init-list, but not from an {{lc|std::initializer_list}}</ref>
 
|{{c|1=a = il}}||{{c|X&}}||Assigns the range represented by {{ttb|il}} into {{ttb|a}}<ref>{{lc|std::array}} supports assignment from a braced-init-list, but not from an {{lc|std::initializer_list}}</ref>
−
| T {{concept|CopyInsertable}} and {{concept|CopyAssignable}}
+
| T {{named req|CopyInsertable}} and {{named req|CopyAssignable}}
 
| Existing elements of {{ttb|a}} are destroyed or assigned to
 
| Existing elements of {{ttb|a}} are destroyed or assigned to
 
|-  
 
|-  
 
|{{c|a.emplace(p,args)}}||{{tt|iterator}}
 
|{{c|a.emplace(p,args)}}||{{tt|iterator}}
 
|Insert an object of type {{tt|T}}, constructed with {{c|std::forward<Args>(args)}} before {{ttb|p}}
 
|Insert an object of type {{tt|T}}, constructed with {{c|std::forward<Args>(args)}} before {{ttb|p}}
−
|{{tt|T}} {{concept|CopyInsertable}}
+
|{{tt|T}} {{named req|CopyInsertable}}
−
{{mark|for std::vector and std::deque}} {{tt|T}} {{concept|MoveAssignable}} and {{concept|MoveInsertable}}
+
{{mark|for std::vector and std::deque}} {{tt|T}} {{named req|MoveAssignable}} and {{named req|MoveInsertable}}
 
|Returned iterator points at the element constructed from {{tt|args}} into {{tt|a}}
 
|Returned iterator points at the element constructed from {{tt|args}} into {{tt|a}}
 
|-  
 
|-  
 
|{{c|a.insert(p,t)}}||{{tt|iterator}}
 
|{{c|a.insert(p,t)}}||{{tt|iterator}}
 
|Inserts a copy of {{ttb|t}} before {{ttb|p}}
 
|Inserts a copy of {{ttb|t}} before {{ttb|p}}
−
|{{tt|T}} {{concept|CopyInsertable}}
+
|{{tt|T}} {{named req|CopyInsertable}}
−
{{mark|for std::vector and std::deque}} {{tt|T}} {{concept|CopyAssignable}} or {{concept|MoveAssignable}}
+
{{mark|for std::vector and std::deque}} {{tt|T}} {{named req|CopyAssignable}} or {{named req|MoveAssignable}}
 
|Returned iterator points at the copy of {{tt|t}} inserted into {{tt|a}}
 
|Returned iterator points at the copy of {{tt|t}} inserted into {{tt|a}}
 
|-  
 
|-  
 
|{{c|a.insert(p,rv)}}||{{tt|iterator}}
 
|{{c|a.insert(p,rv)}}||{{tt|iterator}}
 
|Inserts a copy of {{ttb|rv}} before {{ttb|p}}, possibly using move semantics
 
|Inserts a copy of {{ttb|rv}} before {{ttb|p}}, possibly using move semantics
−
|{{tt|T}} {{concept|MoveInsertable}}
+
|{{tt|T}} {{named req|MoveInsertable}}
−
{{mark|for std::vector and std::deque}} {{tt|T}} {{concept|MoveAssignable}}
+
{{mark|for std::vector and std::deque}} {{tt|T}} {{named req|MoveAssignable}}
 
|Returned iterator points at the copy of {{tt|rv}} inserted into {{tt|a}}
 
|Returned iterator points at the copy of {{tt|rv}} inserted into {{tt|a}}
 
|-
 
|-
 
|{{c|a.insert(p,n,t)}}||{{tt|iterator}}||Inserts {{ttb|n}} copies of {{ttb|t}} before {{ttb|p}}
 
|{{c|a.insert(p,n,t)}}||{{tt|iterator}}||Inserts {{ttb|n}} copies of {{ttb|t}} before {{ttb|p}}
−
|{{tt|T}} {{concept|CopyInsertable}} and {{concept|CopyAssignable}}
+
|{{tt|T}} {{named req|CopyInsertable}} and {{named req|CopyAssignable}}
 
|Returned iterator points at the copy of the first element inserted into {{tt|a}} or is {{tt|p}} for {{c|1=n==0}}
 
|Returned iterator points at the copy of the first element inserted into {{tt|a}} or is {{tt|p}} for {{c|1=n==0}}
 
|-
 
|-
 
|{{c|a.insert(p,i,j)}}||{{tt|iterator}}||Inserts copies of elements in {{tt|[i, j)}} before {{ttb|p}}
 
|{{c|a.insert(p,i,j)}}||{{tt|iterator}}||Inserts copies of elements in {{tt|[i, j)}} before {{ttb|p}}
−
| T {{concept|EmplaceConstructible}} and {{ttb|i}} and {{ttb|j}} are not in {{ttb|a}}
+
| T {{named req|EmplaceConstructible}} and {{ttb|i}} and {{ttb|j}} are not in {{ttb|a}}
−
{{mark|only for std::vector}} If the iterators are not {{concept|ForwardIterator}}s, T must be {{concept|MoveInsertable}} and {{concept|MoveAssignable}}
+
{{mark|only for std::vector}} If the iterators are not {{named req|ForwardIterator}}s, T must be {{named req|MoveInsertable}} and {{named req|MoveAssignable}}
 
|Each iterator in {{tt|[i,j)}} is dereferenced once. Returned iterator points at the copy of the first element inserted into {{tt|a}} or is {{tt|p}} for {{c|1=i==j}}
 
|Each iterator in {{tt|[i,j)}} is dereferenced once. Returned iterator points at the copy of the first element inserted into {{tt|a}} or is {{tt|p}} for {{c|1=i==j}}
 
|-
 
|-
Line 85: Line 85:
 
|-
 
|-
 
|{{c|a.erase(q)}}||{{tt|iterator}}||Erases the element pointed to by {{tt|q}}
 
|{{c|a.erase(q)}}||{{tt|iterator}}||Erases the element pointed to by {{tt|q}}
−
|{{mark|std::deque, std::vector}} T {{concept|MoveAssignable}}
+
|{{mark|std::deque, std::vector}} T {{named req|MoveAssignable}}
 
|Returned iterator points at the element that was immediately following {{tt|q}} prior to erasure, or {{c|a.end()}} if no such element exists.
 
|Returned iterator points at the element that was immediately following {{tt|q}} prior to erasure, or {{c|a.end()}} if no such element exists.
 
|-
 
|-
−
|{{c|a.erase(q1,q2)}}||{{tt|iterator}}||Erases elements in {{tt|[q1,q2)}}||{{mark|std::deque, std::vector}} T {{concept|MoveAssignable}}||Returned iterator points at the element that was pointed by {{tt|q2}} prior to any erasure, or {{c|a.end()}} if no such element exists.
+
|{{c|a.erase(q1,q2)}}||{{tt|iterator}}||Erases elements in {{tt|[q1,q2)}}||{{mark|std::deque, std::vector}} T {{named req|MoveAssignable}}||Returned iterator points at the element that was pointed by {{tt|q2}} prior to any erasure, or {{c|a.end()}} if no such element exists.
 
|-
 
|-
 
|{{c|a.clear()}}||{{tt|void}}||Destroys all elements in {{ttb|a}}|| ||
 
|{{c|a.clear()}}||{{tt|void}}||Destroys all elements in {{ttb|a}}|| ||
Line 94: Line 94:
 
|-
 
|-
 
|{{c|a.assign(i,j)}}||{{tt|void}}||Replaces elements in a with a copy of {{tt|[i, j)}}
 
|{{c|a.assign(i,j)}}||{{tt|void}}||Replaces elements in a with a copy of {{tt|[i, j)}}
−
|{{tt|T}} {{concept|EmplaceConstructible}} and {{ttb|i}}, {{ttb|j}} not in {{ttb|a}}
+
|{{tt|T}} {{named req|EmplaceConstructible}} and {{ttb|i}}, {{ttb|j}} not in {{ttb|a}}
−
{{mark|std::vector}} If not {{concept|ForwardIterator}}. {{tt|T}} {{concept|MoveInsertable}}
+
{{mark|std::vector}} If not {{named req|ForwardIterator}}. {{tt|T}} {{named req|MoveInsertable}}
 
|Each iterator in {{tt|[i,j)}} is dereferenced once
 
|Each iterator in {{tt|[i,j)}} is dereferenced once
 
|-
 
|-
Line 102: Line 102:
 
|{{c|a.assign(n,t)}}||{{tt|void}}
 
|{{c|a.assign(n,t)}}||{{tt|void}}
 
|Replaces elements in {{ttb|a}} with {{ttb|n}} copies of {{ttb|t}}
 
|Replaces elements in {{ttb|a}} with {{ttb|n}} copies of {{ttb|t}}
−
|T {{concept|CopyInsertable}} and {{concept|CopyAssignable}}
+
|T {{named req|CopyInsertable}} and {{named req|CopyAssignable}}
 
|
 
|
 
|-
 
|-
Line 132: Line 132:
 
|{{tt|void}}
 
|{{tt|void}}
 
|Prepends a {{tt|T}} constructed with {{c|std::forward<Args>(args)...}}
 
|Prepends a {{tt|T}} constructed with {{c|std::forward<Args>(args)...}}
−
|{{tt|T}} {{concept|EmplaceConstructible}} into {{tt|X}} from {{tt|args}}
+
|{{tt|T}} {{named req|EmplaceConstructible}} into {{tt|X}} from {{tt|args}}
 
|{{lc|std::deque}} {{lc|std::forward_list}} {{lc|std::list}}
 
|{{lc|std::deque}} {{lc|std::forward_list}} {{lc|std::list}}
 
|-
 
|-
Line 138: Line 138:
 
|{{tt|void}}
 
|{{tt|void}}
 
|Appends a {{tt|T}} constructed with {{c|std::forward<Args>(args)...}}
 
|Appends a {{tt|T}} constructed with {{c|std::forward<Args>(args)...}}
−
|{{tt|T}} {{concept|EmplaceConstructible}} into {{tt|X}} from {{tt|args}}
+
|{{tt|T}} {{named req|EmplaceConstructible}} into {{tt|X}} from {{tt|args}}
−
{{mark|std::vector only}} {{tt|T}} {{concept|MoveInsertable}} into {{tt|X}}
+
{{mark|std::vector only}} {{tt|T}} {{named req|MoveInsertable}} into {{tt|X}}
 
|{{lc|std::deque}} {{lc|std::list}} {{lc|std::vector}}
 
|{{lc|std::deque}} {{lc|std::list}} {{lc|std::vector}}
 
|-
 
|-
Line 145: Line 145:
 
|{{tt|void}}
 
|{{tt|void}}
 
|Prepends a copy of {{tt|t}}
 
|Prepends a copy of {{tt|t}}
−
|{{tt|T}} {{concept|CopyInsertable}} into {{tt|X}}
+
|{{tt|T}} {{named req|CopyInsertable}} into {{tt|X}}
 
|{{lc|std::deque}} {{lc|std::forward_list}} {{lc|std::list}}
 
|{{lc|std::deque}} {{lc|std::forward_list}} {{lc|std::list}}
 
|-
 
|-
Line 151: Line 151:
 
|{{tt|void}}
 
|{{tt|void}}
 
|Prepends a copy of {{tt|rv}}, possibly using move semantics
 
|Prepends a copy of {{tt|rv}}, possibly using move semantics
−
|{{tt|T}} {{concept|MoveInsertable}} into {{tt|X}}
+
|{{tt|T}} {{named req|MoveInsertable}} into {{tt|X}}
 
|{{lc|std::deque}} {{lc|std::forward_list}} {{lc|std::list}}
 
|{{lc|std::deque}} {{lc|std::forward_list}} {{lc|std::list}}
 
|-
 
|-
Line 157: Line 157:
 
|{{tt|void}}
 
|{{tt|void}}
 
|Appends a copy of {{tt|t}}
 
|Appends a copy of {{tt|t}}
−
|{{tt|T}} {{concept|CopyInsertable}} into {{tt|X}}
+
|{{tt|T}} {{named req|CopyInsertable}} into {{tt|X}}
 
|{{lc|std::basic_string}} {{lc|std::deque}} {{lc|std::list}} {{lc|std::vector}}
 
|{{lc|std::basic_string}} {{lc|std::deque}} {{lc|std::list}} {{lc|std::vector}}
 
|-
 
|-
Line 163: Line 163:
 
|{{tt|void}}
 
|{{tt|void}}
 
|Appends a copy of {{tt|rv}}, possibly using move semantics
 
|Appends a copy of {{tt|rv}}, possibly using move semantics
−
|{{tt|T}} {{concept|MoveInsertable}} into {{tt|X}}
+
|{{tt|T}} {{named req|MoveInsertable}} into {{tt|X}}
 
|{{lc|std::basic_string}} {{lc|std::deque}} {{lc|std::list}} {{lc|std::vector}}
 
|{{lc|std::basic_string}} {{lc|std::deque}} {{lc|std::list}} {{lc|std::vector}}
 
|-
 
|-
Line 193: Line 193:
 
|}
 
|}
  
−
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 {{concept|InputIterator}}.
+
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}}.
  
 
===SequenceContainers in the standard library===
 
===SequenceContainers in the standard library===

Revision as of 14:29, 15 June 2018

 
C++
 
C++ named requirements
 

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, 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:

expression return type effects precondition postcondition
X(n, t)

X a(n, t)

Constructs the sequence container holding n copies of t T CopyInsertable into X std::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 CopyInsertable

std::distance(begin(),end()) == std::distance(i,j)
X(il) X(il.begin(), il.end())
a = il X& Assigns the range represented by il into a[1] T CopyInsertable and CopyAssignable Existing elements of a are destroyed or assigned to
a.emplace(p,args) iterator Insert an object of type T, constructed with std::forward<Args>(args) before p T CopyInsertable

(for std::vector and std::deque) T MoveAssignable and MoveInsertable

Returned iterator points at the element constructed from args into a
a.insert(p,t) iterator Inserts a copy of t before p T CopyInsertable

(for std::vector and std::deque) T CopyAssignable or MoveAssignable

Returned iterator points at the copy of t inserted into a
a.insert(p,rv) iterator Inserts a copy of rv before p, possibly using move semantics T MoveInsertable

(for std::vector and std::deque) T MoveAssignable

Returned iterator points at the copy of rv inserted into a
a.insert(p,n,t) iterator Inserts n copies of t before p T CopyInsertable and CopyAssignable 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 T 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) iterator a.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) iterator Erases the element pointed to by q (std::deque, std::vector) T 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) iterator Erases elements in [q1,q2) (std::deque, std::vector) T 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() void Destroys all elements in a

All references, pointers, and iterators are invalidated, including the end iterator. a.empty() == true.

a.assign(i,j) void Replaces elements in a with a copy of [i, j) T EmplaceConstructible and i, j not in a

(std::vector) If not LegacyForwardIterator. T MoveInsertable

Each iterator in [i,j) is dereferenced once
a.assign(il) void a.assign(il.begin(),il.end())
a.assign(n,t) void Replaces elements in a with n copies of t T CopyInsertable and CopyAssignable
notes
  1. ↑ std::array supports assignment from a braced-init-list, but not from an std::initializer_list

The following expressions must be valid and have their specified effects for the sequence containers named:

expression return type effects preconditions containers
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) void Prepends a T constructed with std::forward<Args>(args)... T EmplaceConstructible into X from args std::deque std::forward_list std::list
a.emplace_back(args) void Appends a T constructed with std::forward<Args>(args)... T EmplaceConstructible into X from args

(std::vector only) T MoveInsertable into X

std::deque std::list std::vector
a.push_front(t) void Prepends a copy of t T CopyInsertable into X std::deque std::forward_list std::list
a.push_front(rv) void Prepends a copy of rv, possibly using move semantics T MoveInsertable into X std::deque std::forward_list std::list
a.push_back(t) void Appends a copy of t T CopyInsertable into X std::basic_string std::deque std::list std::vector
a.push_back(rv) void Appends a copy of rv, possibly using move semantics T MoveInsertable into X std::basic_string std::deque std::list std::vector
a.pop_front() void Destroys the first element. a.empty() == false std::deque std::forward_list std::list
a.pop_back() void Destroys the last element a.empty() == false std::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 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.

SequenceContainers 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]
double-ended queue
(class template) [edit]
(C++11)
 singly-linked list
(class template) [edit]
doubly-linked list
(class template) [edit]

Trade-offs / usage notes

std::array Fast access but fixed number of elements
std::vector Fast access but mostly inefficient insertions/deletions
std::list
std::forward_list 		Efficient insertion/deletion in the middle of the sequence
std::deque Efficient insertion/deletion at the beginning and at the end of the sequence
Retrieved from "https://en.cppreference.com/mwiki/index.php?title=cpp/named_req/SequenceContainer&oldid=103283"