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

cppcon.org/
github.com/CppCon/CppCon2021
---
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).
---
Videos Filmed & Edited by Bash Films: www.BashFilms.com
KZbin Channel Managed by Digital Medium Ltd events.digital-medium.co.uk
*--*

[@brunizzl]

the use of boost::hana::type_c at 5:22 is not nessecairy. one could just write template constexpr auto determine_size_type() { if constexpr (capacity

[@adammitchell55]

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.

[@gast128]

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.

[@KitsuneAlex]

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

[@tcocaine]

Great talk!

[@yuehuajia3176]

definitely.

[@immanuellitzroth1905]

Great talk.

[@Omnifarious0]

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.

[@user-cy1rm5vb7i]

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

[@fedoralekseev8824]

std::bit_cast is not constexpr if source or target types are pointers

[@Roibarkan]

I believe bit_cast copies, and won’t allow referencing (or pointing) directly to the storage. Also, I think bit_cast requires T to be trivially copiable (and the presented solution “only” requires trivially constructible for constexpr)

[@kamlot0]

You need to cast std::byte* to T*, but std::bit_cast on pointers is not constexpr.

[@IsaacClancy]

unfortunately std::bit_cast isn't constexpr then casting from one pointer type to another

[@olzhaszhumabek2034]

bit_cast uses memcpy, which will not work if the type has non-trivial copy constructor.

[@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"?

[@jamesflames6987]

Look at the bottom of the slide. In the case of trivial types they make an array of that type. In the case of non trivial types they make an array of bytes. You can't static_cast bytes to an object, hence reinterpret_cast.

[@CarlosAcostaPastene]

Is the source code of this talk available somewhere? 🤔

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

[@vbregier]

You have to worry that the moved-from array does not call elements destructors when it is destroyed, which means at least resetting its size to 0.

[@JohnB5290]

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?

[@VioletGiraffe]

There is nothing in common between optional and and a static vector.

[@DFPercush]

std::optional is a union + a bool. I think one of the points he brought up was that you can't convert a union{T...}* to a T*, at least not at compile time.

[@n0ame1u1]

@@DFPercush Why not? If `x` is a `union {unsigned char default_field; T contents }`, can't we just do `&x.contents`?

[@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

[@Roibarkan]

I think it’s sort of discussed around 52:00, where he says a single such element might be easy, but an array (which can also be referenced as T&) isn’t currently “defined behavior” (strict aliasing)

[@eugnsp]

It's in the standard library - std::optional.

[@icenberg5908]

Are you making source available?

[@alexandrebustico9691]

there is a open source library : ETL for embedded template library, which provide STL equivalent classes, but using only statically allocated memory, and there is static vector among all the others containers : www.etlcpp.com/vector.html

[@hampus23]

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

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

[@embeddor2230]

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

[@brunizzl]

wether or not the range would consist of two nullptrs is unfortnately only known at runtime.

[@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 ?

[@jamesflames6987]

That calls the default constructor of all elements.

[@fburton8]

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.

[@eroween2]

That's already what is happening if we think about it. "You specify the semantics" -> That's code, literally "programs should be [...] writing low level code" -> that's a compiler You just increase or decrease the amount of information you provide to your compiler by choosing a lower or higher language. It's just a bit more strange when you write code that are expected to be libraries and used in generic context because then you have to account for everything. Otherwise you can most of the time make things much simpler if your context allow it

[@fergusbaker2701]

check out the Julia programming language

[@jamesflames6987]

The optimal code isn't the problem. The code is just a bunch of if statements and assignments. Figuring out the exact semantics is what the whole talk is about.

[@dennisrkb]

Isn't this called std::array?

[@lerusius]

he talks about this at 9:47

[@xplorethings]

he talks about the issues with using std::array for this case around 9:55

[@Dth091]

No, a std::array always contains exactly n items. A static_vector contains n *or fewer* items.

[@adammitchell55]

std::vector has variable size and variable capacity. std::array has fixed size and fixed capacity. This proposed static_vector has variable size and fixed capacity.

[@ohwow2074]

That initialized all of the N elements. Whereas his static vector implementation does not. So there's a performance cost in std::array. Also he mentioned that not all types are default constructible.

[@danjo008]

I can’t help thinking that this is an awfully complex way of trying to avoid using a std::array together with a separate count variable.

[@broken_abi6973]

that is a terrible solution and doesn't solve the actual problem

[@hampus23]

No

[@boffo25]

Why not std::array

[@hampus23]

9:55

[@Avantarius]

After watching this video I still don't understand why C++ people call dynamic arrays "vector" and vectors "array"... very confusing... like all of C++

[@4otko999]

actually great talk and very likable speaker, alas mention of rust gives this talk a faint smell of sh-t. i understand that you have to look how similar problems are solved in other languages, but rust is a very ugly language and it is likely would be a drawback for c++ to borrow anything from it. would be much better to reference some other language instead.

[@isitanos]

Such open-mindedness.

[@njd9828]

Great talk. I spent yesterday trying to make absl::InlinedVector constexpr. I watched this video and subsequently deleted my code.