inplace_vector

A dynamically-resizable vector with fixed capacity and embedded storage

Document number: P0843R12.
Date: 2024-05-20.
Authors: Gonzalo Brito Gadeschi, Timur Doumler <papers _at_ timur.audio>, Nevin Liber, David Sankel <dsankel _at_ adobe.com>.
Reply to: Gonzalo Brito Gadeschi <gonzalob _at_ nvidia.com>.
Audience: LWG.

Table of Contents

Changelog

Introduction

This paper proposes inplace_vector, a dynamically-resizable array with capacity fixed at compile time and contiguous inplace storage, that is, the array elements are stored within the vector object itself. Its API closely resembles std::vector<T, A>, making it easy to teach and learn, and the inplace storage guarantee makes it useful in environments in which dynamic memory allocations are undesired.

This container is widely-used in the standard practice of C++, with prior art in, e.g., boost::static_vector<T, Capacity> [1] or the EASTL [2], and therefore we believe it will be very useful to expose it as part of the C++ standard library, which will enable it to be used as a vocabulary type.

Motivation and Scope

The inplace_vector container is useful when:

Existing practice

Three widely used implementations of inplace_vector are available: 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 the following.

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

Design

The design described below was approved at LEWG Varna '23:

Strongly Favor Weakly Favor Neutral Weakly Against Strongly Against
9 7 0 0 0
Strongly Favor Weakly Favor Neutral Weakly Against Strongly Against
11 5 0 0 0

Standalone or a special case another type?

The EASTL [2] and Folly [3] special case small_vector, e.g., using a fourth template parameter, to make it become an 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 differ subtly 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 and use, and makes it easy to "just change" one type in 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 high-performance computing (HPC) use cases, such as the following.

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

Note: this revision brings back this section which was dropped in R8 because per LEWG discussion, LEWG thought that this whole type was implementable within constexpr for all types. The design intent of LEWG was to make it "as constexpr as possible."

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:

Exception Safety guarantees of Mutating Operations

When an inplace_vector API throws an exception,

The following alternative were considered:

  1. Same guarantees as their counter-part vector APIs.
  2. Always provide the Basic Guarantee independent on the concepts implemented by the iterators/ranges: always insert up to the capacity, then throw.
  3. Provide different exception safety guarantees depending on the concepts modeled by the iterators/ranges API arguments:
    • sized_range, random_access_iterator, or LegacyRandomAccessIterator: Strong guarantee, i.e., if the capacity would be exceeded, the API throws without attempting to insert any elements. This performs well and the caller looses no data.
    • Otherwise: Basic guarantee, i.e., elements are inserted up to the capacity, and are not removed before throwing. This performs well and the caller only looses data, e.g., stashed in discarded input iterators.

We propose to, unless stated otherwise, inplace_vector APIs should provide the same exception safety guarantees as their counter-part vector APIs.

Exception thrown by mutating operations exceeding capacity

We propose that mutating operations that exceed the capacity throw bad_alloc, to make it safer for applications handling out of memory errors to introduce inplace_vector as a performance optimization by replacing vector.

LEWG revisited the rationale below and decided to keep throwing bad_alloc in the 2024-01-30 telecon.

Alternatives:

  1. Throw bad_alloc: inplace_vector requests storage from "allocator embedded within the inplace_vector", which fails to allocate, and therefore throws bad_alloc (e.g. like vector and pmr "stack allocator").
    • Pros: handling bad_alloc is more common than other exceptions when attempting to handle failure to insert due to "out-of-memory".
  2. Throw length_error: insertion exceeds max_size and therefore throws length_error
    • Pros: container requirements already imply that this exception may be thrown.
    • Cons: handling length_error is rare since it is usually very high.
  3. Throw "some other exception" when the inplace_vector is out-of-memory:
    • Pros: to be determined.
    • Cons: different programming model as vector.
  4. Abort the process
    • Pros: portability to embedded platforms without exception support
    • Cons: different programming model than vector
  5. 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 (and 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);

template< container-compatible-range<T> R>
  constexpr ranges::iterator_t<R> try_append_range(R&& rg);

