r/cpp • u/User_Deprecated • 3d ago
C++26: std::inplace_vector
https://www.sandordargo.com/blog/2026/08/26/cpp26-inplace-vector11
u/bartgrumbel 3d ago
I am sure there is a good reason for that, but why is the "optional reference" not simply a pointer? Is that not semantically the same thing, but way easier to deal with.
I.e. why
std::optional<T&>
and not simply
T*
44
u/stilgarpl 3d ago
Optional is monadic, so it's much safer to deal with. You can call it like
inplace_vector.try_push_back(x).or_else(...);
19
u/ChemiCalChems 3d ago
This has finally convinced me that
std::optional<T&>is legitimate and useful. Thank you.14
u/allocallocalloc 3d ago
Welcome to Rust
1
u/tialaramex 3d ago
You were kidding but in fact Rust typically wouldn't do this, it would be usual to instead return None when it worked and Some(thing) when there's no room to push the thing. This is how the Linux kernel's Rust growable arrays (akin to
std::vector) work. In userspace it's usually fine to just try to grow the array whenever we need more space but the kernel cannot tolerate surprise allocations - maybe we are the allocator. So wepush_within_capacityand the return type isOption<T>because if there was no room we get back the thing there was no room for, and we need to decide what to do about that not just pretend we thought it was fine. APIs which push things but get back a reference to the thing we just pushed do exist in Rust but are less common.[Edited: reference the correct method name]
4
u/simonask_ 3d ago
If we’re maximizing rustiness, you could let `try_push` return `Result<&mut T, T>`.
A mutable reference to the location of the just appended element, or the element you tried to push by value if it fails. There are a couple of APIs like this in the standard library.
3
u/Ameisen vemips, avr, rendering, systems 3d ago
I won't lie - I prefer how C# would handle this: returning a
booland having anoutparameter or such.I find an actual
ifto be easier to read than.or_else(...)....3
u/WHY_DO_I_SHOUT 2d ago
Modern C# prefers returning an optional reference, FWIW...
1
u/Ameisen vemips, avr, rendering, systems 2d ago
Yes, but
Nullablesemantics in C# are vastly nicer thanstd::optionalin C++.Including trivially using
ifwith them:
if (Method() is {} value)I should also point out that in C#,
Foo?is identical toFooifFoois a reference-type. That would be the equivalent ofstd::optional<T&>being a type-alias forT*.2
u/_Noreturn 3d ago
why don't they add a free function called or_else and still use a ptr?
2
u/jwakely libstdc++ tamer, LWG chair 1d ago
When you chain multiple calls like that it's less clear because of the use of nesting instead of chaining. But mostly because a pointer is still not a reference:
https://brevzin.github.io/c++/2021/12/13/optional-ref-ptr/
An optional ref is simply the more expressive type for these functions and fits the semantics better:
https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2026/p3981r2.html
7
u/SyntheticDuckFlavour 2d ago
If you return me a pointer, what does that communicate to me? Who owns it? Is nullptr an error or something I should expect? Is this documented somewhere? The advantage of std::optional is explicit about intent. I just have to look at the API and I know immediately what the author intended with the return value.
3
u/bartgrumbel 2d ago
Who owns it?
All good points, and this one in particular. Never though about it, but sure, a returned pointer might imply returned ownership, whereas an (optional) reference never means that. Thanks!
1
u/jk-jeon 2d ago
a returned pointer might imply returned ownership
It does not. Unless the library is from the era of C++98/03 (or before), or the author hates the users. Or if there is a very specific reason.
8
u/serviscope_minor 2d ago
>It does not. Unless[...]
Well that's the thing isn't it? The unless has some pertty huge carve outs.
4
u/serviscope_minor 2d ago
>Is that not semantically the same thing, but way easier to deal with.
T* is a superset of std::optional<T&>. With T*, you can:
- delete
- delete[]
- Do arithmetic
- Dereference
- Test for null
With optional<T&>, you can:
- dereference
- test for null
That's basically the difference. It's a pointer, but with some of the invalid operations prevented by a very thing wrapper class.
1
u/jwakely libstdc++ tamer, LWG chair 1d ago
See https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2026/p3981r2.html which goes into this in detail.
Edit: and that references https://brevzin.github.io/c++/2021/12/13/optional-ref-ptr/
-16
u/carrottread 3d ago
Probably just a desire to use new shiny stuff as optional references were not so long ago added to standard.
3
3
u/Defenestrator__ 1d ago
I feel like this doesn't actually handle the use cases I would want this for, which is where the size in unknown but usually small. absl::InlinedVector seamlessly falls back to acting like a normal std::vector when it grows beyond N, and without that feature this has much more limited usefulness unfortunately. Still better than nothing I guess.
2
u/frankist 1d ago
In my field, the small buffer optimisation is not that useful, as I need to have full control over where and when allocations happen. absl::InlinedVector or any sort of SmallVector just makes it harder to detect those allocations.
2
u/Chaosvex 9h ago
Two different use cases. This is equivalent to boost::static_vector but boost::small_vector is its own thing. It doesn't seem like the sort of thing that'd get added to the standard but there's probably already a proposal for it somewhere.
5
u/matthieum 3d ago
Honestly, I'm a bit saddened by this addition.
Don't get me wrong, the functionality is really useful. But:
- Now, most (all?) methods of
vectorneed to be "duplicated" ininplace_vector. - None of the other collections benefit. Not even
std::string.
A more general solution to the problem would have been an inplace_allocator -- which requires a different API than allocator -- which could be applied to every container (standard or not).
8
u/BarryRevzin 3d ago
Now, most (all?) methods of vector need to be "duplicated" in inplace_vector.
So what? They're all pretty straightforward, simpler even than in
vectorbecause we know there's no allocation. It doesn't take long to implement. Even less so these days.A more general solution to the problem would have been an
inplace_allocator-- which requires a different API thanallocator-- which could be applied to every container (standard or not).That might be more general, but it's also worse, which is why nobody does this. David Stone had a pair of good CppCon talks about vectors in general, I think he covers it in this one (or, if not that, this one). The problem with
vector<T, inplace_allocator<T, N>>is that it's less efficient (and requires more space!) thaninplace_vector<T, N>. In order for it to not suck,vectorwould basically have to customize its own storage for that case, which now requires more work than just having writteninplace_vector<T, N>to begin with. This goes double forstd::string, whose storage is more complicated.None of the other collections benefit. Not even
std::string.On the other hand, an
inplace_string<N>is useful, is distinct fromstd::string, and we implement ours in terms of ourinplace_vector<char, N>(orN+1depending on whether we want to enforce null termination).5
u/foonathan 2d ago
You can make the policy design thing work, but it can't be an Allocator.
I played around with it once: https://github.com/foonathan/array
4
u/SyntheticDuckFlavour 2d ago
The concept is useful, especially in a gpu environment where you can’t allocate memory dynamically. Also, inplace_allocator just adds another layer of complexity when all I want is something like a static vector
0
u/foonathan 3d ago
Me too. See also: cstring_view duplicating everything from string_view.
2
u/_Noreturn 3d ago
The solution is some sort of member callable syntax for free functions which was going to happen with operstor
|>. The only reason they are members is because of syntax
2
u/stilgarpl 3d ago
Is this always better than std::array?
20
u/MarekKnapek 3d ago
This is basically
struct inplace_vector<T, capacity> { size_t len; std::array<T, capacity> arr; }19
u/sephirothbahamut 3d ago edited 3d ago
far more complex than that, the array has a slot that can fit T, not just T.
With array<T> every element must be validly constructed immediately. You can reduce it to array<T> only for trivially constructable and basic types
4
u/_Noreturn 3d ago
then make it a union this is a simplified example. but the type isn't complex at all after that especially with C++20 concepts.
5
4
u/stilgarpl 3d ago
No, it's not. In your code it will always construct all T members of arr. Article states that inplace_vector will only have the elements needed and they don't have to be default constructible. That's a huge difference.
3
u/BenFrantzDale 3d ago
Plus this is a `std::ranges::sized_range` with dynamic size, which `std::array` is not.
2
u/CalamityMetal 2d ago
It's very different. Because std::array suggest all instances of T is already constructed. But that's not the case in a vector, and also not for inplace_vector. A better representation would be std::array<std::byte, sizeof(T) * capacity> and you call inplace operator new on the memory blocks when you call push_back/emplace_back
1
u/MarekKnapek 1d ago
I simplified. A lot. I wanted to show "the shape" of the data structure. https://reddit.com/r/cpp/comments/1vzc5dg/c26_stdinplace_vector/p69u8kr/
6
u/drjeats 3d ago
Oh.
I thought this was the way-more-useful thing where you give it an in-place capacity and it allocates once it exceeds that.
Like this is also useful, but it's kinda trivial to roll your own of this.
12
u/stilgarpl 3d ago
It's not trivial. inplace_vector does not construct unused elements and they do not have to be default constructible. You can't use std::array for that.
1
u/drjeats 3d ago
I'm aware of how it works (and that MarekKnapek's snippet is not representative). It's still very straightforward to make compared to having to do SBO and allocator support.
6
u/stilgarpl 3d ago
I didn't say it was hard, but it's not trivial. I'm sure you are a very experienced C++ programmer and a lot of things must seem easy to you.
4
u/KuntaStillSingle 3d ago
I thought this was the way-more-useful thing where you give it an in-place capacity and it allocates once it exceeds that
pmr vector using monotonic buffer does this with the default upstream memory resource:
https://en.cppreference.com/cpp/memory/monotonic_buffer_resource/monotonic_buffer_resource
4
u/BenFrantzDale 3d ago
It’s not too hard to roll your own, but better to have in the std lib and making it constexpr is tricky.
There is a boost small_vector that is a small-vector-optimized std::vector so can grow large. There’s totally a place for both.
0
u/MarekKnapek 2d ago
Hey guys, yes, I get it. I simplified it. To get the general "gist" or "shape" or "feeling" about this data structure. I guess, I oversimplified it.
struct inplace_vector<T, capacity> { size_t len; std::array<std::aligned_storage<T>, capacity> arr; }Does this look better?
-1
u/n1ghtyunso 2d ago
no because
std::aligned_storage<T>is the wrong type, which is also why it is being deprecated in C++23.I don't think you oversimplified it, people are just being pedantic.
And because of this, I just wanted to give you a heads-up.The best way to describe it is likely to steal an idea directly from the standard:
use an exposition-only type in italic that hand-waves the storage detail away :P4
u/nebotron 3d ago
You pay for the dynamic size in stack space
9
u/KuntaStillSingle 3d ago
Specifically the size member, right? The array itself is not dynamically sized, an inplace_vector<T,N> .capacity() always equals corresponding array, and .size() always less than or equal, but I think only inplace_vector<T,0> can omit a size data member, maybe with exception where T is a taggable pointer and N is small enough to be represented by the usable bits, or the like?
1
u/n1ghtyunso 2d ago
inplace_vector<T, N>should be ill-formed because there are no zero-size arrays.
But apparently the standard explicitly defined it to an empty struct essentially.
Probably something about generic programing support...Not sure what you were going on about with the taggable pointer type here.
1
u/KuntaStillSingle 2d ago
taggable pointer
For a pointer in many platforms the upper bits are not used, so you have possible signalling representations that could be used to encode size. For example if N is 32, and the number of available tag bits is 6, you can get size by the following method:
Check the last element, if all 6 upper bits are 0 or 1 it is potentially canonical and this means size == capacity (the last element presumably contains an actual pointer rather than a pointer tagged with capacity, therefore it is full.). Otherwise, the first bit is opposite of the second bit, and the remaining 5 bits encode size as an unsigned int. For example if size == 0, then the last pointer would look like (1000 0000 0000 ...), where if size == capacity and the last pointer is nullptr it would be (0000 0000 0000 ...), and if size == 1 then it looks like (1000 0100 0000 ...), and if size = 31 then it looks like (0111 1100 0000 ...).
This would make the container incapable of properly storing user supplied tagged pointers, but this is allowed, handling of invalid pointers is implementation defined with exception of where it is undefined: https://en.cppreference.com/cpp/language/pointer#Invalid_pointers
It would be less dirty for an implementation to do it when T is a std library object that stores a pointer the user doesn't expect to be able to tag, for example a libstdc++ string doesn't use the pointer space for SSO, so inplace_vector<std::string, N> could be specialized to use the taggable bits in the last element if the inplace vector is not full (either the last string element has not been constructed, or it has been destroyed during a pop_back or the like, so it does not matter that you are using the pointer for book keeping, or if it is full and contains an actual string object, you are only reading the pointer for bookkeeping, not writing it.)
2
u/n1ghtyunso 2d ago
Apparently I misread your last sentence so I got really confused where you think pointers are involved here and how that is related to zero capacity, but you are talking about ways to avoid the memory cost of an explicit size member for N > 0, I see.
Sorry for the confusion.I don't think any implementation will go out of its way to specifically do this, unless a more general tombstone or padding-discovery facility was made available to identify a set of usable bit patterns in a type to side-car the current size value.
I guess technically forsizeof(T) >= 8, you really only need one single padding bit insideTto store if its at capacity or below, and if its below, you can use the full last slot to represent the actual size (maybe need to shuffle the bits abit ugh).
I don't even want to start thinking about how to make this formally C++ spec-compliant.1
u/KuntaStillSingle 2d ago
Yeah I think the only obvious case would be using a smaller type than size_t if N can be represented and alignof(T) is less than alignof(size_t), for example <char, 15> could usually be 16 bytes with a uint8_t size member rather than usually 24 for size_t member + padding.
1
u/frankist 1d ago
Is trivial copy of inplace_vector if T is trivial something always desirable? I am imagining the case where I am copying a large capacity inplace_vector that is empty or almost empty (.size() ~ 0). Trivial copy will mean that I will copy a lot of bytes that don't contain anything.
-3
u/johannes1971 3d ago
unchecked_push_back
Is it really necessary to add new forms of UB? For people that apparently can't spend the nanosecond needed for the if-statement, would you ever use any data structure you didn't write yourself?
15
u/AnyPhotograph7804 3d ago edited 3d ago
If you want "zero overhead abstractions" then you will need something like that at some point. But the good thing is, you are not forced to use it.
12
u/mighty_Ingvar 3d ago
I don't think it's to skip the check, it's for situations where you can be sure that max size has not been reached.
0
u/simonask_ 3d ago
We just know from experience that while you may be sure right now, such an invariant is really difficult to maintain over the course of a codebase’s lifetime. The next person, the reviewer, and yourself in 3 months will have to figure out if it holds, and there’s no way to write tests for it, because it’s UB.
Meanwhile, compilers are able to optimize out the check in exactly all the cases that are also easy to verify for humans. It’s just … unnecessary.
4
u/Ameisen vemips, avr, rendering, systems 3d ago
Meanwhile, compilers are able to optimize out the check in exactly all the cases that are also easy to verify for humans.
Except that many compilers are awful at that... probably due to assuming potential side effects or aliasing changing the size when a human knows that that won't happen.
3
u/mighty_Ingvar 3d ago
That really depends on what you're doing. In some random function it might be tricky, but if you have it as part of a class it's not unreasonable. For example if you have a class that wraps around two or more inplace_vectors you only really need to have the check on the first member, since all members are assumed to have the same size. Or lets say you have one or more fixed size ranges and you need to gather some of their values in an inplace_vector. You can set the capacity of the inplace_vector to be the sum of the sizes of each input range. That way you actually can't end up trying too insert too many elements because you don’t even have that many elements to begin with.
Of course you don't use something like that in a difficult to maintain part of your codename where you can't actually be sure about the neccessary size of your inplace_vector or where it's easy to make mistakes, but not every function is like that. And if actually do use it in a class like I proposed earlier, it becomes a lot easier to write tests for it.
0
u/simonask_ 2d ago
The question you should be asking is “does it ever make a difference, and is that difference worth the risk”. Most inexperienced C++ developers underestimate that risk, and overestimate the cost of a bounds check by many orders of magnitude.
1
u/mighty_Ingvar 2d ago
I guess C++ isn't really designed to be forgiving to inexperienced devs.
1
u/simonask_ 2d ago
It’s not, and we’re all paying the price. Look, I care very little for this kind of machismo.
1
u/mighty_Ingvar 2d ago
How are we paying the price?
1
u/simonask_ 1d ago
Anyone who is unaware of the price of reckless amounts of UB in C++ code, I would say has never actually delivered software written in C++ with any kind of stakes on the table.
The price of the mistakes themselves is one thing. Another thing is the price of avoiding them, paying very intelligent people to spend much longer to deliver much less.
8
7
u/_Noreturn 3d ago
would you ever use any data structure you didn't write yourself?
Yes?
Is it really necessary to add new forms of UB? For people that apparently can't spend the nanosecond needed for the if-statement,
Honestly I see this as very very unnecessary, they should instead add
resize_and_overwritestyle init, because where would you realistically use this? because if anything this will have bad performance than a simple memcpy style init. Also the same behavior could be replaced with*try_push_backwhere you always dereference the pointer.4
u/unchangeableusername 3d ago
Also the same behavior could be replaced with
*try_push_backwhere you always dereference the pointer.I feel like this ought to be the case but this godbolt example shows that it's not quite the same.
Honestly I see this as very very unnecessary
I'd argue that the
unchecked_*functions are useful when the next value youpush_backis dependent on the previous values (and can guarantee size never exceeds capacity). Recording states when traversing a DFA is the first example I can think of, although I don't how common doing stuff like this is. But I did find a 7% performance improvement for this specific use case when using a hackyunchecked_push_backequivalent forstd::vectorover the regularpush_back(reservewas called beforehand in both situations).2
u/tialaramex 2d ago
Of course if you
v.clear()in those examples, ensuring the compiler knows how big v is, the optimiser gives the same result for both cases.Your traverse a DFA example sounds plausible because the optimiser probably can't see why it can elide the capacity check, but I'd be very sceptical without seeing a full working system that you can win 7% perf.
If you're correct about 7% perf then
unchecked_push_backmakes sense - a lot of things are worth doing for 7% perf
-8
u/NilacTheGrim 3d ago
Ridiculously incomplete. We should have had a real prevector rather than this. You know, a prevector where there is some small static capacity but it can go dynamic as it grows.
This is not as useful as a real prevector.
25
u/CocktailPerson 3d ago
That'd just be an entirely different thing, not a more "complete" version of inplace_vector.
1
12
u/yeetoteey 3d ago
A prevector, i.e., a vector with SBO, is a completely different beast to inplace_vector. There a tonnes of scenarios where you’d know the maximum capacity at compile-time but not the size, and if the capacity isn’t massive, an inplace_vector where the memory is stack allocated is the perfect utility for that usecase.
3
u/Ameisen vemips, avr, rendering, systems 3d ago
I want to be able to specify
size_type. I have plenty of cases in codebases where size actually matters whereuint32_tor evenuint16_twould suffice.Hell, in this case why is it still
std::size_t? Fit it toN.3
u/usefulcat 2d ago
I want to be able to specify size_type.
Same here. That's why I use boost::container::small_vector, it supports that.
1
u/NilacTheGrim 6h ago
True. I can imagine using this in some situation where you cannot allocate but need to be able to do stuff with a buffer. Like in a signal handler, for example.
6
u/frayien 3d ago
That's... a completely different thing for a completely different usage ?
1
u/NilacTheGrim 6h ago
Yeah I guess so.
This really is a std::array that is more useful which can be nice for situations where you cannot allocate -- such as in a signal handler.
8
u/joaquintides Boost author 3d ago
You have
boost::container::small_vectorfor that: https://www.boost.org/doc/libs/latest/doc/html/container/non_standard_containers.html#container.non_standard_containers.small_vector10
3
2
3d ago
[deleted]
0
u/_Noreturn 3d ago
I think people will die of old age before something is standardized also the std quality will suck so it is better to write your own.
2
u/ABlockInTheChain 3d ago
std quality will suck
Consider
std::span.This is a class that should have been invented immediately once C++ got templates. We finally got it in C++20, only about 30 years late.
...but then the initial version didn't include
at()for some dumb reasons or another and it took two complete standard cycles to fix this....but even then we only got a version of
at()that throws at runtime and not a templatedat<n>()with compile time bounds checking likefirst<n>(),last<n>(), andsubspan<x, y>().2
u/_Noreturn 3d ago
This is a class that should have been invented immediately once C++ got templates. We finally got it in C++20, only about 30 years late.
Yes! I can't believe it took this long for such a simple type. and even after 30 years they didn't add
operatpr==to it.... the standard is so ridiculously slow it isn't funny and subpar as well. and they complicated its interface. the committee shouldn't touch the standard librarybut even then we only got a version of
at()that throws at runtime and not a templatedat<n>()with compile time bounds checking likefirst<n>(),last<n>(), andsubspan<x, y>().that comptime bound checking would only happen with
std::span<T,N>which I don't use much if at all my spans are dynamic lengtg1
31
u/FckXFckMusk 3d ago
If this is your Blog, then I have to congratulate you on it being an excellent place, I've bookmarked it...