--- title: "P3933R1:constexpr hive" document: p3933r1 date: 2026-05-12 audience: LEWG Library Evolution reply-to: - "Hana Dusíková" - "NylteJ" paper-type: proposal --- Number: P3933R1 Date: 2026-05-08 Audience: [Library Evolution](mailto:Library Evolution (YOU-NEED-JAVASCRIPT-ENABLED) #TGlicmFyeSZuYnNwO0V2b2x1dGlvbiA8bGliLWV4dEBsaXN0cy5pc29jcHAub3JnPj9zdWJqZWN0PVAzOTMzUjE6IGNvbnN0ZXhwciBoaXZl) Target: C++29 Author: [Hana Dusíková](mailto:hana dusikova (YOU-NEED-JAVASCRIPT-ENABLED) #SGFuYStEdXMlQzMlQURrb3YlQzMlQTEgPGhhbmlja2FAaGFuaWNrYS5uZXQ+P3N1YmplY3Q9UDM5MzNSMTogY29uc3RleHByIGhpdmU=) --- Thanks to NylteJ for providing implementation in MS STL. ◀︎ # P3933R1: constexpr hive This paper makes `std::hive` usable during constant evaluation, consistently with every other container type in the C++ standard library. It also resolves NB comment [`CZ 1-231 23.3.8 [hive] make std::hive constexpr`](https://github.com/cplusplus/nbballot/issues/802) which was raised against C++26, but LEWG decided against making hive `constexpr` in C++26 timeframe. This is almost identical paper as before, but it's aiming C++29. As before there is existing implementation, and it doesn't make sense to leave this one container non-`constexpr`. ## Motivation C++ users are often surprised by missing functionality available during constant evaluation, sometimes there is no real reason in the language, it's just no one wrote a paper making the thing `constexpr`. Anecdotally this is often surprise to Jason Turner's students when they start experimenting with `constexpr` code. This paper rectify this, and makes section [`[containers]`](https://eel.is/c++draft/containers) fully constexpr compatible. This is also design intent of [P3372: constexpr containers and adapters](https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2025/p3372r3.html) which made all containers marked constexpr, `std::hive` which got merged after this paper is not marked `constexpr`. We believe it's imperative `std::hive` to be `constexpr` as that's what is expected from the container part of the standard library. All implementations are aware of this intention, and hopefully didn't choose implementation strategy which would force them to break ABI to implement this paper. ## History of `std::hive` and `constexpr` - **2017-10-16**: The paper [P0447R4](https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0447r4.html) introducing `std::hive` under original "colony" name was first published. - **2019-08-23**: `constexpr` [`std::string`](https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p0980r1.pdf) and [`std::vector`](https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p1004r2.pdf) containers are adopted in C++20 draft just before feature freeze (huge thanks for the paper to Louis Dionne). This doesn't contain non-transient allocations, no memory allocation done in compile time can be transfered to runtime. - **2020-03-24**: Clang 10 with constexpr non-transient allocations support was released. - **2020-05-07**: GCC 10.1 with constexpr non-transient allocations support was released. - **2021-02-16**: LEWG [asked the author to consider](https://github.com/cplusplus/papers/issues/328#issuecomment-780011750) making the `std::hive` constexpr. - **2021-03-25**: [The paper in its 13th revision](https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2021/p0447r13.html) introduces appendix "why not constexpr?". There the author [describes their worries](https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2021/p0447r13.html#:~:text=Calculating%20a%20minus%20operation%20on%20stuff%20that's%20already%20in%20cache%20is%20about%20100x%20faster%20than%20making%20a%20call%20out%20to%20main%20memory%20for%20a%20compile%2Dtime%2Dstored%20value%20of%20this%20function%2C%20if%20that%20is%20necessary.) about lowering performance of the container by compiler deciding to replace calls like `size()` with a constant somewhere in memory, instead of doing effective calculation in cache. The author claims benchmarked `constexpr` implementation resulted in 2% slowdown which according them is unacceptable. Note this is not how the constant evaluation is specified, only constant-known values can be used in constant evaluation, so in order for constant evaluator to replace `size()` with a value in runtime it would need to have both iterators as constant-known values. Such replacements are by optimizer, not the constant evaluator.[Another worry of the author is bloated binary size when resources are precalculated](https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2022/p0447r18.html#:~:text=This%20suspicion%20was%20based%20on%20the%20substantial%20increases%20in%20executable%20size%20in%20the%20constexpr%20versions.). If you don't want to have precalculated resources in your binaries, then do not precalculate them. Compilers constant evaluates code only when requested thru `constexpr` variables initialization, `if consteval`, `template` arguments, and similar constructs. This is not happening for random `constexpr` code, and again this happens in most cases with optimizers taking adventage of code visibility. [*"If there were a mechanism which specified that for a given class instance, it's constexpr functions may not be evaluated at compile time, then I would give the go-ahead."*](https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2021/p0447r13.html#:~:text=If%20there%20were%20a%20mechanism%20which%20specified%20that%20for%20a%20given%20class%20instance%2C%20it's%20constexpr%20functions%20may%20not%20be%20evaluated%20at%20compile%20time%2C%20then%20I%20would%20give%20the%20go%2Dahead.) this is how constant evaluated code is behaving, any constant folding and inlining is done by optimizer regarding `constexpr`-ness. - **2021-11-03**: in [R17](https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2021/p0447r17.html) of the paper the appendix "why not constexpr?" is simplified by removing the list of claims about constexpr functions. - **2022-02-18**: in [R19](https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2022/p0447r19.html) of the paper authors proposes wait and see approach to making `std::hive` marked `constexpr`. - **2022-06-04**: in [R20](https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2022/p0447r20.html) The author says adding of `constexpr` can be done later before ABI freezes.Note: previous revision of this paper argued that change should be done in C++26, so we won't need to break ABI, LEWG decided to wait for more experience. - **2023-10-09**: in [R23](https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2023/p0447r23.html) authors updates the appendix again and says: [*"...Early compiler support was not good but this is improving steadily over time. I wasn't happy with having to label each and every function as constexpr, as this seemed to prompt some compilers to store some results at compile time even when the container wasn't being used as constexpr, bloating executable size and cache use..."*](https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2023/p0447r23.html#:~:text=Early%20compiler%20support,and%20cache%20use.), the author also argues necessity of usage of `reinterpret_cast` in various parts of the data structure to provide optimal code-gen and layout. Note: the reference implementation is using `reinterpret_cast` between two unrelated structs (which both contains array of bytes) and then casting them to `element_type` or the skiplist element type. Such `reinterpret_cast`-ing is a language undefined behaviour. Closest casting which is valid is to/from same type and byte storage, which is not allowed in constexpr yet, but can be replaced with usage of `union`. Author also states *"I am personally happier for `std::array` and `std::vector` to be the 'canaries in the coalmine' here"*. - **2023-11-10**: `std::hive` was forwarded by LEWG to LWG pending electronic polling (12/5/3/1/0). - **2023-11-10**: `std::hive` was forwarded with weak consensus to LWG in [electronic polling](https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2024/p3054r0.html#poll-2-send-p0447r26-introduction-of-stdhive-to-the-standard-library-to-library-working-group-for-c26) (8/4/3/4/2). - **2024-10-08**: [P3372R0](https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2024/p3372r0.html) "constexpr containers and adapters" (making *all* containers in the draft constexpr) got its design approved by LEWG (10/2/2/0/0) while requesting some fixes of problems found (getting non-const reference to const key of map's node, a language UB). - **2025-01-28**: [P3372R2](https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2024/p3372r2.html) "constexpr containers and adapters" was forwarded to LWG (12/8/2/0/0). - **2025-02-15**: [P3372R3](https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2025/p3372r3.html) and [P0447R28](https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2023/p0447r23.html) (`std::hive`) was adopted to C++26 during Hagenberg meeting. During the meeting I asked LWG co-chair what to do about `hive` and was told the best way to fix such inconsistency is to fill an NB comment as this meeting was also the feature freeze for C++26. - **2025-10-02**: [NB comments were published](https://sd.iso.org/documents/ui/#!/browse/iso/iso-iec-jtc-1/iso-iec-jtc-1-sc-22/library/5/8919481_LL/SoV%20and%20Collated%20Comment.1759421039736) for everyone to read. - **2025-11-03**: [LEWG on Kona meeting decided](https://github.com/cplusplus/nbballot/issues/801#issuecomment-3486983941) to support the NB comment CZ 1-231 to make `hive` `constexpr` (6/10/1/3/1, strong consensus in favor) and requested a paper to do so. Author of the original proposal was in the room. - **2025-12-14**: [Previous revision](https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2025/p3933r0.html) of this paper was published in December 2025 mailing per LEWG request. In the same mailing a response paper [P3945](https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2025/p3945r0.html) was published by the author of the original proposal. The paper has some technical comments (and argues the [UB is necessory for overaligned types](https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2025/p3945r0.html#:~:text=The%20undefined%20behaviour%20(UB)%20within%20the%20reference%20implementation%20mentioned%20in%20the%20paper%20is%20necessary%20to%20support%20overaligned%20types)), some STL prototype implementation comments, and arguing P3933 (this paper) is missing performance measurements of making something constexpr, no performance measurements were ever part of any revision of P0447, only the argument making hive constexpr lead to 2% downgrade of performance. In the same response paper author states [I never built a constexpr version of hive. I believed I had at the time](https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2025/p3945r0.html#:~:text=I%20never%20built%20a%20constexpr%20version%20of%20hive.%20I%20believed%20I%20had%20at%20the%20time). The constexpr implementation is not changing performance, only changes in the performance can be only because it's actualy avoiding UB, the prototype implementation [does provide the performance path with UB in case union and value_type are of same size](https://github.com/NylteJ/STL/blob/0d2575fa5748fab462ce985401ff7f94c89f78ff/stl/inc/hive#L1961C31-L1961C49). - **2026-02-09**: [updated STL prototype](https://github.com/NylteJ/STL) was published implementing both bitset and skipfield approaches independently based on the standard draft specification. - **2026-02-10**: [STL prototype](https://github.com/hanickadot/constexpr-hive-experiment) was extracted so it can be run outside of MS STL (tested with libstdc++ and libc++, the something author of P0447/P3945 was too hard to do to properly assess the new independent implementation) and against original author's own tests, it passes them (and passes them also in the interpreter itself), with notable exceptions of difference between the standard specification and original author's pfl implementation prototype ([like accepting mismatching iterator constness in hive constructor](https://github.com/mattreecebentley/plf_hive/blob/9f762762231c28d5f11cd3d06be2b802f4c071f0/plf_hive_test_suite.cpp#L279)). - **2025-02-10**: LEWG chair on a telecon meeting [decided](https://github.com/cplusplus/nbballot/issues/819#issuecomment-3941781441) to poll confirmation of the status quo (3/5/4/3/1, no consensus) and then, when was told we shouldn't vote to confirm status quo, reversed and retook the poll to change the status quo (1/7/3/2/2, no consensus), and then **without looking** at the paper (which has its implementation, previous LEWG support for the change, and the wording change is trivial) went directly to vote on "Resolve the NB comment CZ 1-231 by applying the paper P3933R0 and send to LWG for C++26 (to be confirmed by an EP)" (3/0/1/11/1, consensus against), with comments "too late to do any change" and original author's "I couldn't look at the implementation properly". - **2026-05-08**: This paper now targets C++29, and proposes also `get_iterator` functionality to be `constexpr`. ## Implementation [NylteJ](https://github.com/NylteJ) provided implementation of `constexpr std::hive` in his [fork of MS STL](https://github.com/NylteJ/STL/tree/hive), and informed me [under the issue](https://github.com/microsoft/STL/issues/5301) for `std::hive` implementation tracking in MS STL where Steven T. Lavavej made a note that whoever imlements it, should make it sure it can be `constexpr` compatible. According the author only problematic thing is `::get_iterator(const T *)` functionality. ### skiplist or bitset Original hive's author wrote a publication and implementation of performance improvement over proposed skiplist with a fast bitset. The STL implementation author implemented it too. ### `get_iterator` and comparing of unrelated pointers Wording requirement for `get_iterator` is to be linear with number of blocks allocated. During constant evaluation there is no global ordering of pointers (even in runtime it's just implementation defined behaviour). To implement this this paper depends on proposal of mine [P3852](https://isocpp.org/files/papers/P3852R1.html) or Herb's similar proposal [P3952](https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2026/p3952r0.pdf) which provides required functionality. Alternatively it can be implemented magically via builtin available only to the library. ## Wording Wording adds `constexpr` to all functions and member functions in [`[hive.syn]`](https://eel.is/c++draft/hive.syn) and [`[hive]`](https://eel.is/c++draft/hive). Following diff is made against version of C++26's draft from November 8th, so it probably won't contain changes applied after the Kona meeting, if there is a conflict, intention is to just add `constexpr` everywhere. :::wording ### Header synopsis [hive.syn] 🔗 #include // see [initializer.list.syn] #include // see [compare.syn] namespace std { struct hive_limits { size_t min; size_t max; constexpr hive_limits(size_t minimum, size_t maximum) noexcept : min(minimum), max(maximum) {} }; // [hive], class template hive template> class hive; template constexpr void swap(hive& x, hive& y) noexcept(noexcept(x.swap(y))); template constexpr typename hive::size_type erase(hive& c, const U& value); template constexpr typename hive::size_type erase_if(hive& c, Predicate pred); namespace pmr { template using hive = std::hive>; } } ::: :::wording ### Class template hive [hive] #### Overview [hive.overview] 1 # A hive is a type of sequence container that provides constant-time insertion and erasure operations . Storage is automatically managed in multiple memory blocks, referred to as *element blocks* . Insertion position is determined by the container, and insertion may re-use the memory locations of erased elements . 2 # Element blocks which contain elements are referred to as *active blocks* , those which do not are referred to as *reserved blocks* . Active blocks which become empty of elements are either deallocated or become reserved blocks . Reserved blocks become active blocks when they are used to store elements . A user can create additional reserved blocks by calling reserve . 3 # Erasures use unspecified techniques of constant time complexity to identify the memory locations of erased elements, which are subsequently skipped during iteration, as opposed to relocating subsequent elements during erasure . 4 # Active block capacities have an implementation-defined growth factor (which need not be integral), for example a new active block's capacity could be equal to the summed capacities of the pre-existing active blocks . 5 # Limits can be placed on both the minimum and maximum element capacities of element blocks, both by users and implementations . - (5.1)The minimum limit shall be no larger than the maximum limit. - (5.2)When limits are not specified by a user during construction, the implementation's default limits are used. - (5.3)The default limits of an implementation are not guaranteed to be the same as the minimum and maximum possible capacities for an implementation's element blocks. [*Note 1*: To allow latitude for both implementation-specific and user-directed optimization. — *end note*] The latter are defined as hard limits. The maximum hard limit shall be no larger than std::allocator_traits::max_size(). - (5.4)If user-specified limits are not within hard limits, or if the specified minimum limit is greater than the specified maximum limit, the behavior is undefined. - (5.5)An element block is said to be *within the bounds* of a pair of minimum/maximum limits when its capacity is greater-or-equal-to the minimum limit and less-than-or-equal-to the maximum limit. 6 # A hive conforms to the requirements for containers ( [container.reqmts] ), with the exception of operators == and != . A hive also meets the requirements of a reversible container ( [container.rev.reqmts] ), of an allocator-aware container ( [container.alloc.reqmts] ), and some of the requirements of a sequence container ( [sequence.reqmts] ) . Descriptions are provided here only for operations on hive that are not described in that table or for operations where there is additional semantic information . 7 # The iterators of hive meet the Cpp17BidirectionalIterator requirements but also model three_way_comparable . namespace std { template> class hive { public: // types using value_type = T; using allocator_type = Allocator; using pointer = allocator_traits::pointer; using const_pointer = allocator_traits::const_pointer; using reference = value_type&; using const_reference = const value_type&; using size_type = *implementation-defined*; // see [container.requirements] using difference_type = *implementation-defined*; // see [container.requirements] using iterator = *implementation-defined*; // see [container.requirements] using const_iterator = *implementation-defined*; // see [container.requirements] using reverse_iterator = std::reverse_iterator; // see [container.requirements] using const_reverse_iterator = std::reverse_iterator; // see [container.requirements] // [hive.cons], construct/copy/destroy constexpr hive() noexcept(noexcept(Allocator())) : hive(Allocator()) {} constexpr explicit hive(const Allocator&) noexcept; constexpr explicit hive(hive_limits block_limits) : hive(block_limits, Allocator()) {} constexpr hive(hive_limits block_limits, const Allocator&); constexpr explicit hive(size_type n, const Allocator& = Allocator()); constexpr hive(size_type n, hive_limits block_limits, const Allocator& = Allocator()); constexpr hive(size_type n, const T& value, const Allocator& = Allocator()); constexpr hive(size_type n, const T& value, hive_limits block_limits, const Allocator& = Allocator()); template constexpr hive(InputIterator first, InputIterator last, const Allocator& = Allocator()); template constexpr hive(InputIterator first, InputIterator last, hive_limits block_limits, const Allocator& = Allocator()); template<*container-compatible-range* R> constexpr hive(from_range_t, R&& rg, const Allocator& = Allocator()); template<*container-compatible-range* R> constexpr hive(from_range_t, R&& rg, hive_limits block_limits, const Allocator& = Allocator()); constexpr hive(const hive& x); constexpr hive(hive&&) noexcept; constexpr hive(const hive& x, const type_identity_t& alloc); constexpr hive(hive&&, const type_identity_t& alloc); constexpr hive(initializer_list il, const Allocator& = Allocator()); constexpr hive(initializer_list il, hive_limits block_limits, const Allocator& = Allocator()); constexpr ~hive(); constexpr hive& operator=(const hive& x); constexpr hive& operator=(hive&& x) noexcept(*see below*); constexpr hive& operator=(initializer_list); template constexpr void assign(InputIterator first, InputIterator last); template<*container-compatible-range* R> constexpr void assign_range(R&& rg); constexpr void assign(size_type n, const T& t); constexpr void assign(initializer_list); constexpr allocator_type get_allocator() const noexcept; // iterators constexpr iterator begin() noexcept; constexpr const_iterator begin() const noexcept; constexpr iterator end() noexcept; constexpr const_iterator end() const noexcept; constexpr reverse_iterator rbegin() noexcept; constexpr const_reverse_iterator rbegin() const noexcept; constexpr reverse_iterator rend() noexcept; constexpr const_reverse_iterator rend() const noexcept; constexpr const_iterator cbegin() const noexcept; constexpr const_iterator cend() const noexcept; constexpr const_reverse_iterator crbegin() const noexcept; constexpr const_reverse_iterator crend() const noexcept; // [hive.capacity], capacity constexpr bool empty() const noexcept; constexpr size_type size() const noexcept; constexpr size_type max_size() const noexcept; constexpr size_type capacity() const noexcept; constexpr void reserve(size_type n); constexpr void shrink_to_fit(); constexpr void trim_capacity() noexcept; constexpr void trim_capacity(size_type n) noexcept; constexpr hive_limits block_capacity_limits() const noexcept; static constexpr hive_limits block_capacity_default_limits() noexcept; static constexpr hive_limits block_capacity_hard_limits() noexcept; constexpr void reshape(hive_limits block_limits); // [hive.modifiers], modifiers template constexpr iterator emplace(Args&&... args); template constexpr iterator emplace_hint(const_iterator hint, Args&&... args); constexpr iterator insert(const T& x); constexpr iterator insert(T&& x); constexpr iterator insert(const_iterator hint, const T& x); constexpr iterator insert(const_iterator hint, T&& x); constexpr void insert(initializer_list il); template<*container-compatible-range* R> constexpr void insert_range(R&& rg); template constexpr void insert(InputIterator first, InputIterator last); constexpr void insert(size_type n, const T& x); constexpr iterator erase(const_iterator position); constexpr iterator erase(const_iterator first, const_iterator last); constexpr void swap(hive&) noexcept(*see below*); constexpr void clear() noexcept; // [hive.operations], hive operations constexpr void splice(hive& x); constexpr void splice(hive&& x); template> constexpr size_type unique(BinaryPredicate binary_pred = BinaryPredicate()); template> constexpr void sort(Compare comp = Compare()); constexpr iterator get_iterator(const_pointer p) noexcept; constexpr const_iterator get_iterator(const_pointer p) const noexcept; private: hive_limits *current-limits* = *implementation-defined*; // *exposition only* }; template>> hive(InputIterator, InputIterator, Allocator = Allocator()) -> hive<*iter-value-type*, Allocator>; template>> hive(InputIterator, InputIterator, hive_limits, Allocator = Allocator()) -> hive<*iter-value-type*, Allocator>; template>> hive(from_range_t, R&&, Allocator = Allocator()) -> hive, Allocator>; template>> hive(from_range_t, R&&, hive_limits, Allocator = Allocator()) -> hive, Allocator>; } #### Constructors, copy, and assignment [hive.cons] 🔗 constexpr explicit hive(const Allocator&) noexcept; 1 # Effects : Constructs an empty hive , using the specified allocator . 2 # Complexity : Constant . 🔗 constexpr hive(hive_limits block_limits, const Allocator&); 3 # Effects : Constructs an empty hive , using the specified allocator . Initializes *current-limits* with block_limits . 4 # Complexity : Constant . 🔗 constexpr explicit hive(size_type n, const Allocator& = Allocator()); constexpr hive(size_type n, hive_limits block_limits, const Allocator& = Allocator()); 5 # Preconditions : T is Cpp17DefaultInsertable into hive . 6 # Effects : Constructs a hive with n default-inserted elements, using the specified allocator . If the second overload is called, also initializes *current-limits* with block_limits . 7 # Complexity : Linear in n . 🔗 constexpr hive(size_type n, const T& value, const Allocator& = Allocator()); constexpr hive(size_type n, const T& value, hive_limits block_limits, const Allocator& = Allocator()); 8 # Preconditions : T is Cpp17CopyInsertable into hive . 9 # Effects : Constructs a hive with n copies of value , using the specified allocator . If the second overload is called, also initializes *current-limits* with block_limits . 10 # Complexity : Linear in n . 🔗 template constexpr hive(InputIterator first, InputIterator last, const Allocator& = Allocator()); template constexpr hive(InputIterator first, InputIterator last, hive_limits block_limits, const Allocator& = Allocator()); 11 # Effects : Constructs a hive equal to the range [ first, last ), using the specified allocator . If the second overload is called, also initializes *current-limits* with block_limits . 12 # Complexity : Linear in distance(first, last) . 🔗 template<*container-compatible-range* R> constexpr hive(from_range_t, R&& rg, const Allocator& = Allocator()); template<*container-compatible-range* R> constexpr hive(from_range_t, R&& rg, hive_limits block_limits, const Allocator& = Allocator()); 13 # Effects : Constructs a hive object with the elements of the range rg , using the specified allocator . If the second overload is called, also initializes *current-limits* with block_limits . 14 # Complexity : Linear in ranges​::​distance(rg) . 🔗 constexpr hive(const hive& x); constexpr hive(const hive& x, const type_identity_t& alloc); 15 # Preconditions : T is Cpp17CopyInsertable into hive . 16 # Effects : Constructs a hive object with the elements of x . If the second overload is called, uses alloc . Initializes *current-limits* with x.*current-limits* . 17 # Complexity : Linear in x.size() . 🔗 constexpr hive(hive&& x) noexcept; constexpr hive(hive&& x, const type_identity_t& alloc); 18 # Preconditions : For the second overload, when allocator_traits​::​is_always_equal​::​value is false , T meets the Cpp17MoveInsertable requirements . 19 # Effects : When the first overload is called, or the second overload is called and alloc == x.get_allocator() is true , *current-limits* is set to x.*current-limits* and each element block is moved from x into *this . Pointers and references to the elements of x now refer to those same elements but as members of *this . Iterators referring to the elements of x will continue to refer to their elements, but they now behave as iterators into *this . If the second overload is called and alloc == x.get_allocator() is false , each element in x is moved into *this . References, pointers and iterators referring to the elements of x , as well as the past-the-end iterator of x , are invalidated . 20 # Postconditions : x.empty() is true . 21 # Complexity : If the second overload is called and alloc == x.get_allocator() is false , linear in x.size() . Otherwise constant . 🔗 constexpr hive(initializer_list il, const Allocator& = Allocator()); constexpr hive(initializer_list il, hive_limits block_limits, const Allocator& = Allocator()); 22 # Preconditions : T is Cpp17CopyInsertable into hive . 23 # Effects : Constructs a hive object with the elements of il , using the specified allocator . If the second overload is called, also initializes *current-limits* with block_limits . 24 # Complexity : Linear in il.size() . 🔗 constexpr hive& operator=(const hive& x); 25 # Preconditions : T is Cpp17CopyInsertable into hive and Cpp17CopyAssignable . 26 # Effects : All elements in *this are either copy-assigned to, or destroyed . All elements in x are copied into *this . > [ > > Note 1 > > : > > *current-limits* > > is unchanged > > . > > — > > end note > > ] 27 # Complexity : Linear in size() + x.size() . 🔗 constexpr hive& operator=(hive&& x) noexcept(allocator_traits::propagate_on_container_move_assignment::value || allocator_traits::is_always_equal::value); 28 # Preconditions : When (allocator_traits::propagate_on_container_move_assignment::value || allocator_traits::is_always_equal::value) is false , T is Cpp17MoveInsertable into hive and Cpp17MoveAssignable . 29 # Effects : Each element in *this is either move-assigned to, or destroyed . When (allocator_traits::propagate_on_container_move_assignment::value || get_allocator() == x.get_allocator()) is true , *current-limits* is set to x.*current-limits* and each element block is moved from x into *this . Pointers and references to the elements of x now refer to those same elements but as members of *this . Iterators referring to the elements of x will continue to refer to their elements, but they now behave as iterators into *this , not into x . When (allocator_traits::propagate_on_container_move_assignment::value || get_allocator() == x.get_allocator()) is false , each element in x is moved into *this . References, pointers and iterators referring to the elements of x , as well as the past-the-end iterator of x , are invalidated . 30 # Postconditions : x.empty() is true . 31 # Complexity : Linear in size() . If (allocator_traits::propagate_on_container_move_assignment::value || get_allocator() == x.get_allocator()) is false , also linear in x.size() . #### Capacity [hive.capacity] 🔗 constexpr size_type capacity() const noexcept; 1 # Returns : The total number of elements that *this can hold without requiring allocation of more element blocks . 2 # Complexity : Constant . 🔗 constexpr void reserve(size_type n); 3 # Effects : If n <= capacity() is true , there are no effects . Otherwise increases capacity() by allocating reserved blocks . 4 # Postconditions : capacity() >= n is true . 5 # Throws : length_error if n > max_size() , as well as any exceptions thrown by the allocator . 6 # Complexity : Linear in the number of reserved blocks allocated . 7 # Remarks : The size of the sequence is not changed . All references, pointers, and iterators referring to elements in *this , as well as the past-the-end iterator, remain valid . 🔗 constexpr void shrink_to_fit(); 8 # Preconditions : T is Cpp17MoveInsertable into hive . 9 # Effects : shrink_to_fit is a non-binding request to reduce capacity() to be closer to size() . > [ > > Note 1 > > : > > The request is non-binding > to allow latitude for implementation-specific optimizations > > . > > — > > end note > > ] It does not increase capacity() , but may reduce capacity() . It may reallocate elements . If capacity() is already equal to size() , there are no effects . If an exception is thrown during allocation of a new element block, capacity() may be reduced and reallocation may occur . Otherwise if an exception is thrown, the effects are unspecified . 10 # Complexity : If reallocation happens, linear in the size of the sequence . 11 # Remarks : If reallocation happens, the order of the elements in *this may change and all references, pointers, and iterators referring to the elements in *this , as well as the past-the-end iterator, are invalidated . 🔗 constexpr void trim_capacity() noexcept; constexpr void trim_capacity(size_type n) noexcept; 12 # Effects : For the first overload, all reserved blocks are deallocated, and capacity() is reduced accordingly . For the second overload, capacity() is reduced to no less than n . 13 # Complexity : Linear in the number of reserved blocks deallocated . 14 # Remarks : All references, pointers, and iterators referring to elements in *this , as well as the past-the-end iterator, remain valid . 🔗 constexpr hive_limits block_capacity_limits() const noexcept; 15 # Returns : *current-limits* . 16 # Complexity : Constant . 🔗 static constexpr hive_limits block_capacity_default_limits() noexcept; 17 # Returns : A hive_limits struct with the min and max members set to the implementation's default limits . 18 # Complexity : Constant . 🔗 static constexpr hive_limits block_capacity_hard_limits() noexcept; 19 # Returns : A hive_limits struct with the min and max members set to the implementation's hard limits . 20 # Complexity : Constant . 🔗 constexpr void reshape(hive_limits block_limits); 21 # Preconditions : T is Cpp17MoveInsertable into hive . 22 # Effects : For any active blocks not within the bounds of block_limits , the elements within those active blocks are reallocated to new or existing element blocks which are within the bounds . Any element blocks not within the bounds of block_limits are deallocated . If an exception is thrown during allocation of a new element block, capacity() may be reduced, reallocation may occur, and *current-limits* may be assigned a value other than block_limits . Otherwise block_limits is assigned to *current-limits* . If any other exception is thrown the effects are unspecified . 23 # Postconditions : size() is unchanged . 24 # Complexity : Linear in the number of element blocks in *this . If reallocation happens, also linear in the number of elements reallocated . 25 # Remarks : This operation may change capacity() . If reallocation happens, the order of the elements in *this may change . Reallocation invalidates all references, pointers, and iterators referring to the elements in *this , as well as the past-the-end iterator . > [ > > Note 2 > > : > > If no reallocation happens, they remain valid > > . > > — > > end note > > ] #### Modifiers [hive.modifiers] 🔗 template constexpr iterator emplace(Args&&... args); template constexpr iterator emplace_hint(const_iterator hint, Args&&... args); 1 # Preconditions : T is Cpp17EmplaceConstructible into hive from args . 2 # Effects : Inserts an object of type T constructed with std​::​forward(args)... . The hint parameter is ignored . If an exception is thrown, there are no effects . > [ > > Note 1 > > : > > args > > can directly or indirectly refer to a value in > > *this > > . > > — > > end note > > ] 3 # Returns : An iterator that points to the new element . 4 # Complexity : Constant . Exactly one object of type T is constructed . 5 # Remarks : Invalidates the past-the-end iterator . 🔗 constexpr iterator insert(const T& x); constexpr iterator insert(const_iterator hint, const T& x); constexpr iterator insert(T&& x); constexpr iterator insert(const_iterator hint, T&& x); 6 # Effects : Equivalent to: return emplace(std​::​forward(x)); > [ > > Note 2 > > : > > The > > hint > > parameter is ignored > > . > > — > > end note > > ] 🔗 constexpr void insert(initializer_list rg); template<*container-compatible-range* R> constexpr void insert_range(R&& rg); 7 # Preconditions : T is Cpp17EmplaceInsertable into hive from *ranges​::​begin(rg) . rg and *this do not overlap . 8 # Effects : Inserts copies of elements in rg . Each iterator in the range rg is dereferenced exactly once . 9 # Complexity : Linear in the number of elements inserted . Exactly one object of type T is constructed for each element inserted . 10 # Remarks : If an element is inserted, invalidates the past-the-end iterator . 🔗 constexpr void insert(size_type n, const T& x); 11 # Preconditions : T is Cpp17CopyInsertable into hive . 12 # Effects : Inserts n copies of x . 13 # Complexity : Linear in n . Exactly one object of type T is constructed for each element inserted . 14 # Remarks : If an element is inserted, invalidates the past-the-end iterator . 🔗 template constexpr void insert(InputIterator first, InputIterator last); 15 # Effects : Equivalent to insert_range(ranges​::​subrange(first, last)) . 🔗 constexpr iterator erase(const_iterator position); constexpr iterator erase(const_iterator first, const_iterator last); 16 # Complexity : Linear in the number of elements erased . Additionally, if any active blocks become empty of elements as a result of the function call, at worst linear in the number of element blocks . 17 # Remarks : Invalidates references, pointers and iterators referring to the erased elements . An erase operation that erases the last element in *this also invalidates the past-the-end iterator . 🔗 constexpr void swap(hive& x) noexcept(allocator_traits::propagate_on_container_swap::value || allocator_traits::is_always_equal::value); 18 # Effects : Exchanges the contents, capacity() , and *current-limits* of *this with that of x . 19 # Complexity : Constant . #### Operations [hive.operations] 1 # In this subclause, arguments for a template parameter named Predicate or BinaryPredicate shall meet the corresponding requirements in [algorithms.requirements] . The semantics of i + n and i - n , where i is an iterator into the hive and n is an integer, are the same as those of next(i, n) and prev(i, n) , respectively . For sort , the definitions and requirements in [alg.sorting] apply . 🔗 constexpr void splice(hive& x); constexpr void splice(hive&& x); 2 # Preconditions : get_allocator() == x.get_allocator() is true . 3 # Effects : If addressof(x) == this is true , the behavior is erroneous and there are no effects . Otherwise, inserts the contents of x into *this and x becomes empty . Pointers and references to the moved elements of x now refer to those same elements but as members of *this . Iterators referring to the moved elements continue to refer to their elements, but they now behave as iterators into *this , not into x . 4 # Throws : length_error if any of x 's active blocks are not within the bounds of *current-limits* . 5 # Complexity : Linear in the sum of all element blocks in x plus all element blocks in *this . 6 # Remarks : Reserved blocks in x are not transferred into *this . If addressof(x) == this is false , invalidates the past-the-end iterator for both x and *this . 🔗 template> constexpr size_type unique(BinaryPredicate binary_pred = BinaryPredicate()); 7 # Preconditions : binary_pred is an equivalence relation . 8 # Effects : Erases all but the first element from every consecutive group of equivalent elements . That is, for a nonempty hive , erases all elements referred to by the iterator i in the range [ begin() + 1, end() ) for which binary_pred(*i, *(i - 1)) is true . 9 # Returns : The number of elements erased . 10 # Throws : Nothing unless an exception is thrown by the predicate . 11 # Complexity : If empty() is false , exactly size() - 1 applications of the corresponding predicate, otherwise no applications of the predicate . 12 # Remarks : Invalidates references, pointers, and iterators referring to the erased elements . If the last element in *this is erased, also invalidates the past-the-end iterator . 🔗 template> constexpr void sort(Compare comp = Compare()); 13 # Preconditions : T is Cpp17MoveInsertable into hive , Cpp17MoveAssignable , and Cpp17Swappable . 14 # Effects : Sorts *this according to the comp function object . If an exception is thrown, the order of the elements in *this is unspecified . 15 # Complexity : O(NlogN) comparisons, where N is size() . 16 # Remarks : May allocate . References, pointers, and iterators referring to elements in *this , as well as the past-the-end iterator, may be invalidated . > [ > > Note 1 > > : > > Not required to be stable > > [algorithm.stable] > > . > > — > > end note > > ] 🔗 constexpr iterator get_iterator(const_pointer p) noexcept; constexpr const_iterator get_iterator(const_pointer p) const noexcept; 17 # Preconditions : p points to an element in *this . 18 # Returns : An iterator or const_iterator pointing to the same element as p . 19 # Complexity : Linear in the number of active blocks in *this . #### Erasure [hive.erasure] 🔗 template constexpr typename hive::size_type erase(hive& c, const U& value); 1 # Effects : Equivalent to: return erase_if(c, [&](const auto& elem) -> bool { return elem == value; }); 🔗 template constexpr typename hive::size_type erase_if(hive& c, Predicate pred); 2 # Effects : Equivalent to: auto original_size = c.size(); for (auto i = c.begin(), last = c.end(); i != last; ) { if (pred(*i)) { i = c.erase(i); } else { ++i; } } return original_size - c.size(); ::: ### Feature test macro #### Header synopsis [version.syn] ``` #define __cpp_lib_constexpr_hive 2026??L // also in ```