The try_append_range API always tries to insert all rg range elements up to either the vector capacity or the range rg is exhausted. It returns an iterator to the first non-inserted element of rg or the end iterator of rg if the range was exhausted. It intentionally provides the Basic Exception Safety guarantee, i.e., if inserting an element throws, previously succesfully inserted elements are preserved in the vector (i.e. not lost).

These APIs may 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();
}

auto il = {1, 2, 3};
if (v.try_append_range(il) != end(il)) {
    // The vector capacity was exhausted
    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>::unchecked_push_back(const T& value);
constexpr T& inplace_vector<T, C>::unchecked_push_back(T&& value);

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

The append_range API was requested during LWG review in December 2023.

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

This was confirmed at LEWG Varna '23 after a discussion on safety:

Strongly Favor Weakly Favor Neutral Weakly Against Strongly Against
1 5 3 3 7

The name unchecked_push_back was polled in LEWG Varna '23:

The potential impact of the three APIs on code size and performance is shown here, where the main difference between try_push_back and unchecked_push_back is the presence of an extra branch in try_push_back.

Allocator awareness

We believe that right now, making inplace_vector allocator-aware does not outweigh its complexity and design cost. We can always provide a way to support that in the future.

Options:

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

Manyinplace_vector APIs are not available in freestanding because fallible insertion APIs (constructors, push back, insert, …) may throw.

The infallible try_ APIs do not throw and are available in freestanding. They only cover a subset of the functionality available through fallible APIs. This is intentional. Adding more infallible APIs to inplace_vector and potentially other containers is left as future work.

We'd need to add it to: [library.requirements.organization.compliance]

When we fix this we'd need to add <inplace_vector> to [tab:headers.cpp.fs]:

Subclause Headers
[containers] containers <inplace_vector>

Same or Separate header

We propose that this container goes into its own header <inplace_vector> rather than in header <vector>, because it is a sufficiently different container.

LWG asked for inplace_vector to be part of the <vector> header. LEWG Varna '23 took the following poll:

That is, consensus against change.

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.

reserve and shrink_to_fit APIs

shrink_to_fit requests vector to decrease its capacity, but this request may be ignored. inplace_vector may implement it as a nop (and it may be noexcept).

reserve(n) requests the vector to potentially increase its capacity, failing if the request can't be satisfied. inplace_vector may implement it as a nop if n <= capacity(), throwing bad_alloc otherwise.

These APIs make it easier and safe for programs to be "more" parametric over "vector-like" containers (vector, small_vector, inplace_vector), but since they do not do anything useful for inplace_vector, we may want to fail to compile instead.

Deduction guides

Unlike the other containers, inplace_vector does not have any deduction guides because there is no case in which it would be possible to deduce the second template argument, the capacity, from the initializer.

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

Name

The class template name was confirmed at LEWG Varna '23:

Options Votes
static_vector 4
inplace_vector 14
fixed_capacity_vector 5

Technical specification

EDITORIAL: This enhancement is a pure header-only addition to the C++ standard library as the <inplace_vector> header. It belongs in the "Sequence containers" ([sequences]) part of the "Containers library" ([containers]) as "Class template inplace_vector".

[library.requirements.organization.headers]

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

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

Subclause Headers
[containers] containers <inplace_vector>

[iterator.range] Range access

Modify:

1 In addition to being available via inclusion of the <iterator> header, the function templates in [iterator.range] are available when any of the following headers are included: <array>, <deque>, <forward_list>, <inplace_vector>, <list>, <map>, <regex>, <set>, <span>, <string>, <string_view>, <unordered_map>, <unordered_set>, and <vector>.

[container.alloc.reqmts]

Modify:

1 All of the containers defined in [containers] and in [basic.string] except array and inplace_vector meet the additional requirements of an allocator-aware container, as described below.

[allocator.requirements.general]

1 The library describes a standard set of requirements for allocators, which are class-type objects that encapsulate the information about an allocation model. This information includes the knowledge of pointer types, the type of their difference, the type of the size of objects in this allocation model, as well as the memory allocation and deallocation primitives for it. All of the string types, containers (except array and inplace_vector), string buffers and string streams ([input.output]), and match_results are parameterized in terms of allocators.

[containers.general]

Modify [tab:containers.summary]:

Subclause Headers
[sequences] Sequence containers <array>, <deque>, <forward_list>, <inplace_vector>, <list>, <vector>

[container.reqmts] General container requirements

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

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.

Unless otherwise specified (see [associative.reqmts.except], [unord.req.except], [deque.modifiers], [inplace.vector.modifiers] and [vector.modifiers]) all container types defined in this Clause meet the following additional requirements:

  1. If an exception is thrown by an insert() or emplace() function while inserting a single element, that function has no effects.
  2. If an exception is thrown by a push_back(), push_front(), emplace_back(), or emplace_front() function, that function has no effects.
  3. No erase(), clear(), pop_back() or pop_front() function throws an exception.
  4. No copy constructor or assignment operator of a returned iterator throws an exception.
  5. No swap() function throws an exception.
  6. No swap() function invalidates any references, pointers, or iterators referring to the elements of the containers being swapped.
    [Note 4: The end() iterator does not refer to any element, so it can be invalidated. — end note]

[containers.sequences.general]

Modify:

1 The headers <array>, <deque>, <forward_list>, <inplace_vector>, <list>, and <vector> define class templates that meet the requirements for sequence containers.

[container.requirements.sequence.reqmts]

Modify:

sequence.reqmts.1 A sequence container organizes a finite set of objects, all of the same type, into a strictly linear arrangement. The library provides fourthe following basic kinds of sequence containers: vector, inplace_vector, forward_list, list, and deque. In addition, array is provided as a sequence container which provides limited sequence operations because it has a fixed number of elements. The library also provides container adaptors that make it easy to construct abstract data types, such as stacks, queues, flat_maps, flat_multimaps, flat_sets, or flat_multisets, out of the basic sequence container kinds (or out of other program-defined sequence containers).

sequence.reqmts.2 [Note 1: The sequence containers offer the programmer different complexity trade-offs. vector is appropriate in most circumstances. array has a fixed size known during translation. inplace_vector has a fixed capacity known during translation. list or forward_list support frequent insertions and deletions from the middle of the sequence. deque supports efficient insertions and deletions taking place at the beginning or at the end of the sequence. When choosing a container, remember vector is best; leave a comment to explain if you choose from the rest! — end note]

seqeuence.reqmts.5

X u(n, t);

X u(i, j);

X(from_range, rg)

X(il)

a = il

a.emplace(p, args)

a.insert(p, t)

a.insert(p, rv)

a.insert(p, n, t)

a.insert(p, i, j)

a.insert_range(p, rg)

a.insert(p, il)

a.erase(q)

a.erase(q1, q2)

a.clear()

a.assign(i, j)

a.assign_range(rg)

a.assign(il)

a.assign(n, t)

sequence.reqmts.69 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)

