`static_vector`

A dynamically-resizable vector with fixed capacity and embedded storage

**Document number**: P0843r6.

**Date**: 2023-05-18.

**Authors**: Gonzalo Brito Gadeschi, Timur Doumler.

**Reply to**: Timur Doumler <papers _at_ timur.audio>.

**Audience**: LEWG.

Table of Contents

**Changelog**

**Revision 6**: for Varna 2023 following Kona’s 2022 guidance
- Updated push_back semantics to follow std::vector (note about exception to throw).
- Added
`try_push_back`

returning an `optional`

- Added
`push_back_unchecked`

: excedding capacity exhibits undefined behavior.
- Added note about naming.

**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_type`

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

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>>);
```

The offset of the first element within `static_vector`

is unspecified, and `T`

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

.
- Note: this API may need to throw an exception other than
`std::bad_alloc`

since it is reserved to be thrown from allocation functions. An alternative may be `std::length_error`

since we provide a `max_size`

that matches `Capacity`

.

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

We add the following new allocation APIs following Kona guidance:

```
constexpr void static_vector<T, C>::push_back_unchecked(const T& value);
constexpr void static_vector<T, C>::push_back_unchecked(T&& value);
```

- Exceeding the capacity is a precondition violation.

```
constexpr optional<T> static_vector<T, C>::try_push_back(const T& value);
constexpr optional<T> static_vector<T, C>::try_push_back(T&& value);
```

- If the element is inserted into the vector, they return
`nullopt`

. Otherwise, they return an `optional`

containing the value passed in.

## Iterator invalidation

`static_vector`

iterator invalidation guarantees differ from `std::vector`

:

- moving a
`static_vector`

invalidates all iterators, and
- swapping two
`static_vector`

s invalidates all iterators.

`static_vector`

APIs that potentially invalidate iterators are: `resize(n)`

, `resize(n, v)`

, `pop_back`

, `erase`

, and `swap`

.

# Naming

`static_vector`

is not a very good name because the name is overloaded. We prefer to switch to the name `inplace_vector`

instead.

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

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

```
typename X::const_reference
```

```
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~~the following 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()
```

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

.

```
namespace std {
template <typename T, size_t N>
class static_vector {
public:
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;
using const_iterator = implementation-defined;
using reverse_iterator = std::reverse_iterator<iterator>;
using const_reverse_iterator = std::reverse_iterator<const_iterator>;
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);
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);
constexpr ~static_vector();
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;
[[nodiscard]] 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);
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;
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<class InputIterator>
static_vector(InputIterator, InputIterator)
-> static_vector<iter-value-type<InputIterator>>;
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);
template <typename T, size_t N>
constexpr void swap(static_vector<T, N>& x, static_vector<T, N>& y)
noexcept(noexcept(x.swap(y)));
}
```

- 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.
- The types iterator and const_iterator meet the constexpr iterator

requirements ([iterator.requirements.general])."

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

```
constexpr static_vector() noexcept;
```

*Effects*: Constructs an empty `static_vector`

.
*Postconditions*: `empty()`

is true.
*Complexity*: Constant.

```
constexpr static_vector(static_vector&& rv);
```

*Effects*: Constructs a `static_vector`

by move-inserting the elements of `rv`

.
*Mandates*: `is_move_constructible_v<value_type>`

is true.
*Postconditions*: 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*: `is_default_constructible_v<value_type>`

is true.
*Preconditions*: `n <= capacity()`

is true.
*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*: `is_copy_constructible_v<value_type>`

is true.
*Preconditions*: `n <= capacity()`

is true.
*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*: `is_constructible_v<value_type, decltype(*first)>`

is true.
*Preconditions*: `distance(first, last) <= capacity()`

is true.
*Complexity*: Linear in `distance(first, last)`

.

```
constexpr ~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
```

```
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*: `is_default_constructible_v<value_type>`

is true.
*Preconditions*: `sz <= capacity()`

is true.
*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*: `is_copy_constructible_v<value_type>`

is true.
*Preconditions*: `sz <= capacity()`

is true.
*Complexity*: Linear in `sz`

.

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.

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`

? `std::length_error`

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

.
*Preconditions*: `size() < capacity()`

is true.
*Mandates*: `is_copy_constructible_v<value_type>`

is true.
*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`

.
*Preconditions*: `n <= capacity() - size()`

is true.
*Mandates*: `is_copy_constructible_v<value_type>`

is true.
*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`

