Namespaces
Variants
Views
Actions

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

From cppreference.com
< cpp‎ | named req
({{dsc inc | cpp/string/dsc basic_string_view}} // since C++17)
(Undo revision 96333 by Dbjdbj (talk))
Line 198: Line 198:
 
{{dsc begin}}
 
{{dsc begin}}
 
{{dsc inc | cpp/string/dsc basic_string}}
 
{{dsc inc | cpp/string/dsc basic_string}}
−
{{dsc inc | cpp/string/dsc basic_string_view}} // since C++17
 
 
{{dsc inc | cpp/container/dsc array}}
 
{{dsc inc | cpp/container/dsc array}}
 
{{dsc inc | cpp/container/dsc vector}}
 
{{dsc inc | cpp/container/dsc vector}}

Revision as of 03:53, 22 October 2017

Template:cpp/concept/title Template:cpp/concept/navbar

A SequenceContainer is a Template:concept 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 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, Template:concepts 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 Template:concept 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 Template:concept from *i into X

(only for std::vector) If the iterators are not Template:concepts, T must be Template:concept

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 Template:concept and Template:concept 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 Template:concept

(for std::vector and std::deque) T Template:concept and Template:concept

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

(for std::vector and std::deque) T Template:concept or Template:concept

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 Template:concept

(for std::vector and std::deque) T Template:concept

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 Template:concept and Template:concept 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 Template:concept and i and j are not in a

(only for std::vector) If the iterators are not Template:concepts, T must be Template:concept and Template:concept

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 Template:concept 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 [p,q) (std::deque, std::vector) T Template:concept 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 Template:concept and i, j not in a

(std::vector) If not Template:concept. T Template:concept

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 Template:concept and Template:concept
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 Template:concept 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 Template:concept into X from args

(std::vector only) T Template:concept into X

std::deque std::list std::vector
a.push_front(t) void Prepends a copy of t T Template:concept into X std::deque std::forward_list std::list
a.push_front(rv) void Prepends a copy of rv, possibly using move semantics T Template:concept into X std::deque std::forward_list std::list
a.push_back(t) void Appends a copy of t T Template:concept 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 Template:concept 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 Template:concept.

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=96337"