Drafting note: inplace_vector is never reallocated, so there is no need to extend the "For vector, T is also Cpp17MoveInsertable into X" to inplace_vector.

Drafting note: It's okay to use Cpp17MoveInsertable here, even though inplace_vector isn’t allocator-aware. [container.alloc.reqmts.2] states: “If X is not allocator-aware or is a specialization of basic_string, the terms below [including Cpp17MoveInsertable] are defined as if A were allocator<T>”. 

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

EDITORIAL: this synopsis goes after the corresponding one from <vector>: [vector.syn].




















// mostly freestanding
#include <compare>              // see [compare.syn]
#include <initializer_list>     // see [initializer.list.syn]

namespace std {

// [inplace.vector], class template inplace_vector
template <class T, size_t N>
class inplace_vector; // partially freestanding

// [inplace.vector.erasure], erasure
template<class T, size_t N, class U>
constexpr typename inplace_vector<T, N>::size_type
  erase(inplace_vector<T, N>& c, const U& value);
template<class T, size_t N, class Predicate>
constexpr typename inplace_vector<T, N>::size_type
  erase_if(inplace_vector<T, N>& c, Predicate pred);

}  // namespace std

Drafting note: erase and erase_if are specified in terms of remove and remove_if which are not freestanding, and are therefore not freestanding here.

[containers.sequences.inplace.vector] Class template inplace_vector