.
*Preconditions*: `size() < capacity()`

is true.
*Mandates*: `is_move_constructible_v<value_type>`

is true.
*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`

.
*Preconditions*: `distance(first, last) <= capacity() - size()`

is true.
*Mandates*: `is_constructible_v<value_type, decltype(*first)>`

is true.
*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`

.
*Preconditions*: `il.size() <= capacity() - size()`

is true.
*Mandates*: `is_copy_constructible_v<value_type>`

is true.
*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`

.
*Preconditions*: `size() < capacity()`

is true.
*Mandates*: `is_constructible_v<value_type, Args...>`

is true.
*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.
*Preconditions*: `size() < capacity()`

is true.
*Mandates*: `is_constructible_v<value_type, Args...>`

is true.
*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.
*Preconditions*: `size() < capacity()`

is true.
*Mandates*: `is_copy_constructible_v<value_type>`

is true.
*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.
*Preconditions*: `size() < capacity()`

is true.
*Mandates*: `is_move_constructible_v<value_type>`

is true.
*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.
*Preconditions*: `!empty()`

is true.
*Complexity*: Constant.

```
constexpr iterator erase(const_iterator position);
```

*Effects*: Removes the element at `position`

, destroys it, and invalidates references to elements after `position`

.
*Preconditions*: `position`

in range `[begin(), end())`

is true.
*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`

.
*Preconditions*: `[first, last)`

in range `[begin(), end())`

is true.
*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`

.

```
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()`

.

### TODOS:

- Add a specialization of hash like for
`std::vector`

.
- Update
`operator!=`

to `operator<=>`

using hidden friends for them.
- Add deduction guides (there is only one, do we need more).

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

# References

`static_vector`

Document number: P0843r6.Date: 2023-05-18.Authors: Gonzalo Brito Gadeschi, Timur Doumler.Reply to: Timur Doumler <papers _at_ timur.audio>.Audience: LEWG.Table of Contents

ChangelogRevision 6: for Varna 2023 following Kona’s 2022 guidance`try_push_back`

returning an`optional`

`push_back_unchecked`

: excedding capacity exhibits undefined behavior.Revision 5:Revision 4:Revision 3:Revision 2`fixed_capacity_vector`

with`static_vector`

Revision 1Unresolved questions`<static_vector>`

as afree-standingheader. LWG suggests that`static_vector`

should be included in`<vector>`

instead.`vector`

programming model. Proposal has been extended and adapted.`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_type`

s, the vector is fully usable inside`constexpr`

functions.## Motivation and Scope

The

`static_vector`

container is useful when:static-memory segment is required,`std::array`

is not an option, e.g., if non-default constructible objects must be stored,`constexpr`

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

`contiguous_container`

proposal [5]: proposes a`Storage`

concept.`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[7] proposes improving the`constexpr_vector`

`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:The offset of the first element within

`static_vector`

is unspecified, and`T`

s 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:moves

`a`

’s elements element-wise into`b`

. The`static_vector`

is left in a valid but unspecified state.Design Optionsfor 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.`vector`

`std::vector`

semantics: guarantees that`static_vector`

is left in a valid but unspecified state.`vector`

`size()`

before re-using element storage, just like for`vector`

.`static_vector`

by resizing it:`vector`

`constexpr`

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

),`push_back`

,`insert`

,`emplace`

,`static_vector(value_type, size)`

,`static_vector(begin, end)`

…), and`front`

/`back`

/`pop_back`

when empty,`operator[]`

.We choose the same semantics as for

`vector`

`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.`static_vector`

to run out of space, and therefore throw`std::bad_alloc`

like`vector`

APIs do. This preserves the programming model from`vector`

.`std::bad_alloc`

since it is reserved to be thrown from allocation functions. An alternative may be`std::length_error`

since we provide a`max_size`

that matches`Capacity`

.Design Optionsfor exception safety semantics of`static_vector`

mutating operations:Pros: same as`std::vector`

if throws`bad_alloc`

.Pros: portability to embedded platforms without exception supportCons: different programming model than`vector`

Cons: different proramming model than`vector`

, users responsible for checking before modifying vector size, etc.We add the following new allocation APIs following Kona guidance:

`nullopt`

. Otherwise, they return an`optional`

containing the value passed in.## Iterator invalidation

`static_vector`

iterator invalidation guarantees differ from`std::vector`

:`static_vector`

invalidates all iterators, and`static_vector`

