`static_vector`

A dynamically-resizable vector with fixed capacity and embedded storage

Document number: P0843r5.
Date: 2022-07-12.
Reply-to: Gonzalo Brito Gadeschi <gonzalob _at_ nvidia _dot_ com>.
Audience: LEWG.

Table of Contents

static_vector
Introduction
Motivation and Scope
Existing practice
Design
Technical specification
Acknowledgments
References

Changelog

Revision 5:
- Update contact wording and contact data.
- Removed naming discussion, since it was resolved (last available in P0843r4).
- Removed future extensions discussion (last available in P0843r4).
- Addressed LEWG feedback regarding move-semantics and exception-safety.
Revision 4:
- LEWG suggested that push_back should be UB when the capacity is exceeded
- LEWG suggested that this should be a free-standing header
Revision 3:
- Include LWG design questions for LEWG.
- Incorporates LWG feedback.
Revision 2
- Replace the placeholder name fixed_capacity_vector with static_vector
- Remove at checked element access member function.
- Add changelog section.
Revision 1
- Minor style changes and bugfixes.

Unresolved questions

Proposes <static_vector> as a free-standing header. LWG suggests that static_vector should be included in <vector> instead.
LEWG requested pros/cons of move-semantics in the last meeting and suggested to keep vector programming model. Proposal has been extended and adapted.
LEWG requested pros/cons of exception-safety in the last meeting and suggested to keep vector programming model. Proposal has been extended and adapted.

Introduction

This paper proposes a modernized boost::static_vector<T, Capacity> [1]. That is, a dynamically-resizable vector with compile-time fixed capacity and contiguous embedded storage in which the elements are stored within the vector object itself.

Its API closely resembles that of std::vector<T, A>. It is a contiguous container with O(1) insertion and removal of elements at the end (non-amortized) and worst case O(size()) insertion and removal otherwise. Like std::vector, the elements are initialized on insertion and destroyed on removal. For trivial value_types, the vector is fully usable inside constexpr functions.

Motivation and Scope

The static_vector container is useful when:

memory allocation is not possible, e.g., embedded environments without a free store, where only a stack and the static memory segment are available,
memory allocation imposes an unacceptable performance penalty, e.g., with respect to latency,
allocation of objects with complex lifetimes in the static-memory segment is required,
std::array is not an option, e.g., if non-default constructible objects must be stored,
a dynamically-resizable array is required within constexpr functions,
the storage location of the static_vector elements is required to be within the static_vector object itself (e.g. to support memcpy for serialization purposes).

Existing practice

There are at least 3 widely used implementations of static_vector: Boost.Container [1], EASTL [2], and Folly [3]. Boost.Container implements static_vector as a standalone type with its own guarantees. EASTL and Folly implement it via an extra template parameter in their small_vector types.

Custom allocators like Howard Hinnant’s stack_alloc [4] emulate static_vector on top of std::vector, but as discussed in the next sections, this emulation is not great.

Other prior art includes:

P0494R0: contiguous_container proposal [5]: proposes a Storage concept.
P0597R0: std::constexpr_vector<T> [6]: proposes a vector that can only be used in constexpr contexts.

A reference implementation of this proposal is available here (godbolt).

Design

Should static_vector be a standalone type or a special case of some other type?

The EASTL [2] and Folly [3] special case small_vector, e.g., using a 4th template parameter, to make it become a static_vector. P0639R0: Changing attack vector of the constexpr_vector [7] proposes improving the Allocator concepts to allow implementing static_vector as a special case of std::vector with a custom allocator. Both approaches produce specializations of small_vector or std::vector whose methods subtly differ in terms of effects, exception-safety, iterator invalidation, and complexity guarantees.

This proposal closely follows boost::container::static_vector<T,Capacity> [1] and proposes static_vector as a standalone type.

Where possible, this proposal defines the semantics of static_vector to match std::vector. Providing the same programming model makes this type easier to teach, use, and makes it easy to “just change” one type on a program to, e.g., perform a performance experiment.

Layout

static_vector models ContiguousContainer. Its elements are stored and properly aligned within the static_vector object itself. If the Capacity is zero the container has zero size:

static_assert(is_empty_v<static_vector<T, 0>>); // for all T

The offset of the first element within static_vector is unspecified, and Ts are not allowed to overlap.

The layout differs from std::vector, since static_vector does not store the capacity field (its known from the template parameter)

Move semantics

static_vector move semantics are equivalent to std::vector. The move constructor:


static_vector a(10);
static_vector b(std::move(a));

moves a’s elements element-wise into b. The static_vector is left in a valid but unspecified state.

Design Options for move-semantics of static_vector:

std::array semantics: guarantees that size() of static_vector does not change, and that elements are left in an initialized but unspecified state.
- Con: reduces portability to vector
std::vector semantics: guarantees that static_vector is left in a valid but unspecified state.
- Pro: same programming model as vector
- Con: user must check size() before re-using element storage, just like for vector.
empty source static_vector by resizing it:
- Pro: increases safety by requiring users to re-initialize vector elements
- Con: different programming model than vector

`constexpr` support

The API of static_vector<T, Capacity> can be used in constexpr-contexts if is_trivially_copyable_v<T>, is_default_constructible_v<T>, and is_trivially_destructible<T> are true.

The implementation cost of this is small. The prototye implementation specializes the storage to use a C array with value-initialized elements.

This negatively impacts the algorithmic complexity of static_vector constructors for these types from O(size) to O(capacity). When value-initialization takes place at run-time, this difference is significant.

Vectors with large capacity requirements are better served by std::vector instead.

Exception Safety

Fallible static_vector<value_type, Capacity> APIs:

value_type’s constructors/assignment/destructors/swap can potentially throw (depends on noexcept),
mutating operations exceeding the capacity (push_back, insert, emplace, static_vector(value_type, size), static_vector(begin, end)…), and
out-of-bounds unchecked access: front/back/pop_back when empty, operator[].

We choose the same semantics as for vector

When value_type’s operations are invoked, static_vector exception-safety guarantees depend on whether these operations throw, which is detected with noexcept if the API has a narrow contract.
Mutating operations that exceed the capacity cause the allocator embedded within the static_vector to run out of space, and therefore throw std::bad_alloc like vector APIs do. This preserves the programming model from vector.
out-of-bounds unchecked access is a precondition violation.

Design Options for exception safety semantics of static_vector mutating operations:

Throw an exception:
- Pros: same as std::vector if throws bad_alloc.
Abort the process
- Pros: portability to embedded platforms without exception support
- Cons: different programming model than vector
Precondition violation
- Cons: different proramming model than vector, users responsible for checking before modifying vector size, etc.

Iterator invalidation

static_vector iterator invalidation guarantees differ from std::vector:

moving a static_vector invalidates all iterators, and
swapping two static_vectors invalidates all iterators.

static_vector APIs that potentially invalidate iterators are: resize(n), resize(n, v), pop_back, erase, and swap.

Technical specification

Note to editor: This enhancement is a pure header-only addition to the C++ standard library as the freestanding <static_vector> header. It belongs in the “Sequence containers” (\ref{sequences}) part of the “Containers library” (\ref{containers}) as “Class template static_vector”.

UNRESOLVED QUESTION: LWG recommends making this header part of <vector>.

Note: one of the primary use cases for this container is embedded/freestanding applications. Do we impact those by not putting it in a free-standing header and adding it to <vector> instead?

[library.requirements.organization.headers]

Add <static_vector> to [tab:headers.cpp].

[library.requirements.organization.compliance]

Add <static_vector> tp [tab:headers.cpp.fs]:

[containers]
Subclause: containers
Headers: <static_vector>

[container.reqmts] General container requirements

http://eel.is/c++draft/container.reqmts

A type X meets the container requirements if the following types, statements, and expressions are well-formed and have the specified semantics.

typename X::value_type

Result: T
Preconditions: T is Cpp17Erasable from X (see [container.alloc.reqmts], below).

typename X::reference

Result: T&

typename X::const_reference

Result: const T&

typename X::iterator

