Implementing static_vector: How Hard Could it Be? - David Stone - CppCon 2021

---
static_vector is a std::vector that allocates things on the stack instead of the heap. We have std::vector, so it should be easy to write a non-allocating version, right?

Sadly, it's not quite that simple. There are many aspects of the vector interface that make sense based on a container that can reallocate, but do not make sense for a container that cannot. This leads to some API differences. static_vector also faces certain challenges around constexpr that makes it both more and less constexpr than std::vector.

We will go into detail on how std::vector and how static_vector work, how they are similar, and how they differ. This presentation will be focusing on lower-level details and interactions with specific language features in C++20 and (hopefully) C++23. There will be lots of code examples, and we'll step through how they work and where they fall short, trying to build up to a working, production-ready solution.

---
David Stone

David Stone has worked on autonomous vehicles, large-scale distributed systems, and now works developing software for high-frequency trading. He is a member of the C++ Standardization Committee, where he chairs the Modules Study Group (SG2) and is the vice chair of the Evolution Working Group (EWG).

---

*--*

[brunizzl]

the use of boost::hana::type_c at 5:22 is not nessecairy. one could just write


template<std::size_t capacity>
constexpr auto determine_size_type() {
if constexpr (capacity <= std::numeric_limits<unsigned char>::max()) {
return unsigned char{};
}else if constexpr (capacity <= std::numeric_limits<unsigned short>::max()) {
return unsigned short{};
}
...
}

template<std::size_t capacity>
using size_type =


i loved the talk and would love to see static_vector become part of c++23.

[adammitchell]

Great talk! I was just building my own equivalent static_vector class (and also a "small-string-optimized" vector). I hit some of the same issues you mentioned. I ended up creating a raw_buffer class (what you called uninitialized_array) using a union to wrap it to prevent it from initializing anything. This allowed me to get a typed array (nice for debugging, etc.) and I could construct things into it. When I attempted to make it constexpr, I hit a few issues. So maybe this approach will prevent it from being constexpr. Not sure yet.

[ElementaryWatson-]

My suggestion is a new intrinsic compiler type that leaves the object uninitialized, e.g. std::array<T, N> a{std::noinit}; would be uninitialized array.

[Omnifarious]

57:21 - I think that reinterpret_cast to and from a 'normal' pointer type and `byte *` should be considered constexpr. Normal being, not a function pointer, not a member variable pointer.

[satosiwu]

40:30 speaker is wrong here. Trivially move constructable implies trivially destruable.

Constructability is defined as a well formed statement:
T t(args..)

For it to be trivially constructable, this statement needs to be trivial. This requires both a trivial constructor and a trivial destructor.

[Raspredval]

but what about std::bit_cast? Isn't it the solution for the constexpr reinterpret cast problem?

[gast]

Boost's static_vector; small_vector; circular_buffer and flat_map are all useful additions to std containers. Only flat_map is scheduled to be standardized.

[CarlosAcostaPastene]

Is the source code of this talk available somewhere? 🤔

[KitsuneAlex]

Very nice talk, i was looking forward to someone taking a shot at a nice explanation/implementation of a static_vector :)

[Peregringlk]

At 15:20 or so, why can't you apply a static_cast over non-trivial types if you know the actual type behind the pointer? Or does the restriction only apply when the pointed-to memory is uninitialized? And what is the "clever trick with unions"?

[hampus]

10:00 How about an std::array with std::optional?

[OlliS]

Use boost::small_vector, which includes some static storage but can grow beyond dynamically.

[JohnB]

We already have std::optional, which is a static_array of capacity 1. So, why is it that hard to generalize, in particular wrt constexpr?

[embeddor]

36:14 why not just template specialize on std::nullptr_t instead of this whole thing with memcpy?

[Solarbonite]

If effectively we're doing placement new, why do we have to worry about move constructors? Wouldn't it always be safe to just not destroy the original and simply copy the raw bytes over? I guess this changes the meaning of the original object but it makes sense.

[ElementaryWatson-]

Just wrap array in a union and use std::start_lifetime_as when you do construction.

[ABaumstumpf]

I HATE that C++ is getting more and more undefined behaviour.
It makes it so much harder to use anything cause even checking for UB is basically impossible as the compiler can rip out most of those checks as it is allowed to assume no UB happens ever.

You wanna do a simple cheap sanity-check if a signed addition overflowed? You can't. More than once i had this problem were an overflow was permissible but checking for that beforehand was a lot more computational costly than checking after the fact (yes - sometimes you are not interested in the exact result but just some aspects of that. In which case you have some further logic that can happen after the calculation regardless the outcome and extra handling just in case something did go wrong. )

The only thing imo even worse is that there there is no diagnostic required. Cause of this you can have code that you have no idea is faulty, and at any time it can just do anything it likes, yet there is no way for you of knowing that other than knowing the entire C++ specification AND checking the entire codebase by hand.

[AxelStrem]

Isn't there some kind of "deferred constructor" template in boost that would make any class default-constructible? This would probably allow the std::array approach

[vbregier]

uninitialized_array, that provides storage for n elements of type T, without calling elements constructor / destructor.
Is this not what c-style array T a[n]; declaration provide ?

[fburton]

I can’t help thinking that programs should be writing this kind of low-level code, i.e. you specify the semantics, say you want it to run as fast as possible in certain situations, and let the computer find the optimal code.