s invalidates all iterators.`static_vector`

APIs that potentially invalidate iterators are:`resize(n)`

,`resize(n, v)`

,`pop_back`

,`erase`

, and`swap`

.## Naming

`static_vector`

is not a very good name because the name is overloaded. We prefer to switch to the name`inplace_vector`

instead.## 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`

”.## [library.requirements.organization.headers]

Add

`<static_vector>`

to [tab:headers.cpp].## [library.requirements.organization.compliance]

Add

`<static_vector>`

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

## [container.reqmts] General container requirements

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

`X`

meets the container requirements if the following types, statements, and expressions are well-formed and have the specified semantics.`T`

`T`

is`Cpp17Erasable`

from`X`

(see [container.alloc.reqmts], below).`T&`

`const T&`

`T`

. The type`X::iterator`

is convertible to`X::const_iterator`

.`T`

.`X::iterator`

and`X::const_iterator`

.`X::difference_type`

.`u.empty()`

`T`

is`Cpp17CopyInsertable`

into`X`

(see below).`u == a`

`u`

is equal to the value that`rv`

had before this construction.`static_vector`

and constant for all other standard containers.`X&`

.`a`

are either move assigned to or destroyed.`a`

and`rv`

do not refer to the same object,`a`

is equal to the value that`rv`

had before this assignment.`void`

`a`

; any memory obtained is deallocated.`iterator`

;`const_iterator`

for constant`a`

.`iterator`

;`const_iterator`

for constant`a`

.`const_iterator`

.`const_cast<X const&>(a).begin()`

`const_iterator`

.`const_cast<X const&>(a).end()`

`strong_ordering`

.`X::iterator`

meets the random access iterator requirements.`T`

meets the`Cpp17EqualityComparable`

requirements.`bool`

.`equal(a.begin(), a.end(), b.begin(), b.end())`

[Note 1: The algorithm`equal`

is defined in [alg.equal]. — end note]`a.size() != b.size()`

, linear otherwise.`==`

is an equivalence relation.`!(a == b)`

.`void`

`a`

and`b`

.`static_vector`

, and constant for all other standard containers.`a.swap(b)`

.`X&`

.`r == a`

.`size_type`

.`distance(a.begin(), a.end())`

, i.e. the number of elements in the container.`size_type`

.`distance(begin(), end())`

for the largest possible container.`bool`

.`a.begin() == a.end()`

`a.empty()`

is true.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.`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~~the following 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.

`reference`

;`const_reference`

for constant`a`

.`*a.begin()`

`basic_string`

,`array`

,`deque`

,`forward_list`

,`list`

,`static_vector`

, and vector.`reference`

;`const_reference`

for constant`a`

.`basic_string`

,`array`

,`deque`

,`list`

,`static_vector`

, and vector.`reference`

`T`

is`Cpp17EmplaceConstructible`

into`X`

from`args`

.`T`

constructed with `std::forward<Args>(args)…``.`deque`

,`forward_list`

, and`list`

.`T`

is`Cpp17EmplaceConstructible`

into`X`

from`args`

. For`vector`

and`static_vector`

,`T`

is also`Cpp17MoveInsertable`

into`X`

.`T`

constructed with`std::forward<Args>(args)...`

.`deque`

,`list`

,`static_vector`

, and vector.`void`

`T`

is`Cpp17CopyInsertable`

into`X`

.`t`

.`deque`

,`forward_list`

, and`list`

.`void`

`T`

is`Cpp17MoveInsertable`

into`X`

.`rv`

.`deque`

,`forward_list`

, and`list`

.`void`

`T`

is`Cpp17EmplaceConstructible`

into`X`

from`*ranges::begin(rg)`