Result: A type that meets the forward iterator requirements ([forward.iterators]) with value type T. The type X::iterator is convertible to X::const_iterator.

typename X::const_iterator

Result: A type that meets the requirements of a constant iterator and those of a forward iterator with value type T.

typename X::differcence_type

Result: A signed integer type, identical to the difference type of X::iterator and X::const_iterator.

typename X::size_type

Result: An unsigned integer type that can represent any non-negative value of X::difference_type.

X u;
X u = X();

Postconditions: u.empty()
Complexity: Constant.

X u(a);
X u = a;

Preconditions: T is Cpp17CopyInsertable into X (see below).
Postconditions: u == a
Complexity: Linear.

X u(rv);
X u = rv;

Postconditions: u is equal to the value that rv had before this construction.
Complexity: Linear for array and static_vector and constant for all other standard containers.

a = rv

Result: X&.
Effects: All existing elements of a are either move assigned to or destroyed.
Postconditions: If a and rv do not refer to the same object, a is equal to the value that rv had before this assignment.
Complexity: Linear.

a.~X()

Result: void
Effects: Destroys every element of a; any memory obtained is deallocated.
Complexity: Linear.

a.begin()

Result: iterator; const_iterator for constant a.
Returns: An iterator referring to the first element in the container.
Complexity: Constant.

a.end()

Result: iterator; const_iterator for constant a.
Returns: An iterator which is the past-the-end value for the container.
Complexity: Constant.

a.cbegin()

Result: const_iterator.
Returns: const_cast<X const&>(a).begin()
Complexity: Constant.

a.cend()

Result: const_iterator.
Returns: const_cast<X const&>(a).end()
Complexity: Constant.

i <=> j

Result: strong_ordering.
Constraints: X::iterator meets the random access iterator requirements.
Complexity: Constant.

a == b

Preconditions: T meets the Cpp17EqualityComparable requirements.
Result: Convertible to bool.
Returns: equal(a.begin(), a.end(), b.begin(), b.end()) [Note 1: The algorithm equal is defined in [alg.equal]. — end note]
Complexity: Constant if a.size() != b.size(), linear otherwise.
Remarks: == is an equivalence relation.

a != b

Effects: Equivalent to !(a == b).

a.swap(b)

Result: void
Effects: Exchanges the contents of a and b.
Complexity: Linear for array and static_vector, and constant for all other standard containers.

swap(a, b)

Effects: Equivalent to a.swap(b).

r = a

Result: X&.
Postconditions: r == a.
Complexity: Linear.

a.size()

Result: size_type.
Returns: distance(a.begin(), a.end()), i.e. the number of elements in the container.
Complexity: Constant.
Remarks: The number of elements is defined by the rules of constructors, inserts, and erases.

a.max_size()

Result: size_type.
Returns: distance(begin(), end()) for the largest possible container.
Complexity: Constant.

a.empty()

Result: Convertible to bool.
Returns: a.begin() == a.end()
Complexity: Constant.
Remarks: If the container is empty, then a.empty() is true.

In the expressions

i == j
i != j
i < j
i <= j
i >= j
i > j
i <=> j
i - j

where i and j denote objects of a container’s iterator type, either or both may be replaced by an object of the container’s const_iterator type referring to the same element with no change in semantics.

Unless otherwise specified, all containers defined in this Clause obtain memory using an allocator (see [allocator.requirements]).

[Note 2: In particular, containers and iterators do not store references to allocated elements other than through the allocator’s pointer type, i.e., as objects of type P or pointer_traits<P>::template rebind<unspecified>, where P is allocator_traits<allocator_type>::pointer. — end note]

Copy constructors for these container types obtain an allocator by calling allocator_traits<allocator_type>::select_on_container_copy_construction on the allocator belonging to the container being copied. Move constructors obtain an allocator by move construction from the allocator belonging to the container being moved. Such move construction of the allocator shall not exit via an exception. All other constructors for these container types take a const allocator_type& argument.

[Note 3: If an invocation of a constructor uses the default value of an optional allocator argument, then the allocator type must support value-initialization. — end note]

