inplace_vector

A dynamically-resizable vector with fixed capacity and embedded storage

Document number: P0843R7.
Date: 2023-06-16.
Authors: Gonzalo Brito Gadeschi, Timur Doumler, Nevin Liber, David Sankel <dsankel _at_ adobe.com>.
Reply to: Timur Doumler <papers _at_ timur.audio>.
Audience: LEWG.

Table of Contents

Changelog

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 inplace_vector container is useful when:

Existing practice

There are at least 3 widely used implementations of inplace_vector: Boost.Container [1], EASTL [2], and Folly [3]. Boost.Container implements inplace_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 inplace_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

Standalone or a special case another type?

The EASTL [2] and Folly [3] special case small_vector, e.g., using a 4th template parameter, to make it become a inplace_vector. P0639R0: Changing attack vector of the constexpr_vector [7] proposes improving the Allocator concepts to allow implementing inplace_vector as a special case of vector with a custom allocator. Both approaches produce specializations of small_vector or 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 inplace_vector as a standalone type.

Where possible, this proposal defines the semantics of inplace_vector to match 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 without accidentally introducing undefined behavior.

Layout

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

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

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

The layout differs from vector, since inplace_vector does not store the capacity field (it’s known from the template parameter).

If T is trivially-copyable or N == 0, then inplace_vector<T, N> is also trivially copyable to support HPC (such as copying one between a CPU and a GPU), serialization/deserialization, which is important for use cases like sending a vector via MPI_Send, etc.

// for all C:
static_assert(!is_trivially_copyable_v<T> || is_trivially_copyable_v<inplace_vector<T, C>> || N == 0);

Move semantics

A moved-from inplace_vector is left in a valid but unspecified state (option 3 below) unless T is trivially-copyable, in which case the size of the inplace_vector does not change (array semantics, option 2 below). That is:

inplace_vector a(10); inplace_vector b(std::move(a)); assert(a.size() == 10); // MAY FAIL

moves a’s elements element-wise into b, and afterwards the size of the moved-from inplace_vector may have changed.

This prevents code from relying on the size staying the same (and therefore being incompatible with changing an inplace_vector type back to vector) without incuring the cost of having to clear the inplace_vector.

When T is trivially-copyable, array semantics are used to provide trivial move operations.

This is different from LEWG Kona '22 Polls (22 in person + 8 remote) and we’d like to poll on these semantics again:

Alternatives:

  1. vector semantics: guarantees that inplace_vector is left empty (this happens with move assignment when using std::allocator<T> and always with move construction).
    • Pro: same programming model as vector.
    • Pro: increases safety by requiring users to re-initialize vector elements.
    • Con: clearing an inplace_vector is not free.
    • Con: inplace_vector<T, N> can no longer be made trivially copyable for a trivially copyable T, as the move operations can no longer be trivial.
  2. array semantics: guarantees that size() of inplace_vector does not change, and that elements are left in their moved-from state.
    • Pro: no additional run-time cost incurred.
    • Con: different programming model than vector.
  3. “valid but unspecified state”
    • Con: different programming model than vector and array, requires calling size()
    • Pro: code calling size() is correct for both vector and inplace_vector, enabling changing the type back and forth.

constexpr support

The API of inplace_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 inplace_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 vector instead.

Exception Safety

When using the inplace_vector APIs, the following types of failures are expected:

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

For inplace_vector, we choose the same semantics as for vector:

  1. When value_type’s operations are invoked, inplace_vector exception-safety guarantees depend on whether these operations throw, which is detected with noexcept if the API has a narrow contract.
  2. Mutating operations that exceed the capacity ask “allocator embedded within the inplace_vector”, which has run out of space, for more memory, and therefore throw std::bad_alloc like vector APIs do (e.g. a pmr “stack allocator” throws std::bad_alloc as well). This preserves the programming model from vector. std::bad_alloc also has the property that it never does an allocation itself.
  3. Out-of-bounds unchecked access is a precondition violation.

Alternatives:

  1. Throw std::bad_alloc when the inplace_vector is out-of-memory:
    • Pros: same programming model as vector.
  2. Throw “some other exception” when the inplace_vector is out-of-memory:
    • Pros: to be determined.
    • Cons: different programming model as vector.
  3. Abort the process
    • Pros: portability to embedded platforms without exception support
    • Cons: different programming model than vector
  4. Precondition violation
    • Cons: different proramming model than vector, users responsible for checking before modifying vector size, etc.

Fallible APIs

We add the following new fallible APIs which, when the vector size equal its capacity, return nullptr (do not throw bad_alloc) without moving from the inputs, enabling them to be re-used:

constexpr T* inplace_vector<T, C>::try_push_back(const T& value);
constexpr T* inplace_vector<T, C>::try_push_back(T&& value);

template<class... Args>
constexpr T* try_emplace_back(Args&&... args);

They can be used as follows

