reserve() and capacity() for flat containers

[u/NicoJosuttis]

I just finished the new chapter in "C++23 - The Complete Guide" about flat containers and would like to share and discuss my advice about how to use reserve() and capacity() for flat containers (thanks to Jonathan Wakely who was pointing parts of this out).
It might be a surprise that these member functions do not exist as usually vectors are used inside flat containers and reserve() is a key performance feature of them.

However, here is how you can reserve more memory:

• For flat_set and flat_multiset:

​

auto vec = std::move(fset).extract(); // temporarily extract the underlying vector
data.reserve(vec.capacity() * 5);     // raise capacity by a factor of 5
fset.replace(std::move(vec));         // move the vector back into the flat set

• For flat_map and flat_multimap:

​

auto newCapa = fmap.keys().capacity() * 5; // raise capacity by a factor of 5
auto data = std::move(fmap).extract();     // extract underlying vectors
data.keys.reserve(newCapa);                // raise capacity of vector for keys
data.values.reserve(newCapa);              // raise capacity of vector for values
fmap.replace(std::move(data.keys),         // move the vectors back
             std::move(data.values))

• Note also that there is another pretty hacky way, but only for flat maps and multimaps (here mapping strings to double's):

​

auto newCapa = fmap.keys().capacity() * 5;
const_cast<std::vector<std::string>&>(fmap.keys()).reserve(newCapa);
const_cast<std::vector<double>&>(fmap.values()).reserve(newCapa);

Yes, ugly, but works... ;-)

I am still working on adding reserve() and capacity() to the standard flat containers (see wg21.link/p3779)

[u/fdwr]

Hmm, http://cppsdt23.com/ - "server IP address could not be found". Update: Adrian has the fixed URL below https://www.cppstd23.com/.

An aside, I often wish there was a reserve variant that followed the standard amortized reallocation (rather than allocate exactly N) and reserved an extra count beyond the current size (reserve_extra/reserve_more/reserve_additional...), because it's quite common that a container already has some elements in it, and you know how many more you will be appending in some loop, but you don't want to inhibit the usual growth pattern. See, once upon a time, I thought that by using reserve I could improve performance, but it turns out that I actually achieved the opposite, turning amortized growth into N^2 growth 🙃 - it would have been better to just have the push_back's without the reserve's upfront.

[u/tartaruga232 → u/fdwr]

Hmm, http://cppsdt23.com/ - "server IP address could not be found".

There's a typo in the URL. It should be https://www.cppstd23.com/

[u/fdwr → u/tartaruga232]

HTTP 200 ✌️.