A copy of this allocator is used for any memory allocation and element construction performed, by these constructors and by all member functions, during the lifetime of each container object or until the allocator is replaced. The allocator may be replaced only via assignment or swap(). Allocator replacement is performed by copy assignment, move assignment, or swapping of the allocator only if

allocator_traits<allocator_type>::propagate_on_container_copy_assignment::value,
allocator_traits<allocator_type>::propagate_on_container_move_assignment::value, or
allocator_traits<allocator_type>::propagate_on_container_swap::value
is true within the implementation of the corresponding container operation. In all container types defined in this Clause, the member get_allocator() returns a copy of the allocator used to construct the container or, if that allocator has been replaced, a copy of the most recent replacement.
The expression a.swap(b), for containers a and b of a standard container type other than array and static_vector, shall exchange the values of a and b without invoking any move, copy, or swap operations on the individual container elements. Lvalues of any Compare, Pred, or Hash types belonging to a and b shall be swappable and shall be exchanged by calling swap as described in [swappable.requirements]. If allocator_traits<allocator_type>::propagate_on_container_swap::value is true, then lvalues of type allocator_type shall be swappable and the allocators of a and b shall also be exchanged by calling swap as described in [swappable.requirements]. Otherwise, the allocators shall not be swapped, and the behavior is undefined unless a.get_allocator() == b.get_allocator(). Every iterator referring to an element in one container before the swap shall refer to the same element in the other container after the swap. It is unspecified whether an iterator with value a.end() before the swap will have value b.end() after the swap.

[container.requirements.sequence.reqmts]

http://eel.is/c++draft/sequence.reqmts

sequence.reqmts.1: The library provides four basic kinds of sequence containers: vector, static_vector, forward_list, list, and deque.

sequence.reqmts.2: […] vector is the type of sequence container that should be used by default. static_vector should be used when the container has a fixed capacity known during translation. array should be used when the container has a fixed size known during translation.

[…]

The following operations are provided for some types of sequence containers but not others. An implementation shall implement them so as to take amortized constant time.

a.front()

Result: reference; const_reference for constant a.
Returns: *a.begin()
Remarks: Required for basic_string, array, deque, forward_list, list, static_vector, and vector.

a.back()

Result: reference; const_reference for constant a.

Effects: Equivalent to:

auto tmp = a.end();
--tmp;
return *tmp;

Remarks: Required for basic_string, array, deque, list, static_vector, and vector.

a.emplace_front(args)

Result: reference
Preconditions: T is Cpp17EmplaceConstructible into X from args.
Effects: Prepends an object of type T constructed with `std::forward<Args>(args)…``.
Returns: `a.front()``.
Remarks: Required for deque, forward_list, and list.

a.emplace_back(args)