EDITORIAL: this section goes after the corresponding one from <vector>: [vector]. The sub-sections of this section are nested within it.

[containers.sequences.inplace.vector.overview] Overview

  1. An inplace_vector is a contiguous container. Its capacity is fixed and its elements are stored within the inplace_vector object itself.
  2. An inplace_vector meets all of the requirements of a container ([container.requirements]), of a reversible container ([container.rev.reqmts]), of a contiguous container, and of a sequence container, including most of the optional sequence container requirements ([sequence.reqmts]). The exceptions are the push_front, prepend_range, pop_front, and emplace_front member functions, which are not provided. 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. For any N, if T is an implicit-lifetime type, then inplace_vector<T, N>::iterator and inplace_vector<T, N>::const_iterator meet the constexpr iterator requirements and /* cond-constexpr */ through this section is replaced with constexpr (see Remark below).

LWG Review TODO: We need to review this last clause about constexpr. LEWG design direction is that inplace_vector should be "as constexpr as possible", i.e., it should be constexpr for the types for which C++26 can support constexpr here. That is, this clause needs to state that constexpr only applies to the types for which it's implementable in C++26. LWG should tell us whether this is implicit-lifetime types, trivial types, or something else, and how to word this requirement. The current proposal is to make the API conditionally constexpr.

  1. Any member function of inplace_vector<T, N> that would cause the size to exceed N throws an exception of type bad_alloc.

Drafting note: this is required because assign and others come from the container requirements, and this extends that.

  1. Let IV denote a specialization of inplace_vector<T, N>. If N is zero, then IV is both trivial and empty. Otherwise:
    • If is_trivially_copy_constructible_v<T> is true, then IV has a trivial copy constructor.
    • If is_trivially_move_constructible_v<T> is true, then IV has a trivial move constructor.
    • If is_trivially_destructible_v<T> is true, then:
      • IV has a trivial destructor,
      • if is_trivially_copy_constructible_v<T> && is_trivially_copy_assignable_v<T> is true, then IV has a trivial copy assignment operator,
      • if is_trivially_move_constructible_v<T> && is_trivially_move_assignable_v<T> is true, then IV has a trivial move assignment operator.


























































































































template <class 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], construct/copy/destroy
/* cond-constexpr */ inplace_vector() noexcept;
/* cond-constexpr */ explicit inplace_vector(size_type n); // freestanding-deleted
/* cond-constexpr */ inplace_vector(size_type n, const T& value); // freestanding-deleted
template <class InputIterator>
  /* cond-constexpr */ inplace_vector(InputIterator first, InputIterator last); // freestanding-deleted
template <container-compatible-range<T> R>
  /* cond-constexpr */ inplace_vector(from_range_t, R&& rg); // freestanding-deleted
/* cond-constexpr */ inplace_vector(const inplace_vector&);
/* cond-constexpr */ inplace_vector(inplace_vector&&)
  noexcept(N == 0 || is_nothrow_move_constructible_v<T>);
/* cond-constexpr */ inplace_vector(initializer_list<T> il); // freestanding-deleted
/* cond-constexpr */ ~inplace_vector();
/* cond-constexpr */ inplace_vector& operator=(const inplace_vector& other);
/* cond-constexpr */ inplace_vector& operator=(inplace_vector&& other)
  noexcept(N == 0 || (is_nothrow_move_assignable_v<T> && is_nothrow_move_constructible_v<T>));
/* cond-constexpr */ inplace_vector& operator=(initializer_list<T>); // freestanding-deleted
template <class InputIterator>
  /* cond-constexpr */ void assign(InputIterator first, InputIterator last); // freestanding-deleted
template<container-compatible-range<T> R>
  /* cond-constexpr */ void assign_range(R&& rg); // freestanding-deleted
/* cond-constexpr */ void assign(size_type n, const T& u); // freestanding-deleted
/* cond-constexpr */ void assign(initializer_list<T> il); // freestanding-deleted

