Quuxplusone/SG14 now has inplace_vector

This week I implemented P0843R9 “inplace_vector in the SG14 algorithms-and-data-structures repository Quuxplusone/SG14. This is the same container that Boost.Containers calls static_vector. Personally, I prefer the name fixed_capacity_vector — see inplace_foo versus fixed_capacity_foo (2018-06-18) — but I think WG21 has litigated that name to death already, so inplace_vector it is!

sg14::inplace_vector supports trivial relocatability out of the box (as long as you use my fork of Clang or another compiler supporting P1144 trivial relocation). For example,

sg14::inplace_vector<T, 4> v, w;
v = std::move(w);

is trivial when T is trivial; and when T is trivially relocatable, it compiles to the equivalent of

if (w.size() < v.size()) {
  std::move(w.data(), w.data() + w.size(), v.data());
  std::destroy(v.data() + w.size(), v.data() + v.size());
  v.size_ = w.size_;
} else {
  std::move(w.data(), w.data() + v.size(), v.data());
  std::uninitialized_relocate(w.data() + v.size(), w.data() + w.size(), v.data() + v.size());
  std::swap(v.size_, w.size_);

The else branch says, “Assign the first v.size() elements; then relocate the remaining elements from w into v, thus simultaneously decreasing w’s size and increasing v’s size.”

Notice that the else branch is exception-safe only when uninitialized_relocate is guaranteed not to throw. If it throws, then we need to set w.size_ = v.size_ before propagating the exception, because uninitialized_relocate will have cleaned up after itself by destroying all of the objects in both the source and target ranges. That cleanup behavior is common to all the uninitialized_foo algorithms; see [specialized.algorithms.general]/2.

This suggests that P1144 ought to do at least one of three things: (1) Guarantee that std::uninitialized_relocate throws nothing for trivially relocatable types; and/or (2) Restore R7’s is_nothrow_relocatable type-trait with behavior tied specifically to the throwingness of uninitialized_relocate and company; and/or (3) Give uninitialized_relocate a conditional noexcept-specification (which is a bad idea). I’m leaning toward (1), which is spiritually close to P2786’s proposal of a dedicated entrypoint std::trivially_relocate that would be guaranteed nothrow but (in return) only conditionally callable.

The only defect I intentionally corrected in P0843R9 — besides that P0843R9 marks a lot of things constexpr that can’t be constexpr-evaluated for subtle abstract-machine reasons — is that it was missing an overloaded assignment operator of the form

Vec& operator=(initializer_list<value_type>);

Every existing STL container has one of these. For ordinary containers it’s fairly redundant, because even if it didn’t exist, overload resolution would simply give you a pair of calls to

Vec(initializer_list<value_type>); // implicit conversion
Vec& operator=(Vec&&);  // move-assignment

and the move-assignment is generally cheap. But when move-assignment isn’t cheap — as for inplace_vector — the initializer_list overload cuts out the middleman.

In fact, a custom allocator with POCMA false can not only be expensive to move-assign, but can even give you different runtime behavior depending on whether a temporary container is created or not! Godbolt:

std::pmr::monotonic_buffer_resource mr;
auto v = std::pmr::vector<int>(&mr);
v = {1,2,3};

That last line is okay as written, but if it were v = {{1,2,3}} then we’d try to allocate from the default arena (which is null) and crash.

Of course it’s possible to blow your whole leg off with std::pmr in several ways; and operator=(initializer_list) predates std::pmr by two whole C++ versions. I don’t know why it was originally added to the library in the C++0x timeframe. N2215 §10.5 and §11.3 seem related. My guess is that these assignment operators were added under the mistaken impression that they would be needed for correctness (before the overload-resolution rules for braced-init-lists had solidified), and then simply forgotten about. Finally, in C++17, std::pmr restored a positive reason for them to exist.
See “Origins and purposes” (2023-10-18).

If you find a bug or defect in sg14::inplace_vector, please report it to me and/or via the GitHub issues list. Pull requests welcome!

Posted 2023-10-20