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

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

Expression	Return type	Effects	Precondition	Postcondition
X(n, t) X a(n, t)		Constructs the sequence container holding n copies of t	T is 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 is 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 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)	iterator	Inserts a copy of t before p	T 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)	iterator	Inserts a copy of rv before p, possibly using move semantics	T 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)	iterator	Inserts n copies of t before p	T is 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 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)	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 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)	iterator	Erases 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()	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 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)	void	a.assign(il.begin(),     il.end())
a.assign(n, t)	void	Replaces elements in a with n copies of t	T 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:

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 is 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 is EmplaceConstructible into X from args (std::vector only) T is MoveInsertable into X	std::deque 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)	void	Prepends a copy of rv, possibly using move semantics	T is MoveInsertable into X	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::list std::vector
a.push_back(rv)	void	Appends a copy of rv, possibly using move semantics	T is 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 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

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

Trade-offs / usage notes

pub	std::vector	Fast access but mostly inefficient insertions/deletions
pub	std::array	Fast access but fixed number of elements
pub	std::list std::forward_list	Efficient insertion/deletion in the middle of the sequence
pub	std::deque	Efficient 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.

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

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.