Result: reference
Preconditions: T is Cpp17EmplaceConstructible into X from args. For vector and static_vector, T is also Cpp17MoveInsertable into X.
Effects: Appends an object of type T constructed with std::forward<Args>(args)....
Returns: `a.back()``.
Remarks: Required for deque, list, static_vector, and vector.

a.push_front(t)

Result: void
Preconditions: T is Cpp17CopyInsertable into X.
Effects: Prepends a copy of t.
Remarks: Required for deque, forward_list, and list.

a.push_front(rv)

Result: void
Preconditions: T is Cpp17MoveInsertable into X.
Effects: Prepends a copy of rv.
Remarks: Required for deque, forward_list, and list.

a.prepend_range(rg)

Result: void
Preconditions: T is Cpp17EmplaceConstructible into X from *ranges::begin(rg).
Effects: Inserts copies of elements in rg before begin(). Each iterator in the range rg is dereferenced exactly once. [Note 3: The order of elements in rg is not reversed. — end note]
Remarks: Required for deque, forward_list, and list.

a.push_back(t)

Result: void
Preconditions: T is Cpp17CopyInsertable into X.
Effects: Appends a copy of t.
Remarks: Required for basic_string, deque, list, static_vector, and vector.

a.push_back(rv)

Result: void
Preconditions: T is Cpp17MoveInsertable into X.
Effects: Appends a copy of rv.
Remarks: Required for basic_string, deque, list, static_vector, and vector.

a.append_range(rg)

Result: void
Preconditions: T is Cpp17EmplaceConstructible into X from *ranges::begin(rg). For vector and static_vector, T is also Cpp17MoveInsertable into X.
Effects: Inserts copies of elements in rg before end(). Each iterator in the range rg is dereferenced exactly once.
Remarks: Required for deque, list,static_vector, and vector.

a.pop_front()

Result: void
Preconditions: a.empty() is false.
Effects: Destroys the first element.
Remarks: Required for deque, forward_list, and list.

a.pop_back()

Result: void
Preconditions: a.empty() is false.
Effects: Destroys the last element.
Remarks: Required for basic_string, deque, list,static_vector, and vector.

a[n]

Result: reference; const_reference for constant a
Returns: *(a.begin() + n)
Remarks: Required for basic_string, array, deque, static_vector, and vector.

a.at(n)

Result: reference; const_reference for constant a
Returns: *(a.begin() + n)
Throws: out_of_range if n >= a.size().
Remarks: Required for basic_string, array, deque, static_vector, and vector.

[containers.sequences.static_vector.syn] Header `<static_vector>` synopsis

namespace std {

template <typename T, size_t N>
class static_vector {
public:
// types:
using value_type = T;
using pointer = T*;
using const_pointer = const T*; 
using reference = value_type&;
using const_reference = const value_type&;
using size_type =  size_t;
using difference_type = ptrdiff_t;
using iterator = implementation-defined;  // see [container.requirements]
using const_iterator = implementation-defined; // see [container.requirements]
using reverse_iterator = std::reverse_iterator<iterator>;
using const_reverse_iterator = std::reverse_iterator<const_iterator>;

// [containers.sequences.static_vector.cons]
constexpr static_vector() noexcept;
constexpr static_vector(const static_vector&);
constexpr static_vector(static_vector&&);
constexpr explicit static_vector(size_type n);
constexpr static_vector(size_type n, const value_type& value);
template <class InputIterator>
constexpr static_vector(InputIterator first, InputIterator last);
constexpr static_vector(initializer_list<value_type> il);

// [containers.sequences.static_vector.cons]
constexpr static_vector& operator=(const static_vector& other)
  noexcept(is_nothrow_copy_assignable_v<value_type>);
constexpr static_vector& operator=(static_vector&& other);
  noexcept(is_nothrow_move_assignable_v<value_type>);
template <class InputIterator>
constexpr void assign(InputIterator first, InputIterator last);
constexpr void assign(size_type n, const value_type& u);
constexpr void assign(initializer_list<value_type> il);

// [containers.sequences.static_vector.destructor]
~static_vector();

// iterators
constexpr iterator               begin()         noexcept;
constexpr const_iterator         begin()   const noexcept;
constexpr iterator               end()           noexcept;
constexpr const_iterator         end()     const noexcept;
constexpr reverse_iterator       rbegin()        noexcept;
constexpr const_reverse_iterator rbegin()  const noexcept;
constexpr reverse_iterator       rend()          noexcept;
constexpr const_reverse_iterator rend()    const noexcept;
constexpr const_iterator         cbegin()  const noexcept;
constexpr const_iterator         cend()    const noexcept;
constexpr const_reverse_iterator crbegin() const noexcept;
constexpr const_reverse_iterator crend()   const noexcept;

// [containers.sequences.static_vector.members] size/capacity
constexpr bool empty() const noexcept;
constexpr size_type size() const noexcept;
static constexpr size_type max_size() noexcept;
static constexpr size_type capacity() noexcept;
constexpr void resize(size_type sz);
constexpr void resize(size_type sz, const value_type& c);

// [containers.sequences.static_vector.members] element and data access:
constexpr reference       operator[](size_type n); 
constexpr const_reference operator[](size_type n) const;
constexpr reference       front();
constexpr const_reference front() const;
constexpr reference       back();
constexpr const_reference back() const;
constexpr       T* data()       noexcept;
constexpr const T* data() const noexcept;

// 5.7, modifiers:
constexpr iterator insert(const_iterator position, const value_type& x);
constexpr iterator insert(const_iterator position, value_type&& x);
constexpr iterator insert(const_iterator position, size_type n, const value_type& x);
template <class InputIterator>
  constexpr iterator insert(const_iterator position, InputIterator first, InputIterator last);
constexpr iterator insert(const_iterator position, initializer_list<value_type> il);

template <class... Args>
  constexpr iterator emplace(const_iterator position, Args&&... args);
template <class... Args>
  constexpr reference emplace_back(Args&&... args);
constexpr void push_back(const value_type& x);
constexpr void push_back(value_type&& x);

constexpr void pop_back();
constexpr iterator erase(const_iterator position);
constexpr iterator erase(const_iterator first, const_iterator last);

constexpr void clear() noexcept;

constexpr void swap(static_vector& x)
  noexcept(is_nothrow_swappable_v<value_type> &&
           is_nothrow_move_constructible_v<value_type>);
};

template <typename T, size_t N>
constexpr bool operator==(const static_vector<T, N>& a, const static_vector<T, N>& b);
template <typename T, size_t N>
constexpr bool operator!=(const static_vector<T, N>& a, const static_vector<T, N>& b);
template <typename T, size_t N>
constexpr bool operator<(const static_vector<T, N>& a, const static_vector<T, N>& b);
template <typename T, size_t N>
constexpr bool operator<=(const static_vector<T, N>& a, const static_vector<T, N>& b);
template <typename T, size_t N>
constexpr bool operator>(const static_vector<T, N>& a, const static_vector<T, N>& b);
template <typename T, size_t N>
constexpr bool operator>=(const static_vector<T, N>& a, const static_vector<T, N>& b);

// 5.8, specialized algorithms:
template <typename T, size_t N>
constexpr void swap(static_vector<T, N>& x, static_vector<T, N>& y)
  noexcept(noexcept(x.swap(y)));
  
}  // namespace std

[containers.sequences.static_vector] Class template `static_vector`

[containers.sequences.static_vector.overview] Overview`

