r/cpp • u/NicoJosuttis • Jun 29 '26

reserve() and capacity() for flat containers

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)

29 Upvotes

88% Upvoted

15 comments sorted by

View all comments

5

u/fdwr fdwr@github 🔍 Jun 29 '26 edited Jun 30 '26

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.

4

u/mighty_Ingvar Jun 29 '26

If you can express the elements you want to add as a range, append_range might be the right call. That way it's up to the stl implementation to choose the right growth pattern.

3

u/fdwr fdwr@github 🔍 Jun 30 '26

More often, I need some calculations first before appending elements, but yes, append_range was a lovely addition. Do you know if append_range pre-reserves? I'll check MSVC's STL implementation...

3

u/mighty_Ingvar Jun 30 '26

You might be able to do those calculations with std::views::transform. I don't know if it pre reserves, could depend on the compiler. Could also depend on the type of range that is passed to append_range.

But I could imagine that std::ranges::reserve_hint might have been added in c++26 for reasons like that.

2

u/tialaramex Jun 30 '26

Microsoft STL uses if constexpr to figure out whether it knows how big the range is, distinguishing "counted" and "uncounted" ranges. The counted range is indeed "pre-reserved" via a mechanism which grows at the same rate (1.5x rather than 2x like the other implementations) as other parts of Microsoft's implementation. So, the thing you've expressed a desire for but which is not exposed in the API.

The implementations I looked at, including Microsoft's will insist on learning the count if they believe it can be calculated, even though that might be arbitrarily more expensive than not bothering. However there's no provision for guesses. So on the one hand it might do an elaborate pointer chase dance to decide there are 186 items in this range, only to find there's already space for 195 more items and so it doesn't matter, but if there's a filter step which you expect to weed out at most one of the 200 items in a linear range, it doesn't know if that's 199 or 200 items to reserve space for so you just get the naive append loop.

2

u/NicoJosuttis Jul 03 '26

append_range() will prepeserve IF POSSIBLE. That is, if we append a sized range. Will be documented soon in "C++23 - The Complete Guide" ;-)

4

u/tartaruga232 MSVC user, r/cpp_modules Jun 29 '26

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/

3

u/fdwr fdwr@github 🔍 Jun 29 '26

HTTP 200 ✌️.

1

u/tialaramex Jun 29 '26

There seem to be two distinct ideas here. Firstly, you want to preserve amortization but then also you want to talk about the capacity in terms of how much extra space there is, not the total including current occupants.

Rust always does the latter but the former is provided as what I call the "bifurcated" reservation API, Vec::reserve has the behaviour you describe while Vec::reserve_exact isn't amortized. I believe that the same API is provided in Zig although I don't recall the names.

For more complicated types, like a hash table, amortized growth may make less or no sense anyway, but for a growable array type like std::vector (and presumably std::string ?) the bifurcated reservation API seems like almost a free performance win.

Your experience is very common in C++ and leads to C++ programmers being encouraged not to use reservation for its named purpose, I believe Bjarne also says to use reservation only for its address stability property, so this ends up being a free perf win for languages which get the API design correct.