SequenceContainer

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

Requirements

The type X satisfies SequenceContainer if.

The type X satisfies Container, and

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, InputIterators 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 `ForwardIterator`s, 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 `ForwardIterator`s, 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 `[p,q)`	(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 `ForwardIterator`. `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
`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::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 InputIterator.

SequenceContainers in the standard library

basic_string	stores and manipulates sequences of characters (class template)
array (since C++11)	static contiguous array (class template)
vector	dynamic contiguous array (class template)
deque	double-ended queue (class template)
forward_list (since C++11)	singly-linked list (class template)
list	doubly-linked list (class template)

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

Links:

http://en.cppreference.com/w/cpp/concept/SequenceContainer

doc_CPP

2016-10-11 10:00:01

Comments