.`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]`deque`

,`forward_list`

, and`list`

.`void`

`T`

is`Cpp17CopyInsertable`

into`X`

.`t`

.`basic_string`

,`deque`

,`list`

,`static_vector`

, and vector.`void`

`T`

is`Cpp17MoveInsertable`

into`X`

.`rv`

.`basic_string`

,`deque`

,`list`

,`static_vector`

, and vector.`void`

`T`

is`Cpp17EmplaceConstructible`

into`X`

from`*ranges::begin(rg)`

. For`vector`

and`static_vector`

,`T`

is also`Cpp17MoveInsertable`

into`X`

.`rg`

before`end()`

. Each iterator in the range`rg`

is dereferenced exactly once.`deque`

,`list`

,`static_vector`

, and vector.`void`

`a.empty()`

is`false`

.`deque`

,`forward_list`

, and`list`

.`void`

`a.empty()`

is`false`

.`basic_string`

,`deque`

,`list`

,`static_vector`

, and vector.`reference`

;`const_reference`

for constant`a`

`*(a.begin() + n)`

`basic_string`

,`array`

,`deque`

,`static_vector`

, and vector.`reference`

;`const_reference`

for constant`a`

`*(a.begin() + n)`

`out_of_range`

if`n >= a.size()`

.`basic_string`

,`array`

,`deque`

,`static_vector`

, and`vector`

.## [containers.sequences.static_vector.syn] Header

`<static_vector>`

synopsis## [containers.sequences.static_vector] Class template

`static_vector`

## [containers.sequences.static_vector.overview] Overview`

`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()`

.`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.`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.requirements ([iterator.requirements.general])."

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

`constexpr static_vector() noexcept;`

Effects: Constructs an empty`static_vector`

.Postconditions:`empty()`

is true.Complexity: Constant.`constexpr static_vector(static_vector&& rv);`

Effects: Constructs a`static_vector`

by move-inserting the elements of`rv`

.Mandates:`is_move_constructible_v<value_type>`

is true.Postconditions: 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:`is_default_constructible_v<value_type>`

is true.Preconditions:`n <= capacity()`

is true.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:`is_copy_constructible_v<value_type>`

is true.Preconditions:`n <= capacity()`

is true.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:`is_constructible_v<value_type, decltype(*first)>`

is true.Preconditions:`distance(first, last) <= capacity()`

is true.Complexity: Linear in`distance(first, last)`

.## [containers.sequences.static_vector.destructor] Destruction

`constexpr ~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:`is_default_constructible_v<value_type>`

is true.Preconditions:`sz <= capacity()`

is true.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:`is_copy_constructible_v<value_type>`

is true.Preconditions:`sz <= capacity()`

is true.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`

?`std::length_error`

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

.Preconditions:`size() < capacity()`

is true.Mandates:`is_copy_constructible_v<value_type>`

is true.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 areunspecified.`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`

.Preconditions:`n <= capacity() - size()`

is true.Mandates:`is_copy_constructible_v<value_type>`

is true.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 areunspecified.`constexpr iterator insert(const_iterator position, value_type&& x);`

Effects: Inserts`x`

at`position`

and invalidates all references to elements after`position`

.Preconditions:`size() < capacity()`

is true.Mandates:`is_move_constructible_v<value_type>`

is true.Complexity: Linear in`size()`

.Remarks: If an exception is thrown by`value_type`

’s move constructor the effects areunspecified.`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`

.Preconditions:`distance(first, last) <= capacity() - size()`

is true.Mandates:`is_constructible_v<value_type, decltype(*first)>`

is true.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 areunspecified.`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`

.Preconditions:`il.size() <= capacity() - size()`

is true.Mandates:`is_copy_constructible_v<value_type>`

is true.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 areunspecified.`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`

.Preconditions:`size() < capacity()`

is true.Mandates:`is_constructible_v<value_type, Args...>`

is true.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 areunspecified.`template <class... Args> constexpr reference emplace_back(Args&&... args);`

Effects: Inserts an element constructed from`args...`

at the end.Preconditions:`size() < capacity()`

is true.Mandates:`is_constructible_v<value_type, Args...>`

is true.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.Preconditions:`size() < capacity()`

is true.Mandates:`is_copy_constructible_v<value_type>`

is true.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.Preconditions:`size() < capacity()`

is true.Mandates:`is_move_constructible_v<value_type>`

is true.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.Preconditions:`!empty()`

is true.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`

.Preconditions:`position`

in range`[begin(), end())`

is true.Complexity: Linear in`size()`

.Remarks: If an exception is thrown by`value_type`

’s move constructor the effects areunspecified.`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`

.Preconditions:`[first, last)`

in range`[begin(), end())`

is true.Complexity: Linear in`size()`

and`distance(first, last)`

.Remarks: If an exception is thrown by`value_type`

’s move constructor the effects areunspecified.`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()`

.## TODOS:

`std::vector`

.`operator!=`

to`operator<=>`

using hidden friends for them.## 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, ReinHalbersma, 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.

## References

`contiguous_container`

proposal: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0494r0.pdf`std::constexpr_vector<T>`

: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0597r0.html`constexpr_vector`

: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0639r0.html .