A static_vector is a contiguous container that supports constant time insert and erase operations at the end; insert and erase in the middle take linear time. Its capacity is part of its type and its elements are stored within the static_vector object itself, meaning that that if v is a static_vector<T, N> then it obeys the identity &v[n] == &v[0] + n for all 0 <= n <= v.size().
A static_vector satisfies the container requirements
(\ref{container.requirements}) with the exception of the swap member function, whose complexity is linear instead of constant. It satisfies the sequence container requirements, including the optional sequence container requirements (\ref{sequence.reqmts}), with the exception of the push_front, pop_front, and emplace_front member functions, which are not provided. It satisfies the reversible container ([container.requirements]) and contiguous container ([container.requirements.general]) requirements. Descriptions are provided here only for operations on static_vector that are not described in one of these tables or for operations where there is additional semantic information.
Class static_vector relies on the implicitly-declared special member functions [class.default.ctor], [class.dtor], and [class.copy.ctor] to conform to the container requirements table in [container.requirements]. In addition to the requirements specified in the container requirements table, the move constructor and move assignment operator for array require that T be Cpp17MoveConstructible or Cpp17MoveAssignable, respectively.

[containers.sequences.static_vector.cons] Constructors, copy, and assignment

constexpr static_vector() noexcept;

Effects: Constructs an empty static_vector.
Ensures: empty().
Complexity: Constant.

constexpr static_vector(static_vector&& rv);

Effects: Constructs a static_vector by move-inserting the elements of rv.
Mandates: std::is_move_constructivle<value_type>.
Ensures: The static_vector is equal to the value that rv had before this construction.
Complexity: Linear in rv.size().

constexpr explicit static_vector(size_type n);

Effects: Constructs a static_vector with n default-inserted elements.
Mandates: std::is_default_constructible<value_type>.
Expects: n <= capacity().
Complexity: Linear in n.

constexpr static_vector(size_type n, const value_type& value);

Effects: Constructs a static_vector with n copies of value.
Mandates: std::is_copy_constructible<value_type>
Expects: n <= capacity().
Complexity: Linear in n.