// iterators
/* cond-constexpr */ iterator               begin()         noexcept;
/* cond-constexpr */ const_iterator         begin()   const noexcept;
/* cond-constexpr */ iterator               end()           noexcept;
/* cond-constexpr */ const_iterator         end()     const noexcept;
/* cond-constexpr */ reverse_iterator       rbegin()        noexcept;
/* cond-constexpr */ const_reverse_iterator rbegin()  const noexcept;
/* cond-constexpr */ reverse_iterator       rend()          noexcept;
/* cond-constexpr */ const_reverse_iterator rend()    const noexcept;

/* cond-constexpr */ const_iterator         cbegin()  const noexcept;
/* cond-constexpr */ const_iterator         cend()    const noexcept;
/* cond-constexpr */ const_reverse_iterator crbegin() const noexcept;
/* cond-constexpr */ const_reverse_iterator crend()   const noexcept;

// [containers.sequences.inplace.vector.members] size/capacity
/* cond-constexpr */ bool empty() const noexcept;
/* cond-constexpr */ size_type size() const noexcept;
static constexpr size_type max_size() noexcept;
static constexpr size_type capacity() noexcept;
/* cond-constexpr */ void resize(size_type sz); // freestanding-deleted
/* cond-constexpr */ void resize(size_type sz, const T& c); // freestanding-deleted
static /* cond-constexpr */ void reserve(size_type n) noexcept; // freestanding-deleted
static constexpr void shrink_to_fit();

// element access
/* cond-constexpr */ reference       operator[](size_type n);
/* cond-constexpr */ const_reference operator[](size_type n) const;
/* cond-constexpr */ const_reference at(size_type n) const; // freestanding-deleted
/* cond-constexpr */ reference       at(size_type n); // freestanding-deleted
/* cond-constexpr */ reference       front();
/* cond-constexpr */ const_reference front() const;
/* cond-constexpr */ reference       back();
/* cond-constexpr */ const_reference back() const;
    
// [containers.sequences.inplace.vector.data], data access
/* cond-constexpr */       T* data()       noexcept;
/* cond-constexpr */ const T* data() const noexcept;

// [containers.sequences.inplace.vector.modifiers], modifiers
template <class... Args> /* cond-constexpr */ reference emplace_back(Args&&... args); // freestanding-deleted
/* cond-constexpr */ reference push_back(const T& x); // freestanding-deleted
/* cond-constexpr */ reference push_back(T&& x); // freestanding-deleted
template<container-compatible-range<T> R>
  /* cond-constexpr */ void append_range(R&& rg); // freestanding-deleted
/* cond-constexpr */ void pop_back();

template<class... Args>
  /* cond-constexpr */ pointer try_emplace_back(Args&&... args);
/* cond-constexpr */ pointer try_push_back(const T& x);
/* cond-constexpr */ pointer try_push_back(T&& x);
template<container-compatible-range<T> R>
  /* cond-constexpr */ ranges::borrowed_iterator_t<R> try_append_range(R&& rg);
    
template<class... Args>
  /* cond-constexpr */ reference unchecked_emplace_back(Args&&... args);
/* cond-constexpr */ reference unchecked_push_back(const T& x);
/* cond-constexpr */ reference unchecked_push_back(T&& x);
    
template <class... Args>
  /* cond-constexpr */ iterator emplace(const_iterator position, Args&&... args); // freestanding-deleted
/* cond-constexpr */ iterator insert(const_iterator position, const T& x); // freestanding-deleted
/* cond-constexpr */ iterator insert(const_iterator position, T&& x); // freestanding-deleted
/* cond-constexpr */ iterator insert(const_iterator position, size_type n, const T& x); // freestanding-deleted
template <class InputIterator>
  /* cond-constexpr */ iterator insert(const_iterator position, InputIterator first, InputIterator last); // freestanding-deleted
template<container-compatible-range<T> R>
  /* cond-constexpr */ iterator insert_range(const_iterator position, R&& rg); // freestanding-deleted
/* cond-constexpr */ iterator insert(const_iterator position, initializer_list<T> il); // freestanding-deleted
/* cond-constexpr */ iterator erase(const_iterator position);
/* cond-constexpr */ iterator erase(const_iterator first, const_iterator last);
/* cond-constexpr */ void swap(inplace_vector& x)
  noexcept(N == 0 || (is_nothrow_swappable_v<T> && is_nothrow_move_constructible_v<T>));
