microsoft
P0447R28 `<hive>`
WG21-P0447R28 <hive>
WG21-P3923R0 Additional NB Comment Resolutions For Kona 2025 (sections 2.2, 2.3, 2.4, 2.5)
LWG-4233 The helper lambda of std::erase for hive should specify return type as bool
LWG-4234 Including <hive> doesn't provide std::begin/end
LWG-4318 Have hive::erase_if reevaluate end() to avoid UB
Feature-test macro (expected):
#define __cpp_lib_hive 202502L
We need to teach the IDE about this new extensionless header.
Note: We're focused on implementing the remaining library-only features in C++23. Until that's done, we will NOT be accepting PRs for C++26 features.
@hanickadot mentioned that there will likely be an NB comment for C++26 to make std::hive constexpr, so if we begin implementing this before that lands, we should consider anticipating it by using constexpr-compatible techniques (e.g. unions instead of reinterpret_casts).
I'm trying to implement a preliminary version in https://github.com/NylteJ/STL/tree/hive.
This is really awesome @NylteJ! Did you run into any problem with making it constexpr compatible?
Well, there are a few issues, but they should be resolvable. For example, because pointers to union members can’t be converted to pointers to the union itself during constant evaluation, get_iterator may need some fixes that ~~slightly~~ exceed the complexity specified by the standard.
AFAIK, the core code paths are all constexpr‑friendly (get_iterator needs some fixes, but that’s about it). The main things missing are features provided in C++26 (e.g., unions that are always trivially default-constructible and destructible). The biggest issue may be the tests, though I’ve just manually verified that the most basic ones work correctly.
get_iterator may need some fixes that slightly exceed the complexity specified by the standard.
Hm, complexity as time complexity or logic complexity?
@NylteJ LEWG voted on NB comment making hive constexpr, but I need to author a paper for next meeting. Would you like to be a co-author? I only need you to document all things which you needed to do, especially if there is any deviation from standard specification (I don't think there will be any really needed, but you have the implementation experience).
get_iterator may need some fixes that slightly exceed the complexity specified by the standard.
Hm, complexity as time complexity or logic complexity?
Time complexity - sorry for the ambiguity.
~~More specifically, the standard specifies its time complexity as “linear in the number of active blocks in *this”. In non-constant evaluation, that’s perfectly fine: we can use reinterpret_cast to convert the input into a pointer to the union, and once the relevant block is located, a simple pointer subtraction gives the element’s index. But in constant evaluation, since reinterpret_cast isn’t allowed, we have to search through the block to find the element with the same address, which introduces extra cost linear in the number of elements in the block.
There might be ways to avoid this overhead, but I’m not aware of any at the moment.
Edit: we could use binary search to reduce the additional complexity to logarithmic (given that the hard limit is at most 65535, this is almost constant). But I still haven’t found a way to eliminate the overhead completely.~~
@NylteJ LEWG voted on NB comment making hive constexpr, but I need to author a paper for next meeting. Would you like to be a co-author? I only need you to document all things which you needed to do, especially if there is any deviation from standard specification (I don't think there will be any really needed, but you have the implementation experience).
Yes, I’d be happy to.
@hanickadot I’ve implemented a simple constexpr version at https://github.com/NylteJ/STL/tree/hive_constexpr and manually tested the main scenarios on both Clang and MSVC.
The good news is everything works well except for get_iterator. Clang has some bugs in the test code, but with workarounds I’ve confirmed that the issues aren’t in the product code. I believe more complex cases should also work fine.
The bad news is get_iterator appears completely unable to run in constant evaluation while meeting the specified complexity. The reason is that the “implementation-defined strict total order comparison over pointers” isn’t available in constant evaluation ([expr.const]/10.25, [expr.rel]/4, 5). I had assumed it was allowed - clearly I was wrong, and my earlier oversimplified tests missed this. As a result, there’s no way to determine whether a pointer belongs to a given element block in constant time.
If we ignore the complexity requirement, the function is implementable since pointer equality comparisons are always allowed ([expr.eq]/3, as long as we don’t compare a past-the-end pointer with a begin pointer). But that would make the complexity linear in the total number of elements.
Unless I’ve missed something, I believe this is the only required change to the standard.
@NylteJ I can't find any email to contact you, can you write me an email? You can find it in any of my papers (for example in this one https://isocpp.org/files/papers/N5011.html) on top of the left menu, just click on my name (with browser with enabled javascript).
I think I can live without get_iterator ... it's not really thing I really care about, and I have an idea how to allow it later with some additional library functionality.