template <class InputIterator>
constexpr static_vector(InputIterator first, InputIterator last);

Effects: Constructs a static_vector equal to the range [first, last)
Mandates: std::is_constructible<value_type, decltype(*first)>
Expects: distance(first, last) <= capacity()
Complexity: Linear in distance(first, last).

[containers.sequences.static_vector.destructor] Destruction

~static_vector();

Effects: Destroys the static_vector and its elements.
Remarks: This destructor is trivial if the destructor of value_type is trivial.

[containers.sequences.static_vector.capacity] Size and capacity

static constexpr size_type capacity() noexcept
static constexpr size_type max_size() noexcept

Returns: N.

constexpr void resize(size_type sz);

Effects: If sz < size(), erases the last size() - sz elements from the sequence. Otherwise, appends sz - size() default-constructed elements.
Mandates: std::is_default_constructible<value_type>.
Expects: sz <= capacity().
Complexity: Linear in sz.

constexpr void resize(size_type sz, const value_type& c);

Effects: If sz < size(), erases the last size() - sz elements from the sequence. Otherwise, appends sz - size() copies of c.
Mandates: std::is_copy_constructible<value_type>.
Expects: sz <= capacity().
Complexity: Linear in sz.

[containers.sequences.static_vector.data]

Element and data access

constexpr       T* data()       noexcept;
constexpr const T* data() const noexcept;

Returns: A pointer such that [data(), data() + size()) is a valid range. For a non-empty static_vector, data() == addressof(front()).
Complexity: Constant time.

[containers.sequences.static_vector.modifiers]

Modifiers

Note to LWG: All modifiers have a pre-condition on not exceeding the
capacity() when inserting elements. That is, exceeding the capacity() of the vector is undefined behavior. This supports some of the major use cases of this container (embedded, freestanding, etc.) and was required by the stakeholders during LEWG review. Currently, this provides maximum freedom to the implementation to choose an appropriate behavior: abort, assert, throw an exception (which exception? bad_alloc? logic_error? out_of_bounds? etc.). In the future, this freedom allows us to specify these pre-conditions using contracts.

Note to LWG: Because all modifiers have preconditions, they all have narrow contracts and are not unconditionally noexcept.

constexpr iterator insert(const_iterator position, const value_type& x);

Effects: Inserts x at position and invalidates all references to elements after position.
Expects: size() < capacity().
Mandates: std::is_copy_constructible<value_type>.
Complexity: Linear in size().
Remarks: If an exception is thrown by value_type’s copy constructor and is_nothrow_move_constructible_v<value_type> is true there are no effects. Otherwise, if an exception is thrown by value_type’s copy constructor the effects are unspecified.

constexpr iterator insert(const_iterator position, size_type n, const value_type& x);

Effects: Inserts n copies of x at position and invalidates all references to elements after position.
Expects: n <= capacity() - size().
Mandates: std::is_copy_constructible<value_type>.
Complexity: Linear in size() and n.
Remarks: If an exception is thrown by value_type’s copy constructor and is_nothrow_move_constructible_v<value_type> is true there are no effects. Otherwise, if an exception is thrown by value_type’s copy constructor the effects are unspecified.

constexpr iterator insert(const_iterator position, value_type&& x);

Effects: Inserts x at position and invalidates all references to elements after position.
Expects: size() < capacity().
Mandates: std::is_move_constructible<value_type>.
Complexity: Linear in size().
Remarks: If an exception is thrown by value_type’s move constructor the effects are unspecified.

template <typename InputIterator>
constexpr iterator insert(const_iterator position, InputIterator first, InputIterator last);

Effects: Inserts elements in range [first, last) at position and invalidates all references to elements after position.
Expects: distance(first, last) <= capacity() - size().
Mandates: std::is_constructible<value_type, decltype(*first)>.
Complexity: Linear in size() and distance(first, last).
Remarks: If an exception is thrown by value_type constructor from decltype(*first) and is_nothrow_move_constructible_v<value_type> is true there are no effects. Otherwise, if an exception is thrown by value_type’s constructor from decltype(*first) the effects are unspecified.