/* cond-constexpr */ void clear() noexcept;
    
/* cond-constexpr */ friend bool operator==(const inplace_vector& x, const inplace_vector& y);
/* cond-constexpr */ friend synth-three-way-result<T>
  operator<=>(const inplace_vector& x, const inplace_vector& y);
/* cond-constexpr */ friend void swap(inplace_vector& x, inplace_vector& y)
  noexcept(N == 0 || (is_nothrow_swappable_v<T> && is_nothrow_move_constructible_v<T>))
  { x.swap(y); }
};

[containers.sequences.inplace.vector.cons] Constructors

/* cond-constexpr */ explicit inplace_vector(size_type n);

/* cond-constexpr */ inplace_vector(size_type n, const T& value);

template <class InputIterator>
/* cond-constexpr */ inplace_vector(InputIterator first, InputIterator last);

template <container-compatible-range<T> R>
/* cond-constexpr */ inplace_vector(from_range_t, R&& rg);

[containers.sequences.inplace.vector.capacity] Size and capacity

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

/* cond-constexpr */ void resize(size_type sz);

/* cond-constexpr */ void resize(size_type sz, const T& c);

[containers.sequences.inplace.vector.data] Data

/* cond-constexpr */       T* data()       noexcept;
/* cond-constexpr */ const T* data() const noexcept;

[containers.sequences.inplace.vector.modifiers] Modifiers

/* cond-constexpr */ iterator insert(const_iterator position, const T& x); 
/* cond-constexpr */ iterator insert(const_iterator position, T&& x);
/* cond-constexpr */ iterator insert(const_iterator position, size_type n, const T& x);
template <class InputIterator>
  /* cond-constexpr */ iterator insert(const_iterator position, InputIterator first, InputIterator last);
template <container-compatible-range<T> R>
  /* cond-constexpr */ iterator insert_range(const_iterator position, R&& rg);
/* cond-constexpr */ iterator insert(const_iterator position, initializer_list<T> il);
 
template <class... Args> /* cond-constexpr */ iterator emplace(const_iterator position, Args&&... args);
template<container-compatible-range<T> R>
  /* cond-constexpr */ void append_range(R&& rg);

/* cond-constexpr */ reference push_back(const T& x);
/* cond-constexpr */ reference push_back(T&& x);
template <class... Args>
  /* cond-constexpr */ reference emplace_back(Args&&... args);

template <class... Args>
  /* cond-constexpr */ pointer try_emplace_back(Args&&... args);
/* cond-constexpr */ pointer try_push_back(const T& x);
/* cond-constexpr */ pointer try_push_back(T&& x);

template <container-compatible-range<T> R>
  /* cond-constexpr */ ranges::borrowed_iterator_t<R> try_append_range(R&& rg);

template <class... Args>
  /* cond-constexpr */ reference unchecked_emplace_back(Args&&... x);

/* cond-constexpr */ reference unchecked_push_back(const T& x);
/* cond-constexpr */ reference unchecked_push_back(T&& x);

static /* cond-constexpr */ void reserve(size_type n);

static constexpr void shrink_to_fit() noexcept;

/* cond-constexpr */ iterator erase(const_iterator position);
/* cond-constexpr */ iterator erase(const_iterator first, const_iterator last);
/* cond-constexpr */ void pop_back();

[containers.sequences.inplace.vector.erasure] Erasure

template<class T, size_t N, class U>
  /* cond-constexpr */ size_t erase(inplace_vector<T, N>& c, const U& value);





auto it = remove(c.begin(), c.end(), value);
auto r = distance(it, c.end());
c.erase(it, c.end());
return r;

template<class T, size_t, class Predicate>
  /* cond-constexpr */ size_t erase_if(inplace_vector<T, N>& c, Predicate pred);





auto it = remove_if(c.begin(), c.end(), pred);
auto r = distance(it, c.end());
c.erase(it, c.end());
return r;

[version.syn]

Add:

#define __cpp_lib_inplace_vector   20XXXXL // also in <inplace_vector>

[diff.cpp23.library] Compatibility

Modify:

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, Tomasz Kamiński, and many others. Many thanks to Daniel Krügler for reviewing the wording.