T value = T(); if (!v.try_push_back(value)) { std::cerr << "Failed to insert " << value << std::endl; // value not moved-from std::terminate(); }

Fallible Unchecked APIs

We add the following new fallible unchecked APIs for which exceeding the capacity is a precondition violation:

constexpr T& inplace_vector<T, C>::push_back_unchecked(const T& value);
constexpr T& inplace_vector<T, C>::push_back_unchecked(T&& value);

template<class... Args>
constexpr T& emplace_back_unchecked(Args&&... args);

These APIs were requested in LEWG Kona '22 (22 in person + 8 remote):

The potential impact of the three APIs on code generation is shown here, where the main difference between try_push_back and push_back_unchecked is the presenece of an extra branch in try_push_back.

The authors have made several attempts at micro-benchmarking the performance difference between push_back_unchecked and try_push_back, and the results will be presented to LEWG.

Iterator invalidation

inplace_vector iterator invalidation guarantees differ from std::vector:

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

Freestanding

The inplace_vector APIs are all freestanding.

LWG asked for inplace_vector to be part of the <vector> header.

Request LEWG to poll on that.

Return type of push_back

In C++20, both push_back and emplace_back were slated to return a reference (they used to both return void). Even with plenary approval, changing push_back turned out to be an ABI break that was backed out, leaving the situation where emplace_back returns a reference but push_back is still void. This ABI issue doesn’t apply to new types. Should push_back return a reference to be consistent with emplace_back, or should it be consistent with older containers?

Request LEWG to poll on that.

Summary of semantic differences with vector

Aspect vector inplace_vector
Capacity Indefinite N
Move and swap O(1), no iterators invalidated array semantics: O(size), invalidates all iterators
Moved from left empty (this happens with move assignment when using std::allocator<T> and always with move construction) valid but unspecified state except if T is trivially-copyable, in which case array semantics
Default construction and destruction of trivial types O(1) O(capacity)
Is empty when zero capacity? No Yes
Trivially-copyable if is_trivially_copyable_v<T>? No Yes

Technical specification


Note to editor: This enhancement is a pure header-only addition to the C++ standard library as the freestanding <inplace_vector> header. It belongs in the “Sequence containers” (\ref{sequences}) part of the “Containers library” (\ref{containers}) as “Class template inplace_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 <inplace_vector> to [tab:headers.cpp].

[library.requirements.organization.compliance]

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

[container.reqmts] General container requirements

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

  1. 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
typename X::reference
typename X::const_reference
typename X::iterator
typename X::const_iterator
typename X::differcence_type
typename X::size_type
X u;
X u = X();
X u(a);
X u = a;
X u(rv);
X u = rv;
a = rv
a.~X()
a.begin()
a.end()
a.cbegin()
a.cend()
i <=> j
a == b
a != b
a.swap(b)
swap(a, b)
r = a
a.size()
a.max_size()
a.empty()
  1. 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

  1. allocator_­traits<allocator_­type>​::​propagate_­on_­container_­copy_­assignment​::​value,
  2. allocator_­traits<allocator_­type>​::​propagate_­on_­container_­move_­assignment​::​value, or
  3. 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.
  4. The expression a.swap(b), for containers a and b of a standard container type other than array and inplace_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 fourthe following basic kinds of sequence containers: vector, inplace_vector, forward_list, list, and deque.

sequence.reqmts.2: […] vector is the type of sequence container that should be used by default. inplace_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()
a.back()
a.emplace_front(args)
a.emplace_back(args)
a.push_front(t)
a.push_front(rv)
a.prepend_range(rg)
a.push_back(t)
a.push_back(rv)
a.append_range(rg)
a.pop_front()
a.pop_back()
a[n]
a.at(n)

[containers.sequences.inplace_vector.syn] Header <inplace_vector> synopsis

namespace std {

template <typename T, size_t N>
class inplace_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.inplace_vector.cons]
constexpr inplace_vector() noexcept;
constexpr inplace_vector(const inplace_vector&);
constexpr inplace_vector(inplace_vector&&)
noexcept(!N || is_nothrow_move_constructible_v<value_type>);
constexpr explicit inplace_vector(size_type n);
constexpr inplace_vector(size_type n, const value_type& value);
template <class InputIterator>
constexpr inplace_vector(InputIterator first, InputIterator last);
constexpr inplace_vector(initializer_list<value_type> il);

// [containers.sequences.inplace_vector.cons]
constexpr inplace_vector& operator=(const inplace_vector& other);
constexpr inplace_vector& operator=(inplace_vector&& other)
  noexcept(!N || 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.inplace_vector.destructor]
constexpr ~inplace_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.inplace_vector.members] size/capacity
[[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);

// [containers.sequences.inplace_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 T& push_back(const value_type& x);
constexpr T& 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(inplace_vector& x)
  noexcept(is_nothrow_swappable_v<value_type> &&
           is_nothrow_move_constructible_v<value_type>);
};

template<class InputIterator>
inplace_vector(InputIterator, InputIterator)
-> inplace_vector<iter-value-type<InputIterator>>;

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

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

}  // namespace std

[containers.sequences.inplace_vector] Class template inplace_vector

[containers.sequences.inplace_vector.overview] Overview`

  1. A inplace_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 inplace_vector object itself, meaning that that if v is a inplace_vector<T, N> then it obeys the identity &v[n] == &v[0] + n for all 0 <= n <= v.size().
  2. A inplace_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 inplace_vector that are not described in one of these tables or for operations where there is additional semantic information.
  3. Class inplace_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.
  4. The types iterator and const_iterator meet the constexpr iterator
    requirements ([iterator.requirements.general])."

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


constexpr inplace_vector() noexcept;

constexpr inplace_vector(inplace_vector&& rv);

constexpr explicit inplace_vector(size_type n);

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

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

[containers.sequences.inplace_vector.destructor] Destruction

constexpr ~inplace_vector();

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

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

constexpr void resize(size_type sz);

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

[containers.sequences.inplace_vector.data]

Element and data access

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

[containers.sequences.inplace_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);

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

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

template <typename 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 reference push_back(const value_type& x);

constexpr reference push_back(value_type&& x);

constexpr void pop_back();

[containers.sequences.inplace_vector.erasure] Erasure

constexpr iterator erase(const_iterator position);

constexpr iterator erase(const_iterator first, const_iterator last);

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

[containers.sequences.inplace_vector.special] Specialized algorithms

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

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, Andrzej Krzemieński, Casey Carter and many others.