constexpr iterator insert(const_iterator position, initializer_list<value_type> il);

Effects: Inserts elements of il at position and invalidates all references to elements after position.
Expects: il.size() <= capacity() - size().
Mandates: std::is_copy_constructible<value_type>.
Complexity: Linear in size() and il.size().
Remarks: If an exception is thrown by value_type’s copy constructor and is_nothrow_move_constructible_v<value_type> is true there are no effects. Otherwise, if an exception is thrown by value_type’s copy constructor the effects are unspecified.

template <class... Args>
constexpr iterator emplace(const_iterator position, Args&&... args);

Effects: Inserts an element constructed from args... at position and invalidates all references to elements after position.
Expects: size() < capacity().
Mandates: std::is_constructible<value_type, Args...>.
Complexity: Linear in size().
Remarks: If an exception is thrown by value_type’s constructor from args... and is_nothrow_move_constructible_v<value_type> is true there are no effects. Otherwise, if an exception is thrown by value_type’s constructor from args... the effects are unspecified.

template <class... Args>
constexpr reference emplace_back(Args&&... args);

Effects: Inserts an element constructed from args... at the end.
Expects: size() < capacity().
Mandates: std::is_constructible<value_type, Args...>.
Complexity: Constant.
Remarks: If an exception is thrown by value_type’s constructor from args... there are no effects.

constexpr void push_back(const value_type& x);

Effects: Inserts a copy of x at the end.
Expects: size() < capacity().
Mandates: std::is_copy_constructible<value_type>.
Complexity: Constant.
Remarks: If an exception is thrown by value_type’s copy constructor there are no effects.

constexpr void push_back(value_type&& x);

Effects: Moves x to the end.
Expects: size() < capacity().
Mandates: std::is_move_constructible<value_type>.
Complexity: Constant.
Remarks: If an exception is thrown by value_type’s move constructor there are no effects.

constexpr void pop_back();

Effects: Removes the last element of the container and destroys it.
Expects: !empty().
Complexity: Constant.

[containers.sequences.static_vector.erasure] Erasure

constexpr iterator erase(const_iterator position);

Effects: Removes the element at position, destroys it, and invalidates references to elements after position.
Expects: position in range [begin(), end()).
Complexity: Linear in size().
Remarks: If an exception is thrown by value_type’s move constructor the effects are unspecified.

constexpr iterator erase(const_iterator first, const_iterator last);

Effects: Removes the elements in range [first, last), destroying them, and invalidating references to elements after last.
Expects: [first, last) in range [begin(), end()).
Complexity: Linear in size() and distance(first, last).
Remarks: If an exception is thrown by value_type’s move constructor the effects are unspecified.

constexpr void swap(static_vector& x)
  noexcept(is_nothrow_swappable_v<value_type> &&
           is_nothrow_move_constructible_v<value_type>);

Effects: Exchanges the contents of *this with x. All references to the elements of *this and x are invalidated.
Complexity: Linear in size() and x.size().
Remarks: Shall not participate in overload resolution unless is_move_constructible_v<value_type> is true and is_swappable_v<value_type> is true

[containers.sequences.static_vector.special] Specialized algorithms

template <typename T, size_t N>
constexpr void swap(static_vector<T, N>& x, 
                    static_vector<T, N>& y)
  noexcept(noexcept(x.swap(y)));

Constraints: This function shall not participate in overload resolution unless is_swappable_v<T> is true.
Effects: As if by x.swap(y).
Complexity: Linear in size() and x.size().

Acknowledgments

This proposal is based on Boost.Container’s boost::container::static_vector, mainly authored by Adam Wulkiewicz, Andrew Hundt, and Ion Gaztanaga. The reference implementation is based on Howard Hinnant std::vector implementation in libc++ and its test-suite. The following people provided valuable feedback that influenced some aspects of this proposal: Walter Brown, Zach Laine, Rein
Halbersma, and Andrzej Krzemieński. I want to wholeheartedly acknowledge Casey Carter for taking the time to do a very detailed analysis of the whole proposal, which was invaluable and reshaped it in fundamental ways.

static_vector