[RFC] libstdc++: Implement P0447R28 std::hive

Tomasz Kaminski tkaminsk@redhat.com
Thu Oct 1 14:33:54 GMT 2026


On Wed, Sep 30, 2026 at 4:52 PM Tomasz Kamiński <tkaminsk@redhat.com> wrote:

> This patch implements std::hive for C++26 as specified in P0447R28,
> except the sort member function.
>
> The tracking of the occupied and empty slot inside of single block, is done
> by the combination of low complexity skipfield (_BlockT::_M_skipfield), and
> double linked list of the free nodes stored inside first empty slot
> (_M_free).
> As each slot need to store position of the previous/next entry, we
> determine
> the _SizeT for the _BlockT, based on the size of the element _Tp. Limiting
> to
> half of sizeof(_Tp) or 1. As the skipfied is always byte sized (to reduce
> overhead for each element elements), larger block sized are encoded into
> multiple sequential bytes (see __hive::_Counter).
> We should explore the bitset stacking [1][2] as the alternative for both of
> above, as this would allow us to store elements of _Tp directly (instead of
> union with free node), and enable direct use of memcopy to insert or
> override elements.
> Additionally currently blocks does not store the number of occupied/free
> elements (only capacity), which prevents us from having no-op delete for
> trivially destructible types, and make insertion less optimal.
>
> The block metadata, skipfields and elements are sharing single allocation,
> where the block and skipfields are placed in storage provided by initial
> elements (_BlockT::_S_extra_slots). The pointer to initial allocation is
> stored in the block (_M_mem) and offset on each access (_M_elem). This
> allow
> the pointer to be eliminated completely if _BlockT is guaranteed to share
> same
> address, however requires extra computation on each access.
> We should measure effector storing pointer to start of elements and offset
> for the start of allocation instead (unsigned char member).
> Note that the above approach is not constexpr-compatible, as it requires
> reinterpret_cast and placement new on storage of object from different
> type.
> However, we could use a start offset with value zero to indicate separate
> allocation for blocks, elements and skipfield. This would required adding
> a separate skipfield pointer. Treating this as separate mode (and not
> constexpr path), will still work we support non-transient allocations,
> as runtime would be able to recognized and handle it accordingly.
>
This make iteration 30-40% faster, so clear win.  Changed the implementation
on forget to use that:
https://forge.sourceware.org/gcc/gcc/pulls/224/commits/1a73c796eb6742e5aec02d9203f4588ae6eaf678
.

>
> The implementation currently keeps all reserved blocks (extra capacity)
> by default, until they removal is explicitly requested (shrink_to_fit,
> trim_capacity) or required to meet invariants (change of allocator or
> limits: reshape, move assignment). The reference implementation reduces
> the number of reserved blocks, and keeps only last two. This is again
> something to investigate.
>
> When the user specifies invalid limits (outside of hard limits), the
> standard makes operation erroneous with implementation-defined behavior.
> This patch asserts on that, and then:
> * use default limits, if limits does not for a range max < min,
> * otherwise clamp the limits to the hard limits
>
> Finally, the hive implements unconditional erase for range of iterator,
> in terms of erase with always true predicate (_M_block_erase_if) with
> always true functor. For that purpose we define _Always functor in the
> predefined_ops.h, as such utility is generally useful.
>
> [1]
> https://discourse.llvm.org/t/std-new-information-for-implementors/89125
> [2] https://plflib.org/matt_bentley_-_bitset_stacking.pdf
>
> libstdc++-v3/ChangeLog:
>
>         * include/Makefile.am: Add std/hive and bits/hive.h headers.
>         * include/Makefile.in: Regenerate.
>         * include/bits/predefined_ops.h (__gnucxx::__ops::_Always):
>         Define.
>         * include/bits/version.def (hive): Define with value zero
>         and no-std mode.
>         * include/bits/version.h: Regenerate.
>         * include/bits/hive.h: New file.
>         * include/std/hive: New file.
>         * testsuite/23_containers/hive/access.cc: New test.
>         * testsuite/23_containers/hive/assign.cc: New test.
>         * testsuite/23_containers/hive/capacity.cc: New test.
>         * testsuite/23_containers/hive/copy_alloc.cc: New test.
>         * testsuite/23_containers/hive/ctor.cc: New test.
>         * testsuite/23_containers/hive/erasure.cc: New test.
>         * testsuite/23_containers/hive/insert.cc: New test.
>         * testsuite/23_containers/hive/move_alloc.cc: New test.
>         * testsuite/23_containers/hive/splice.cc: New test.
>         * testsuite/23_containers/hive/throws.cc: New test.
> ---
> The corresponding pull request can be also found on forge:
> https://forge.sourceware.org/gcc/gcc/pulls/224
>
> Some open question, to answer:
> * should I merge bits/hive.h into std/hive, or create
>   separate bits/hive.tcc
> * is __gnucxx::__ops::_Always OK to add in all standard
>   modes
>
> This is send as RFC, but I do not see issue in merging it to
> master in the current form (without exposing FTM).
>
>  libstdc++-v3/include/Makefile.am              |    2 +
>  libstdc++-v3/include/Makefile.in              |    2 +
>  libstdc++-v3/include/bits/hive.h              | 2238 +++++++++++++++++
>  libstdc++-v3/include/bits/predefined_ops.h    |   11 +
>  libstdc++-v3/include/bits/version.def         |    9 +
>  libstdc++-v3/include/bits/version.h           |    9 +
>  libstdc++-v3/include/std/hive                 |   55 +
>  .../testsuite/23_containers/hive/access.cc    |   67 +
>  .../testsuite/23_containers/hive/assign.cc    |  158 ++
>  .../testsuite/23_containers/hive/capacity.cc  |  383 +++
>  .../23_containers/hive/copy_alloc.cc          |  335 +++
>  .../testsuite/23_containers/hive/ctor.cc      |  238 ++
>  .../testsuite/23_containers/hive/erasure.cc   |  291 +++
>  .../testsuite/23_containers/hive/insert.cc    |   93 +
>  .../23_containers/hive/move_alloc.cc          |  444 ++++
>  .../testsuite/23_containers/hive/ranges.cc    |   86 +
>  .../testsuite/23_containers/hive/splice.cc    |  200 ++
>  .../testsuite/23_containers/hive/throws.cc    |  352 +++
>  18 files changed, 4973 insertions(+)
>  create mode 100644 libstdc++-v3/include/bits/hive.h
>  create mode 100644 libstdc++-v3/include/std/hive
>  create mode 100644 libstdc++-v3/testsuite/23_containers/hive/access.cc
>  create mode 100644 libstdc++-v3/testsuite/23_containers/hive/assign.cc
>  create mode 100644 libstdc++-v3/testsuite/23_containers/hive/capacity.cc
>  create mode 100644 libstdc++-v3/testsuite/23_containers/hive/copy_alloc.cc
>  create mode 100644 libstdc++-v3/testsuite/23_containers/hive/ctor.cc
>  create mode 100644 libstdc++-v3/testsuite/23_containers/hive/erasure.cc
>  create mode 100644 libstdc++-v3/testsuite/23_containers/hive/insert.cc
>  create mode 100644 libstdc++-v3/testsuite/23_containers/hive/move_alloc.cc
>  create mode 100644 libstdc++-v3/testsuite/23_containers/hive/ranges.cc
>  create mode 100644 libstdc++-v3/testsuite/23_containers/hive/splice.cc
>  create mode 100644 libstdc++-v3/testsuite/23_containers/hive/throws.cc
>
> diff --git a/libstdc++-v3/include/Makefile.am
> b/libstdc++-v3/include/Makefile.am
> index 3c30aa21d6b..60b795b0379 100644
> --- a/libstdc++-v3/include/Makefile.am
> +++ b/libstdc++-v3/include/Makefile.am
> @@ -79,6 +79,7 @@ std_headers = \
>         ${std_srcdir}/forward_list \
>         ${std_srcdir}/fstream \
>         ${std_srcdir}/future \
> +       ${std_srcdir}/hive \
>         ${std_srcdir}/inplace_vector \
>         ${std_srcdir}/iomanip \
>         ${std_srcdir}/ios \
> @@ -231,6 +232,7 @@ bits_headers = \
>         ${bits_srcdir}/gslice_array.h \
>         ${bits_srcdir}/hashtable.h \
>         ${bits_srcdir}/hashtable_policy.h \
> +       ${bits_srcdir}/hive.h \
>         ${bits_srcdir}/indirect.h \
>         ${bits_srcdir}/indirect_array.h \
>         ${bits_srcdir}/ios_base.h \
> diff --git a/libstdc++-v3/include/Makefile.in
> b/libstdc++-v3/include/Makefile.in
> index d081481293f..5d09c2b826f 100644
> --- a/libstdc++-v3/include/Makefile.in
> +++ b/libstdc++-v3/include/Makefile.in
> @@ -438,6 +438,7 @@ std_freestanding = \
>  @GLIBCXX_HOSTED_TRUE@  ${std_srcdir}/forward_list \
>  @GLIBCXX_HOSTED_TRUE@  ${std_srcdir}/fstream \
>  @GLIBCXX_HOSTED_TRUE@  ${std_srcdir}/future \
> +@GLIBCXX_HOSTED_TRUE@  ${std_srcdir}/hive \
>  @GLIBCXX_HOSTED_TRUE@  ${std_srcdir}/inplace_vector \
>  @GLIBCXX_HOSTED_TRUE@  ${std_srcdir}/iomanip \
>  @GLIBCXX_HOSTED_TRUE@  ${std_srcdir}/ios \
> @@ -587,6 +588,7 @@ bits_freestanding = \
>  @GLIBCXX_HOSTED_TRUE@  ${bits_srcdir}/gslice_array.h \
>  @GLIBCXX_HOSTED_TRUE@  ${bits_srcdir}/hashtable.h \
>  @GLIBCXX_HOSTED_TRUE@  ${bits_srcdir}/hashtable_policy.h \
> +@GLIBCXX_HOSTED_TRUE@  ${bits_srcdir}/hive.h \
>  @GLIBCXX_HOSTED_TRUE@  ${bits_srcdir}/indirect.h \
>  @GLIBCXX_HOSTED_TRUE@  ${bits_srcdir}/indirect_array.h \
>  @GLIBCXX_HOSTED_TRUE@  ${bits_srcdir}/ios_base.h \
> diff --git a/libstdc++-v3/include/bits/hive.h
> b/libstdc++-v3/include/bits/hive.h
> new file mode 100644
> index 00000000000..d3a951dbe23
> --- /dev/null
> +++ b/libstdc++-v3/include/bits/hive.h
> @@ -0,0 +1,2238 @@
> +// Hive implementation -*- C++ -*-
> +
> +// Copyright (C) 2026 Free Software Foundation, Inc.
> +//
> +// This file is part of the GNU ISO C++ Library.  This library is free
> +// software; you can redistribute it and/or modify it under the
> +// terms of the GNU General Public License as published by the
> +// Free Software Foundation; either version 3, or (at your option)
> +// any later version.
> +
> +// This library is distributed in the hope that it will be useful,
> +// but WITHOUT ANY WARRANTY; without even the implied warranty of
> +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
> +// GNU General Public License for more details.
> +
> +// Under Section 7 of GPL version 3, you are granted additional
> +// permissions described in the GCC Runtime Library Exception, version
> +// 3.1, as published by the Free Software Foundation.
> +
> +// You should have received a copy of the GNU General Public License and
> +// a copy of the GCC Runtime Library Exception along with this program;
> +// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
> +// <http://www.gnu.org/licenses/>.
> +
> +/** @file bits/hive.h
> + *  This is an internal header file, included by other library headers.
> + *  Do not attempt to use it directly. @headername{hive}
> + */
> +
> +#ifndef _BITS_HIVE_H
> +#define _BITS_HIVE_H 1
> +
> +#ifdef __glibcxx_hive // C++ >= 26
> +
> +#include <bits/align.h>
> +#include <bits/stl_iterator_base_funcs.h>
> +#include <bits/stdexcept_throw.h>
> +#include <bits/ranges_util.h> // ranges::subrange, _Repeat_iterator
> +#include <compare>
> +#include <bit>
> +#include <initializer_list>
> +#include <span>
> +
> +#include <debug/assertions.h>
> +
> +namespace std _GLIBCXX_VISIBILITY(default)
> +{
> +_GLIBCXX_BEGIN_NAMESPACE_VERSION
> +
> +struct hive_limits
> +{
> +  constexpr
> +  hive_limits(size_t __min, size_t __max) noexcept
> +  : min(__min), max(__max)
> +  { }
> +
> +  size_t min;
> +  size_t max;
> +};
> +
> +template<typename _Tp, typename _Alloc = allocator<_Tp>>
> +  class hive;
> +
> +template<typename _Tp, typename _Alloc, typename _Predicate>
> +  typename hive<_Tp, _Alloc>::size_type
> +  erase_if(hive<_Tp, _Alloc>& __cont, _Predicate __pred);
> +
> +namespace __hive
> +{
> +  struct _IgnorePtr
> +  {
> +    constexpr
> +    _IgnorePtr(nullptr_t)
> +    { }
> +
> +    template<typename _Tp>
> +    constexpr
> +    _IgnorePtr(const volatile _Tp*)
> +    { }
> +  };
> +
> +  template<size_t _Bytes>
> +    struct _Counter
> +    {
> +      static consteval auto
> +      _S_select_size()
> +      {
> +       if constexpr (_Bytes == sizeof(size_t))
> +         return static_cast<size_t>(0);
> +#ifdef __UINT64_TYPE__
> +       else if constexpr (_Bytes == 8)
> +         return static_cast<__UINT64_TYPE__>(0);
> +#endif
> +#ifdef __UINT32_TYPE__
> +       else if constexpr (_Bytes == 4)
> +         return static_cast<__UINT32_TYPE__>(0);
> +#endif
> +#ifdef __UINT16_TYPE__
> +       else if constexpr (_Bytes == 2)
> +         return static_cast<__UINT16_TYPE__>(0);
> +#endif
> +       else if constexpr (_Bytes == 1)
> +         return static_cast<unsigned char>(0);
> +       else
> +         static_assert("Unsupported bytes count");
> +      }
> +
> +      using _SizeT = decltype(_S_select_size());
> +
> +      static consteval _SizeT
> +      max_size()
> +      {
> +       if constexpr (_Bytes >= 8)
> +         return (_SizeT(1) << 48) - 1;
> +       else if constexpr (_Bytes >= 4)
> +         return (_SizeT(1) << 24) - 1;
> +       else if constexpr (_Bytes >= 2)
> +         return (_SizeT(1) << 12) - 1;
> +       else
> +         return _SizeT(255);
> +      }
> +
> +      static constexpr unsigned char _S_contb = 0x40;
> +      static constexpr unsigned char _S_vmask = _S_contb - 1;
> +
> +      static _SizeT
> +      _S_load_high(const unsigned char* __ptr) noexcept
> +      {
> +       _SizeT __res(*__ptr & _S_vmask);
> +       if constexpr (_Bytes >= 2)
> +         __res |= (_SizeT(__ptr[1] & _S_vmask) << 6);
> +       if constexpr (_Bytes >= 4)
> +         {
> +           __res |= (_SizeT(__ptr[2] & _S_vmask) << 12);
> +           __res |= (_SizeT(__ptr[3] & _S_vmask) << 18);
> +         }
> +       if constexpr (_Bytes >= 8)
> +         {
> +           __res |= (_SizeT(__ptr[4] & _S_vmask) << 24);
> +           __res |= (_SizeT(__ptr[5] & _S_vmask) << 30);
> +           __res |= (_SizeT(__ptr[6] & _S_vmask) << 36);
> +           __res |= (_SizeT(__ptr[7] & _S_vmask) << 42);
> +         }
> +        return __res;
> +      }
> +
> +      [[__gnu__::__always_inline__]]
> +      static _SizeT
> +      _S_load_fwd(const unsigned char* __ptr) noexcept
> +      {
> +       if constexpr (_Bytes == 1)
> +         return _SizeT(*__ptr);
> +       else if (!(*__ptr & _S_contb))
> +         return _SizeT(*__ptr & _S_vmask);
> +       else
> +         return _S_load_high(__ptr);
> +      }
> +
> +      [[__gnu__::__always_inline__]]
> +      static _SizeT
> +      _S_load_bwd(const unsigned char* __ptr) noexcept
> +      {
> +       if constexpr (_Bytes == 1)
> +         return _SizeT(*__ptr);
> +       else if (!(*__ptr & _S_contb))
> +         return _SizeT(*__ptr & _S_vmask);
> +       else
> +         return _S_load_high(__ptr + 1 - _Bytes);
> +      }
> +
> +      static void
> +      _S_store_high(unsigned char* __ptr, _SizeT __val) noexcept
> +      {
> +       *__ptr = (_S_contb | (__val & 0x3f));
> +       if constexpr (_Bytes >= 2)
> +         __ptr[1] = (_S_contb | ((__val >> 6) & _S_vmask));
> +       if constexpr (_Bytes >= 4)
> +         {
> +           __ptr[2] = (_S_contb | ((__val >> 12) & _S_vmask));
> +           __ptr[3] = (_S_contb | ((__val >> 18) & _S_vmask));
> +         }
> +       if constexpr (_Bytes >= 8)
> +         {
> +           __ptr[4] = (_S_contb | ((__val >> 24) & _S_vmask));
> +           __ptr[5] = (_S_contb | ((__val >> 30) & _S_vmask));
> +           __ptr[6] = (_S_contb | ((__val >> 36) & _S_vmask));
> +           __ptr[7] = (_S_contb | ((__val >> 42) & _S_vmask));
> +         }
> +      }
> +
> +      [[__gnu__::__always_inline__]]
> +      static void
> +      _S_store(unsigned char* __ptr, _SizeT __val) noexcept
> +      {
> +       if constexpr (_Bytes == 1)
> +         __ptr[0] = __ptr[__val-1] = __val;
> +       else if (__val <= _S_vmask)
> +         __ptr[0] = __ptr[__val-1] = __val;
> +       else
> +         {
> +           _S_store_high(__ptr, __val);
> +           _S_store_high(__ptr + __val - _Bytes, __val);
> +         }
> +      }
> +    };
> +
> +  // Represents an metada about the memory block. Each memory
> +  // block consits of:
> +  //  * block metadata (_Block object)
> +  //  * skipfields (_M_capacity bytes)
> +  //  * slots (_M_capacity _Slot)
> +  // Are of them are placed in single memory chunk of _M_capacity
> +  // + _S_extra_slots(_M_capacity) elements, as follows
> +  //
> +  // | <- _S_extra_slots(_M_capacity)                                 -->
> |
> +  // | <- __for_align_ --> | <-- __for_block -> | <-- _for_skipfields -->
> | <-- _M_capacity --> |
> +  // [    align   ][ _Block         ][ skipfields               ]
>  [ slots               ]
> +  //
> +  // The address of the chunk (if needed) is stored inside block can be
> +  // retrived by _M_memory(). The member is optimized out if it can be
> +  // restored from block address (there is not algigment).
> +  //
> +  // Each of the slot either contains element (_M_val) or is empty,
> +  // occupied elemnts has their corresponding skipfield by set to
> +  // 0xff.
> +  //
> +  // Continous ranges of the empty slot, form a double linked list,
> +  // that are indicated by positions of previous and next node
> +  // (npos is used to indicate first/last node). The head of the
> +  // list is _M_free_head member. The size of the range is encoded
> +  // in the edge bytes of skipfields, allow O(1) skipping.
> +  //
> +  // The _Blocks are member of intriusive list represented by
> +  // _Block_list and _M_next, _M_prev, _M_next_free, _M_prev_free
> +  // members facilitate that.
> +  template<typename _Tp, typename _Counter, typename _Ptr>
> +    struct _Block
> +    {
> +      using _CounterT = _Counter;
> +      using _SizeT = typename _CounterT::_SizeT;
> +      static constexpr _SizeT npos = ~_SizeT(0);
> +
> +      struct _Free_node
> +      {
> +       _SizeT _M_prev;
> +       _SizeT _M_next;
> +      };
> +
> +      union _Slot
> +      {
> +       _Tp _M_val;
> +       _Free_node _M_free;
> +      };
> +
> +      struct _Reservation
> +      {
> +       _SizeT _M_pos;
> +       _SizeT _M_capacity;
> +       _SizeT _M_next;
> +      };
> +
> +      using _Alloc_ptr = __ptr_rebind<_Ptr, _Slot>;
> +      using _Mem_ptr = std::conditional_t<
> +       // Block is stored at the first byte of allocated memory chunk,
> +       // so their pointer value are the same.
> +       is_pointer_v<_Ptr> && (alignof(void*) <= alignof(_Slot)),
> +       _IgnorePtr, _Alloc_ptr>;
> +
> +      static constexpr size_t
> +      _S_slot_count(size_t __bytes) noexcept
> +      { return (__bytes + sizeof(_Slot) - 1) / sizeof(_Slot); }
> +
> +      static constexpr size_t
> +      _S_extra_slots(size_t __capacity) noexcept
> +      {
> +       constexpr size_t __align_req = (alignof(_Block) > alignof(_Slot))
> +                                      ? alignof(_Block) - alignof(_Slot)
> : 0;
> +       constexpr size_t __for_align = _S_slot_count(__align_req);
> +       constexpr size_t __for_block = _S_slot_count(sizeof(_Block));
> +       constexpr size_t __block_pad = __for_align * sizeof(_Slot) -
> __align_req
> +                                    + __for_block * sizeof(_Slot) -
> sizeof(_Block);
> +
> +       size_t __for_skipfields
> +         = (__capacity > __block_pad) ? _S_slot_count(__capacity -
> __block_pad) : 0;
> +       return __for_align + __for_block + __for_skipfields;
> +      }
> +
> +      _Block() = default;
> +
> +      explicit
> +      _Block(_Alloc_ptr __mem, _SizeT __capacity) noexcept
> +      : _M_mem(__mem), _M_capacity(__capacity)
> +      { _M_clear_slots(); }
> +
> +      _Block* _M_next = nullptr;
> +      _Block* _M_prev = nullptr;
> +      _Block* _M_next_free = nullptr;
> +      _Block* _M_prev_free = nullptr;
> +
> +      [[no_unique_address]] _Mem_ptr _M_mem = nullptr;
> +      _SizeT _M_capacity = 0;
> +      _SizeT _M_free_head = npos;
> +
> +      [[__gnu__::__always_inline__]]
> +      bool
> +      _M_sentinel() const noexcept
> +      { return _M_capacity == 0; }
> +
> +      [[__gnu__::__always_inline__]]
> +      bool
> +      _M_full() const noexcept
> +      { return _M_free_head == npos; }
> +
> +      [[__gnu__::__always_inline__]]
> +      bool
> +      _M_empty() const noexcept
> +      {
> +       return (_M_free_head == 0) && (_M_free_count(0) == _M_capacity);
> +      }
> +
> +      [[__gnu__::__always_inline__]]
> +      _Alloc_ptr
> +      _M_memory() const noexcept
> +      {
> +       if constexpr (is_pointer_v<_Ptr> && (alignof(void*) <=
> alignof(_Slot)))
> +         return reinterpret_cast<_Slot*>(const_cast<_Block*>(this));
> +       else
> +         return _M_mem;
> +      }
> +
> +      [[__gnu__::__always_inline__]]
> +      unsigned char*
> +      _M_skipfield(size_t __pos) const noexcept
> +      {
> +       return reinterpret_cast<unsigned char*>(const_cast<_Block*>(this))
> +              + sizeof(_Block) + __pos;
> +      }
> +
> +      // Number of empty slot in free node starting at __pos.
> +      [[__gnu__::__always_inline__]]
> +      _SizeT
> +      _M_free_count(size_t __pos) const noexcept
> +      { return _CounterT::_S_load_fwd(_M_skipfield(__pos)); }
> +
> +      [[__gnu__::__always_inline__]]
> +      bool
> +      _M_occupied(size_t __pos) const noexcept
> +      {
> +       auto val = *_M_skipfield(__pos);
> +       return val == 0xff;
> +      }
> +
> +      [[__gnu__::__always_inline__]]
> +      _SizeT
> +      _M_first_occupied() const noexcept
> +      {
> +       if (_M_sentinel() || _M_occupied(0))
> +         return 0;
> +       return _M_free_count(0);
> +      }
> +
> +      [[__gnu__::__always_inline__]]
> +      _Slot*
> +      _M_slot(size_t __pos) const noexcept
> +      { return std::to_address(_M_memory()) + _S_extra_slots(_M_capacity)
> + __pos; }
> +
> +      [[__gnu__::__always_inline__]]
> +      _Tp*
> +      _M_elem(size_t __pos) const noexcept
> +      { return std::addressof(_M_slot(__pos)->_M_val); }
> +
> +      // If slot is contained within block, returns it position,
> +      // and npos otherwise.
> +      _SizeT
> +      _M_contains(const _Slot* __ptr)
> +      {
> +       constexpr std::less<const _Slot*> __ptrlt;
> +       if (!__ptrlt(__ptr, _M_slot(0)) && !__ptrlt(_M_slot(_M_capacity -
> 1), __ptr))
> +         return __ptr - _M_slot(0);
> +       return npos;
> +      }
> +
> +      // Returns the information about the first range of empty slots,
> +      // with sufficient information to rebuild it.
> +      [[__gnu__::__always_inline__]]
> +      _Reservation
> +      _M_reserve_slots() const noexcept
> +      {
> +       return {_M_free_head,
> +               _M_free_count(_M_free_head),
> +               _M_slot(_M_free_head)->_M_free._M_next};
> +      }
> +
> +      // Push the free node at position __pos to front on the list,
> +      // guaranteeing next insertion will happen at that point
> +      void
> +      _M_move_free_head(size_t __pos) noexcept
> +      {
> +       if (_M_free_head == __pos)
> +         return;
> +
> +       _Free_node& __node = _M_slot(__pos)->_M_free;
> +       // Unlik the node from it's current position
> +       _M_slot(__node._M_prev)->_M_free._M_next = __node._M_next;
> +       if (__node._M_next != npos)
> +         _M_slot(__node._M_next)->_M_free._M_prev = __node._M_prev;
> +
> +       // Move it to the front of the free list
> +       __node = {npos, _M_free_head};
> +       _M_free_head = __pos;
> +      }
> +
> +      // Marks slots in range [__res._M_pos, __res._M_pos + __n),
> adjusting the free list.
> +      // Returns true if the block is filled.
> +      bool
> +      _M_commit_slots(_Reservation __res, size_t __n) noexcept
> +      {
> +       std::fill_n(_M_skipfield(__res._M_pos), __n, 0xff);
> +       if (__n < __res._M_capacity)
> +         {
> +           // Node is partially used, trim it size, and adjust node.
> +           _M_free_head += __n;
> +           _M_slot(_M_free_head)->_M_free = {npos, __res._M_next};
> +           _CounterT::_S_store(_M_skipfield(_M_free_head),
> __res._M_capacity - __n);
> +           return false;
> +         }
> +       else if (__res._M_next != npos)
> +         {
> +           // Node is fully used, next free node becomes first node.
> +           _M_free_head = __res._M_next;
> +           _M_slot(_M_free_head)->_M_free._M_prev = npos;
> +           return false;
> +         }
> +       else
> +         {
> +           // Node and block is fully used.
> +           _M_free_head = npos;
> +           return true;
> +         }
> +      }
> +
> +      // Marks slot in range [__pos, __pos + __n) as empty, and record
> them
> +      // in free list. Updates __pos to next occupied slot and returns
> true
> +      // if block is empty
> +      bool
> +      _M_release_slots(size_t& __pos, size_t __n) noexcept
> +      {
> +       size_t __pfree = 0, __nfree = 0;
> +       if ((__pos > 0) && !_M_occupied(__pos - 1))
> +         __pfree = _CounterT::_S_load_bwd(_M_skipfield(__pos - 1));
> +       if ((__pos + __n < _M_capacity) && !_M_occupied(__pos + __n))
> +         __nfree = _CounterT::_S_load_fwd(_M_skipfield(__pos + __n));
> +
> +       if (__pfree + __nfree + __n == _M_capacity)
> +         {
> +           // All slots in blocks become empty, simply clear the block.
> +           _M_clear_slots();
> +           __pos = _M_capacity;
> +           return true;
> +         }
> +
> +       auto __link_next = [this](size_t __pos, size_t __next)
> +        {
> +          if (__pos != npos)
> +            _M_slot(__pos)->_M_free._M_next = __next;
> +          else
> +            _M_free_head = __next;
> +        };
> +
> +       auto __link_prev = [this](size_t __pos, size_t __prev)
> +        {
> +          if (__pos != npos)
> +            _M_slot(__pos)->_M_free._M_prev = __prev;
> +        };
> +
> +       if (__pfree && __nfree)
> +         {
> +           // Two free blocks are merged, expand the preceeding one to
> cover all slots.
> +           _CounterT::_S_store(_M_skipfield(__pos - __pfree), __pfree +
> __nfree + __n);
> +
> +           // And then remove the succseeding node from the free list.
> +           const _Free_node __next = _M_slot(__pos + __n)->_M_free;
> +           __link_next(__next._M_prev, __next._M_next);
> +           __link_prev(__next._M_next, __next._M_prev);
> +         }
> +       else if (__pfree)
> +         // Expand the preceeding slot, already on free list
> +         _CounterT::_S_store(_M_skipfield(__pos - __pfree), __pfree +
> __n);
> +       else if (__nfree)
> +         {
> +           // Expand the succseeding slot, adjusting it start position.
> +           _CounterT::_S_store(_M_skipfield(__pos), __nfree + __n);
> +           _M_slot(__pos)->_M_free = _M_slot(__pos + __n)->_M_free;
> +           const _Free_node __node = _M_slot(__pos)->_M_free;
> +
> +           // Adjust start position in previous and sucsseding node.
> +           __link_next(__node._M_prev, __pos);
> +           __link_prev(__node._M_next, __pos);
> +         }
> +       else
> +         {
> +           // New [__pos, __pos + __n) is inside occupied slots range,
> +           // created a new slot and corresponding free list node.
> +           _CounterT::_S_store(_M_skipfield(__pos), __n);
> +           _M_slot(__pos)->_M_free = {npos, _M_free_head};
> +
> +           // Add new node at begining of free list.
> +           __link_prev(_M_free_head, __pos);
> +           _M_free_head = __pos;
> +         }
> +
> +       __pos += __n + __nfree;
> +       return false;
> +      }
> +
> +      // Marks are slots as empty, creating single free node
> +      // for range [0, _M_capacity)
> +      void
> +      _M_clear_slots() noexcept
> +      {
> +       std::fill_n(_M_skipfield(0), _M_capacity, 0);
> +       _CounterT::_S_store(_M_skipfield(0), _M_capacity);
> +       _M_slot(0)->_M_free = { npos, npos };
> +       _M_free_head = 0;
> +      }
> +
> +      // Destroys all elements in occupied slot in the node, using
> provided
> +      // allocator. Returns the number of destroyed elements.
> +      template<typename _TpAlloc>
> +       size_t
> +       _M_clear_elems(_TpAlloc& __alloc)
> +       {
> +         size_t __removed = 0;
> +         size_t __pos = 0, __first = 0;
> +         while (__pos != _M_capacity)
> +           if (_M_occupied(__pos))
> +             std::allocator_traits<_TpAlloc>::destroy(__alloc,
> _M_elem(__pos++));
> +           else
> +             {
> +               __removed += __pos - __first;
> +               __pos += _M_free_count(__pos);
> +               __first = __pos;
> +             }
> +         __removed += __pos - __first;
> +         return __removed;
> +       }
> +
> +      [[__gnu__::__always_inline__]]
> +      void
> +      _M_set_next(_Block* __node) noexcept
> +      {
> +       _M_next = __node;
> +       if (__node)
> +         __node->_M_prev = this;
> +      }
> +    };
> +
> +
> +  // Class representing an double linked list of blocks. Manages the block
> +  // itself, but not contained elements.
> +  //
> +  // The blocks are split into two kinds:
> +  // * active [_M_first, _M_sent): contains at least one element, visited
> +  //   by iteration
> +  // * reserved (_M_sent, null): no element contained, provded extra
> capacity.
> +  // The blocks are moved between list by hiding (active -> reserved) or
> +  // exposing (reserved->active).
> +  //
> +  // Futhermore, the reserved blocks and the subset of active list, that
> contains
> +  // at least one free slot, are forming double linked list
> (_M_prev_free, _M_next_free),
> +  // pointed out is _M_sent._M_next_free (head), and _M_prev_free (tail),
> but _M_sent
> +  // is not part of the list.
> +  template<typename _Tp, typename _Alloc>
> +    struct _Block_list
> +    {
> +      static consteval size_t
> +      _S_counter_bytes()
> +      {
> +       constexpr size_t __max = sizeof(_Tp) / 2;
> +       if constexpr (__max >= sizeof(size_t))
> +         return sizeof(size_t);
> +#ifdef __UINT64_TYPE__
> +       else if (__max >= 8)
> +         return 8;
> +#endif
> +#ifdef __UINT32_TYPE__
> +       else if (__max >= 4)
> +         return 4;
> +#endif
> +#ifdef __UINT16_TYPE__
> +       else if (__max >= 2)
> +         return 2;
> +#endif
> +       else
> +         return 1;
> +      }
> +
> +      using _CounterT = _Counter<_S_counter_bytes()>;
> +      using _SizeT = typename _CounterT::_SizeT;
> +      using _BlockT = _Block<_Tp, _CounterT, typename
> allocator_traits<_Alloc>::pointer>;
> +      using _SlotT = typename _BlockT::_Slot;
> +
> +      using _SAlloc = typename allocator_traits<_Alloc>::template
> rebind_alloc<_SlotT>;
> +      using _SAllocTraits = typename allocator_traits<_Alloc>::template
> rebind_traits<_SlotT>;
> +
> +      static consteval hive_limits
> +      _S_hard_limits()
> +      {
> +       size_t __alloc_max;
> +       if constexpr (requires { _SAlloc::max_size(); })
> +         __alloc_max = _SAlloc::max_size();
> +       else
> +         __alloc_max = numeric_limits<typename
> _SAllocTraits::size_type>::max()
> +                         / sizeof(_SlotT);
> +
> +       constexpr size_t __counter_max = _CounterT::max_size();
> +       if  (__alloc_max >= __counter_max +
> _BlockT::_S_extra_slots(__counter_max))
> +         return hive_limits(2, __counter_max);
> +       else
> +         {
> +           size_t __max = __alloc_max;
> +           if constexpr (alignof(_BlockT) > alignof(_SlotT))
> +             __max -= _BlockT::_S_slot_count(alignof(_BlockT) -
> alignof(_SlotT));
> +           __max -= _BlockT::_S_slot_count(sizeof(_BlockT));
> +
> +           __max = (__max * sizeof(_SlotT)) / (sizeof(_SlotT) + 1);
> +           return hive_limits(2, __max);
> +         }
> +      }
> +
> +      static consteval hive_limits
> +      _S_default_limits()
> +      {
> +       // TODO consider if we should do something better
> +       auto __hard = _S_hard_limits();
> +       if (__hard.max < 16)
> +         return __hard;
> +       else if (__hard.max < 255)
> +         return hive_limits(16, __hard.max);
> +       else if (__hard.max < 512)
> +         return hive_limits(16, 255);
> +       else
> +         return hive_limits(16, 512);
> +      }
> +
> +      _BlockT _M_sent = _BlockT();
> +      _BlockT* _M_first = &_M_sent;
> +      size_t _M_capacity = 0;
> +      [[no_unique_address]] _Alloc _M_alloc;
> +      _SizeT _M_min_cap;
> +      _SizeT _M_max_cap;
> +      _SizeT _M_last_cap;
> +
> +      constexpr explicit
> +      _Block_list(hive_limits __limits, const _Alloc& __alloc)
> +      : _M_alloc(__alloc), _M_min_cap(__limits.min),
> _M_max_cap(__limits.max),
> +       _M_last_cap(_M_min_cap)
> +      { }
> +
> +      ~_Block_list()
> +      { _M_drop_blocks(); }
> +
> +      void
> +      _M_swap_blocks(_Block_list& __other) noexcept
> +      {
> +       auto __fixup = [](_Block_list& __list)
> +       {
> +         if (_BlockT* __next = __list._M_sent._M_next)
> +           __next->_M_prev = &__list._M_sent;
> +         __list._M_link_prev(__list._M_sent, &__list._M_sent);
> +       };
> +
> +       std::swap(_M_first, __other._M_first);
> +       std::swap(_M_sent._M_prev, __other._M_sent._M_prev);
> +       std::swap(_M_sent._M_next, __other._M_sent._M_next);
> +       std::swap(_M_sent._M_next_free, __other._M_sent._M_next_free);
> +       std::swap(_M_sent._M_prev_free, __other._M_sent._M_prev_free);
> +       std::swap(_M_capacity, __other._M_capacity);
> +       __fixup(__other);
> +       __fixup(*this);
> +      }
> +
> +      [[__gnu__::__always_inline__]]
> +      _BlockT*
> +      _M_next_free() const noexcept
> +      {
> +       if (_M_sent._M_next_free)
> +         return _M_sent._M_next_free;
> +       else
> +         return _M_sent._M_next;
> +      }
> +
> +      [[__gnu__::__always_inline__]]
> +      void
> +      _M_unlink_free(_BlockT* __block) noexcept
> +      {
> +       _BlockT* __prev = __block->_M_prev_free ? __block->_M_prev_free :
> &_M_sent;
> +       _BlockT* __next = __block->_M_next_free ? __block->_M_next_free :
> &_M_sent;
> +       __prev->_M_next_free = __block->_M_next_free;
> +       __next->_M_prev_free = __block->_M_prev_free;
> +      }
> +
> +      [[__gnu__::__always_inline__]]
> +      void
> +      _M_append_free(_BlockT* __block) noexcept
> +      {
> +       __block->_M_next_free = _M_sent._M_next_free;
> +       __block->_M_prev_free = nullptr;
> +       if (!_M_sent._M_next_free)
> +         _M_sent._M_next_free = _M_sent._M_prev_free = __block;
> +       else
> +         {
> +           _M_sent._M_next_free->_M_prev_free = __block;
> +           _M_sent._M_next_free = __block;
> +         }
> +      }
> +
> +      // Unlinks to block from the active block list, does update free
> list.
> +      [[__gnu__::__always_inline__]]
> +      void
> +      _M_detach_active(_BlockT* __first, _BlockT* __last)
> +      { _M_link_prev(*__first, __last->_M_next); }
> +
> +      // Appends blocks to the active blocks list, does not update free
> list.
> +      [[__gnu__::__always_inline__]]
> +      void
> +      _M_append_active(_BlockT* __first, _BlockT* __last)
> +      {
> +       _M_link_prev(_M_sent, __first);
> +       __last->_M_set_next(&_M_sent);
> +      }
> +
> +      // Move blocks from reserved to active.
> +      void
> +      _M_expose(_BlockT* __first, _BlockT* __last) noexcept
> +      {
> +       __first->_M_prev->_M_set_next(__last->_M_next);
> +       _M_append_active(__first, __last);
> +      }
> +
> +      [[__gnu__::__always_inline__]]
> +      void
> +      _M_expose(_BlockT* __block) noexcept
> +      { _M_expose(__block, __block); }
> +
> +      // Move blocks from active to reserved
> +      // pre: [__first, __last) are not on the free list
> +      void
> +      _M_hide(_BlockT* __first, _BlockT* __last) noexcept
> +      {
> +       _M_detach_active(__first, __last);
> +       _M_append_reserved(__first, __last);
> +      }
> +
> +      [[__gnu__::__always_inline__]]
> +      void
> +      _M_hide(_BlockT* __block) noexcept
> +      { _M_hide(__block, __block); }
> +
> +      _BlockT*
> +      _M_reserve_block(size_t __capacity)
> +      {
> +       _SAlloc __salloc(_M_alloc);
> +
> +       _BlockT* __block = _S_allocate_block(__salloc, __capacity);
> +       _M_append_reserved(__block, __block);
> +       _M_capacity += __capacity;
> +       return __block;
> +      }
> +
> +      _BlockT*
> +      _M_reserve_block()
> +      {
> +       _BlockT* __block = _M_reserve_block(_M_last_cap);
> +       if (_M_last_cap < _M_max_cap / 2)
> +         _M_last_cap *= 2;
> +       else
> +         _M_last_cap = _M_max_cap;
> +       return __block;
> +      }
> +
> +      // Dallocate all reserved blocks.
> +      void
> +      _M_trim_capacity()
> +      {
> +       _SAlloc __salloc(_M_alloc);
> +       _M_capacity -= _S_deallocate_blocks(__salloc, _M_sent._M_next,
> nullptr);
> +       _M_sent._M_next = nullptr;
> +      }
> +
> +      // Deallocate reserved blocks with total capacity no greater
> +      // than __remove.
> +      void
> +      _M_reduce_capacity(size_t __remove)
> +      {
> +       _SAlloc __salloc(_M_alloc);
> +       _BlockT* __prev = &_M_sent;
> +       while (__remove >= _M_min_cap)
> +       {
> +         _BlockT* __last = __prev->_M_next;
> +         while(__last && __last->_M_capacity > __remove)
> +           __last = __last->_M_next;
> +
> +         if (!__last)
> +           break;
> +
> +         __prev = __last->_M_prev;
> +         while (__last && __last->_M_capacity <= __remove)
> +           {
> +             __remove -= __last->_M_capacity;
> +             __last = __last->_M_next;
> +           }
> +
> +         _M_capacity -= _S_deallocate_blocks(__salloc, __prev->_M_next,
> __last);
> +         __prev->_M_set_next(__last);
> +       }
> +      }
> +
> +      // Deallocate reserved blocks for which predicate is true
> +      template<typename _Pred>
> +       void
> +       _M_trim_reserved_if(_Pred __pred)
> +       {
> +         _SAlloc __salloc(_M_alloc);
> +         _BlockT* __prev = &_M_sent;
> +         while (true)
> +         {
> +           _BlockT* __last = __prev->_M_next;
> +           while(__last && !__pred(__last))
> +             __last = __last->_M_next;
> +
> +           if (!__last)
> +             break;
> +
> +           __prev = __last->_M_prev;
> +           while (__last && __pred(__last))
> +             __last = __last->_M_next;
> +
> +           _M_capacity -= _S_deallocate_blocks(__salloc, __prev->_M_next,
> __last);
> +           __prev->_M_set_next(__last);
> +         }
> +       }
> +
> +      // Move active blocks from the __src to the current block list,
> they total
> +      // capacity is assumed to be cap.
> +      void
> +      _M_splice_active(_Block_list& __src, size_t __cap)
> +      {
> +       _BlockT* __first = __src._M_first;
> +       _BlockT* __last = __src._M_sent._M_prev;
> +
> +       __src._M_detach_active(__first, __last);
> +       __src._M_capacity -= __cap;
> +       _M_append_active(__first, __last);
> +       _M_capacity += __cap;
> +
> +       if (!__src._M_sent._M_next_free)
> +         return;
> +
> +       // Concate free lists
> +       _BlockT* __last_free = _M_sent._M_next_free
> +                            ? _M_sent._M_prev_free
> +                            : &_M_sent;
> +       __last_free->_M_next_free = __src._M_sent._M_next_free;
> +       __src._M_sent._M_next_free->_M_prev_free = _M_sent._M_prev_free;
> +       _M_sent._M_prev_free = __src._M_sent._M_prev_free;
> +       __src._M_sent._M_next_free = nullptr;
> +       __src._M_sent._M_prev_free = nullptr;
> +      }
> +
> +      // Deallocates all blocks (reserved and used), asumes elements are
> cleared
> +      void
> +      _M_drop_blocks()
> +      {
> +       _SAlloc __salloc(_M_alloc);
> +       _S_deallocate_blocks(__salloc, _M_first, &_M_sent);
> +       _S_deallocate_blocks(__salloc, _M_sent._M_next, nullptr);
> +
> +       _M_sent._M_prev_free = _M_sent._M_next_free = nullptr;
> +       _M_sent._M_prev = _M_sent._M_next = nullptr;
> +       _M_first = &_M_sent;
> +
> +       _M_capacity = 0;
> +       _M_last_cap = _M_min_cap;
> +      }
> +
> +    private:
> +      static _BlockT*
> +      _S_allocate_block(_SAlloc& __alloc, size_t __capacity)
> +      {
> +       const size_t __count = __capacity +
> _BlockT::_S_extra_slots(__capacity);
> +       auto __mem = _SAllocTraits::allocate(__alloc, __count);
> +
> +       void* __ptr = std::to_address(__mem);
> +       size_t __space = __count * sizeof(_SlotT);
> +       if constexpr (alignof(_BlockT) > sizeof(_SlotT))
> +         __ptr = std::align(alignof(_BlockT), sizeof(_BlockT), __ptr,
> __space);
> +
> +       return ::new(__ptr) _BlockT(__mem, __capacity);
> +      }
> +
> +      static size_t
> +      _S_deallocate_blocks(_SAlloc& __alloc, _BlockT* __from, _BlockT*
> __to)
> +      {
> +       size_t __capacity = 0;
> +       while (__from != __to)
> +         {
> +           _BlockT* __cur = __from;
> +           auto __ptr = __cur->_M_memory();
> +           auto __count = __cur->_M_capacity +
> _BlockT::_S_extra_slots(__cur->_M_capacity);
> +           __capacity += __cur->_M_capacity;
> +           __from = __from->_M_next;
> +
> +           // Custom pointer may have non-trivial destructor,
> +           // call it before releasing memory.
> +           __cur->~_BlockT();
> +           _SAllocTraits::deallocate(__alloc, __ptr, __count);
> +         }
> +       return __capacity;
> +      }
> +
> +      [[__gnu__::__always_inline__]]
> +      void
> +      _M_link_prev(_BlockT& __of, _BlockT* __to) noexcept
> +      {
> +       if (_BlockT* __prev = __of._M_prev)
> +         __prev->_M_set_next(__to);
> +       else
> +         {
> +           // __of is first block, set __to as first
> +           _M_first = __to;
> +           __to->_M_prev = nullptr;
> +         }
> +      }
> +
> +      void
> +      _M_append_reserved(_BlockT* __first, _BlockT* __last)
> +      {
> +       __last->_M_set_next(_M_sent._M_next);
> +       _M_sent._M_set_next(__first);
> +      }
> +    };
> +
> +  template<typename _Tp, typename _BlockT>
> +    struct _Iterator
> +    {
> +      using _CounterT = typename _BlockT::_CounterT;
> +
> +    public:
> +      using iterator_category = bidirectional_iterator_tag;
> +      using value_type = _Tp;
> +      using pointer = _Tp*;
> +      using reference = _Tp&;
> +      using size_type = size_t;
> +      using difference_type = ptrdiff_t;
> +
> +      _Iterator() = default;
> +
> +      template<typename _Up>
> +       requires is_const_v<_Tp> && is_same_v<_Tp, const _Up>
> +       _Iterator(_Iterator<_Up, _BlockT> __other)
> +       : _M_block(__other._M_block), _M_pos(__other._M_pos)
> +       { }
> +
> +      reference
> +      operator*() const noexcept
> +      { return _M_block->_M_slot(_M_pos)->_M_val; }
> +
> +      pointer
> +      operator->() const noexcept
> +      { return _M_block->_M_elem(_M_pos); }
> +
> +      _Iterator&
> +      operator++()
> +      {
> +       ++_M_pos;
> +       if (_M_pos != _M_block->_M_capacity)
> +         {
> +           if (_M_block->_M_occupied(_M_pos))
> +             return *this;
> +
> +           _M_pos +=
> _CounterT::_S_load_fwd(_M_block->_M_skipfield(_M_pos));
> +           if (_M_pos != _M_block->_M_capacity)
> +             return *this;
> +         }
> +
> +       _M_block = _M_block->_M_next;
> +       _M_pos = _M_block->_M_first_occupied();
> +       return *this;
> +      }
> +
> +      _Iterator
> +      operator++(int)
> +      {
> +       _Iterator __res = *this;
> +       ++*this;
> +       return __res;
> +      }
> +
> +      _Iterator&
> +      operator--()
> +      {
> +       if (_M_pos)
> +         {
> +           --_M_pos;
> +           if (_M_block->_M_occupied(_M_pos))
> +             return *this;
> +
> +           if (_M_pos)
> +             {
> +               size_t __gap =
> _CounterT::_S_load_bwd(_M_block->_M_skipfield(_M_pos));
> +               if (_M_pos >= __gap)
> +                 {
> +                   _M_pos -= __gap;
> +                   return *this;
> +                 }
> +             }
> +         }
> +
> +       _M_block = _M_block->_M_prev;
> +       __glibcxx_assert(_M_block);
> +       _M_pos = _M_block->_M_capacity - 1;
> +       if (_M_block->_M_occupied(_M_pos))
> +         return *this;
> +
> +       _M_pos -= _CounterT::_S_load_bwd(_M_block->_M_skipfield(_M_pos));
> +       return *this;
> +      }
> +
> +      _Iterator
> +      operator--(int)
> +      {
> +       _Iterator __res = *this;
> +       --*this;
> +       return __res;
> +      }
> +
> +      friend bool operator==(_Iterator, _Iterator) = default;
> +
> +    private:
> +      explicit
> +      _Iterator(const _BlockT* __block)
> +      : _M_block(__block), _M_pos(__block->_M_first_occupied())
> +      { }
> +
> +      explicit
> +      _Iterator(const _BlockT* __block, size_t __pos)
> +      : _M_block(__block), _M_pos(__pos)
> +      { }
> +
> +      const _BlockT* _M_block = nullptr;
> +      size_t _M_pos = 0;
> +
> +      friend struct _Iterator<const _Tp, _BlockT>;
> +      template<typename, typename>
> +       friend class std::hive;
> +    };
> +} // namespace __hive
> +
> +template<typename _Tp, typename _Alloc>
> +  class hive
> +  {
> +    using _BlockListT = __hive::_Block_list<_Tp, _Alloc>;
> +    using _BlockT = typename _BlockListT::_BlockT;
> +    using _SlotT = typename _BlockListT::_SlotT;
> +    using _CounterT = typename _BlockListT::_CounterT;
> +    using _AllocT = allocator_traits<_Alloc>;
> +
> +  public:
> +    using value_type = _Tp;
> +    using allocator_type = _Alloc;
> +    using pointer = typename _AllocT::pointer;
> +    using const_pointer = typename _AllocT::const_pointer;
> +    using reference = value_type&;
> +    using const_reference = const value_type&;
> +    using size_type = size_t;
> +    using difference_type = ptrdiff_t;
> +    using iterator = __hive::_Iterator<_Tp, _BlockT>;
> +    using const_iterator = __hive::_Iterator<const _Tp, _BlockT>;
> +    using reverse_iterator = std::reverse_iterator<iterator>;
> +    using const_reverse_iterator = std::reverse_iterator<const_iterator>;
> +
> +    constexpr
> +    hive() noexcept(noexcept(_Alloc()))
> +    : _M_blocks(block_capacity_default_limits(), _Alloc())
> +    { }
> +
> +    constexpr explicit
> +    hive(const _Alloc& __alloc) noexcept
> +    : _M_blocks(block_capacity_default_limits(), __alloc)
> +    { }
> +
> +    constexpr explicit
> +    hive(hive_limits __limits)
> +    : _M_blocks(__limits, _Alloc())
> +    { }
> +
> +    constexpr
> +    hive(hive_limits __limits, const _Alloc& __alloc)
> +    : _M_blocks(__limits, __alloc)
> +    { }
> +
> +    explicit
> +    hive(size_type __count, const _Alloc& __alloc = _Alloc())
> +    : hive(__alloc)
> +    { _M_insert_n(__count, _ValueInitTag()); }
> +
> +    hive(size_type __count, hive_limits __limits,
> +        const _Alloc& __alloc = _Alloc())
> +    : hive(_S_clamp_limits(__limits), __alloc)
> +    { _M_insert_n(__count, _ValueInitTag()); }
> +
> +    hive(size_type __count, const _Tp& __value,
> +        const _Alloc& __alloc = _Alloc())
> +    : hive(__alloc)
> +    { _M_insert_n(__count, __value); }
> +
> +    hive(size_type __count, const _Tp& __value,
> +        hive_limits __limits, const _Alloc& __alloc = _Alloc())
> +    : hive(_S_clamp_limits(__limits), __alloc)
> +    { _M_insert_n(__count, __value); }
> +
> +    hive(initializer_list<_Tp> __il, const _Alloc& __alloc = _Alloc())
> +    : hive(__alloc)
> +    { insert(__il); }
> +
> +    hive(initializer_list<_Tp> __il, hive_limits __limits,
> +        const _Alloc& __alloc = _Alloc())
> +    : hive(_S_clamp_limits(__limits), __alloc)
> +    { insert(__il); }
> +
> +    template<__has_input_iter_cat _InputIterator>
> +      hive(_InputIterator __first, _InputIterator __last,
> +          const _Alloc& __alloc = _Alloc())
> +    : hive(__alloc)
> +    { insert(__first, __last); }
> +
> +    template<__has_input_iter_cat _InputIterator>
> +      hive(_InputIterator __first, _InputIterator __last,
> +          hive_limits __limits, const _Alloc& __alloc = _Alloc())
> +    : hive(_S_clamp_limits(__limits), __alloc)
> +    { insert(__first, __last); }
> +
> +    template<__detail::__container_compatible_range<_Tp> _Rg>
> +      hive(from_range_t, _Rg&& __rg, const _Alloc& __alloc = _Alloc())
> +      : hive(__alloc)
> +      { insert_range(__rg); }
> +
> +    template<__detail::__container_compatible_range<_Tp> _Rg>
> +      hive(from_range_t, _Rg&& __rg, hive_limits __limits,
> +          const _Alloc& __alloc = _Alloc())
> +      : hive(_S_clamp_limits(__limits), __alloc)
> +      { insert_range(__rg); }
> +
> +    hive(const hive& __other)
> +    : hive(
> +       __other.block_capacity_limits(),
> +
>  _AllocT::select_on_container_copy_construction(__other.get_allocator()))
> +    { _M_insert_range(__other); }
> +
> +    hive(const hive& __other, const type_identity_t<_Alloc>& __alloc)
> +    : hive(__other.block_capacity_limits(), __alloc)
> +    { _M_insert_range(__other); }
> +
> +    hive(hive&& __other) noexcept
> +    : hive(__other.block_capacity_limits(), __other.get_allocator())
> +    {
> +      _M_blocks._M_swap_blocks(__other._M_blocks);
> +      _M_size = __other._M_size;
> +      __other._M_size = 0;
> +    }
> +
> +    hive(hive&& __other, const type_identity_t<_Alloc>& __alloc)
> +    noexcept(_AllocT::is_always_equal::value)
> +    : hive(__other.block_capacity_limits(), __alloc)
> +    {
> +      if constexpr (!_AllocT::is_always_equal::value)
> +       if (_M_blocks._M_alloc != __other._M_blocks._M_alloc)
> +         {
> +           insert(std::make_move_iterator(__other.begin()),
> +                  std::make_move_iterator(__other.end()));
> +           __other.clear();
> +           return;
> +         }
> +
> +      _M_blocks._M_swap_blocks(__other._M_blocks);
> +      _M_size = __other._M_size;
> +      __other._M_size = 0;
> +    }
> +
> +    hive& operator=(const hive& __other)
> +    {
> +      if (this == std::addressof(__other))
> +       return *this;
> +
> +      if constexpr
> (_AllocT::propagate_on_container_copy_assignment::value)
> +       {
> +         if constexpr (!_AllocT::is_always_equal::value)
> +           if (_M_blocks._M_alloc != __other._M_blocks._M_alloc)
> +             _M_clear_and_trim();
> +         _M_blocks._M_alloc = __other._M_blocks._M_alloc;
> +       }
> +
> +      _M_assign_range(__other);
> +      return *this;
> +    }
> +
> +    hive& operator=(hive&& __other)
> +
> noexcept(allocator_traits<_Alloc>::propagate_on_container_move_assignment::value
> +            || allocator_traits<_Alloc>::is_always_equal::value)
> +    {
> +      if constexpr
> (!_AllocT::propagate_on_container_move_assignment::value
> +                   && !_AllocT::is_always_equal::value)
> +       if (_M_blocks._M_alloc != __other._M_blocks._M_alloc)
> +         {
> +           assign(std::make_move_iterator(__other.begin()),
> +                  std::make_move_iterator(__other.end()));
> +           __other.clear();
> +           return *this;
> +         }
> +
> +      if constexpr
> (_AllocT::propagate_on_container_move_assignment::value)
> +       {
> +         if constexpr (!_AllocT::is_always_equal::value)
> +           if (_M_blocks._M_alloc != __other._M_blocks._M_alloc)
> +             _M_clear_and_trim();
> +         _M_blocks._M_alloc = __other._M_blocks._M_alloc;
> +       }
> +
> +      // Capacity limits are swapped, so the blocks we transfered are
> within them.
> +      _M_swap(__other);
> +      __other.clear();
> +      return *this;
> +    }
> +
> +    hive& operator=(initializer_list<_Tp> __il)
> +    {
> +      assign_range(__il);
> +      return *this;
> +    }
> +
> +    void
> +    swap(hive& __other)
> +    noexcept(allocator_traits<_Alloc>::propagate_on_container_swap::value
> +            || allocator_traits<_Alloc>::is_always_equal::value)
> +    {
> +      if constexpr (_AllocT::propagate_on_container_swap::value)
> +       std::swap(_M_blocks._M_alloc, __other._M_blocks._M_alloc);
> +      else if constexpr (!_AllocT::is_always_equal::value)
> +       __glibcxx_assert(_M_blocks._M_alloc == __other._M_blocks._M_alloc);
> +      _M_swap(__other);
> +    }
> +
> +    ~hive()
> +    { _M_clear_and_trim(); }
> +
> +    template<__detail::__container_compatible_range<_Tp> _Rg>
> +      void
> +      assign_range(_Rg&& __rg)
> +      {
> +       if constexpr (ranges::contiguous_range<_Rg> &&
> ranges::sized_range<_Rg>)
> +         {
> +           span<remove_reference_t<ranges::range_reference_t<_Rg>>>
> +             __span(__rg);
> +           _M_assign_range(__span);
> +         }
> +       else
> +         _M_assign_range(__rg);
> +      }
> +
> +    template<__has_input_iter_cat _InputIterator>
> +      void assign(_InputIterator __first, _InputIterator __last)
> +      {
> +       if constexpr (contiguous_iterator<_InputIterator>)
> +         {
> +           span<remove_reference_t<iter_reference_t<_InputIterator>>>
> +             __span(__first, __last);
> +           _M_assign_range(__span);
> +         }
> +       else
> +         {
> +           ranges::subrange<_InputIterator> __range(__first, __last);
> +           _M_assign_range(__range);
> +         }
> +      }
> +
> +    void
> +    assign(initializer_list<_Tp> __il)
> +    {
> +      span<const _Tp> __span(__il);
> +      _M_assign_range(__span);
> +    }
> +
> +    void
> +    assign(size_type __count, const _Tp& __val)
> +    {
> +      assign(std::__make_repeat_iterator(__val, size_type(0)),
> +            std::__make_repeat_iterator(__val, __count));
> +    }
> +
> +    allocator_type
> +    get_allocator() const noexcept
> +    { return _M_blocks._M_alloc; }
> +
> +    iterator
> +    begin() noexcept
> +    { return iterator(_M_blocks._M_first); }
> +
> +    iterator
> +    end() noexcept
> +    { return iterator(&_M_blocks._M_sent, 0); }
> +
> +    const_iterator
> +    begin() const noexcept
> +    { return const_iterator(_M_blocks._M_first); }
> +
> +    const_iterator
> +    end() const noexcept
> +    { return const_iterator(&_M_blocks._M_sent, 0); }
> +
> +    reverse_iterator
> +    rbegin() noexcept
> +    { return reverse_iterator(end()); }
> +
> +    reverse_iterator
> +    rend() noexcept
> +    { return reverse_iterator(begin()); }
> +
> +    const_reverse_iterator
> +    rbegin() const noexcept
> +    { return const_reverse_iterator(end()); }
> +
> +    const_reverse_iterator
> +    rend() const noexcept
> +    { return const_reverse_iterator(begin()); }
> +
> +    const_iterator
> +    cbegin() const noexcept
> +    { return begin(); }
> +
> +    const_iterator
> +    cend() const noexcept
> +    { return end(); }
> +
> +    const_reverse_iterator
> +    crbegin() const noexcept
> +    { return rbegin(); }
> +
> +    const_reverse_iterator
> +    crend() const noexcept
> +    { return rend(); }
> +
> +    bool
> +    empty() const noexcept
> +    { return _M_size == 0; }
> +
> +    size_type
> +    size() const noexcept
> +    { return _M_size; }
> +
> +    size_type
> +    capacity() const noexcept
> +    { return _M_blocks._M_capacity; }
> +
> +    void
> +    reserve(size_type __n)
> +    { _M_reserve(__n, block_capacity_limits()); }
> +
> +    void
> +    trim_capacity()
> +    { _M_blocks._M_trim_capacity(); }
> +
> +    void
> +    trim_capacity(size_type __keep)
> +    {
> +      if (__keep >= capacity())
> +       return;
> +      else if (__keep <= size())
> +       _M_blocks._M_trim_capacity();
> +      else
> +       _M_blocks._M_reduce_capacity(capacity() - __keep);
> +    }
> +
> +    // shrink to fit
> +    void
> +    shrink_to_fit()
> +    {
> +      trim_capacity();
> +      // No or single partially free block, we size matches capacity
> +      if (size() == capacity())
> +       return;
> +
> +      _RelocateGuard __guard(*this);
> +      // Visit blocks in reserve as they normally go from largest to
> smallest.
> +      _BlockT* __block = _M_blocks._M_sent._M_prev;
> +      _BlockT* __lowest_kept = nullptr;
> +      while (__block)
> +       {
> +         _BlockT* __prev = __block->_M_prev;
> +         if (_M_blocks._M_capacity - __block->_M_capacity >= _M_size)
> +           __guard._M_move_active(__block);
> +         else if (!__lowest_kept || __lowest_kept->_M_capacity >
> __block->_M_capacity)
> +           __lowest_kept = __block;
> +         __block = __prev;
> +       }
> +
> +      // Extra capacity is over minium block size, replace minimum block.
> +      if (_M_blocks._M_capacity - _M_size >= _M_blocks._M_min_cap)
> +       {
> +         __guard._M_move_active(__lowest_kept);
> +         reserve(_M_size);
> +       }
> +
> +      __guard._M_transfer();
> +    }
> +
> +    void
> +    reshape(hive_limits __limits)
> +    {
> +      __limits = _S_clamp_limits(__limits);
> +      auto __outside_limits = [&__limits](const _BlockT* __block)
> +       {
> +         size_t __cap = __block->_M_capacity;
> +         return __cap < __limits.min || __cap > __limits.max;
> +       };
> +
> +      _M_blocks._M_trim_reserved_if(__outside_limits);
> +
> +      _RelocateGuard __guard(*this);
> +      _BlockT* __block = _M_blocks._M_first;
> +      while (!__block->_M_sentinel())
> +       {
> +         _BlockT* __next = __block->_M_next;
> +         if (__outside_limits(__block))
> +           __guard._M_move_active(__block);
> +         __block = __next;
> +       }
> +
> +      // Expand limits, so both new and old blocks are within
> +      // them, as in case of exception both of them may remain.
> +      if (__limits.min < _M_blocks._M_min_cap)
> +       _M_blocks._M_min_cap = __limits.min;
> +      if (__limits.max > _M_blocks._M_max_cap)
> +       _M_blocks._M_max_cap = __limits.max;
> +
> +      _M_reserve(_M_size, __limits);
> +      __guard._M_transfer();
> +      _M_blocks._M_min_cap = __limits.min;
> +      _M_blocks._M_max_cap = __limits.max;
> +    }
> +
> +
> +    constexpr hive_limits
> +    block_capacity_limits() const noexcept
> +    { return hive_limits(_M_blocks._M_min_cap, _M_blocks._M_max_cap); }
> +
> +    static constexpr hive_limits
> +    block_capacity_default_limits() noexcept
> +    { return _BlockListT::_S_default_limits(); }
> +
> +    static constexpr hive_limits
> +    block_capacity_hard_limits() noexcept
> +    { return _BlockListT::_S_hard_limits(); }
> +
> +    static constexpr
> +    bool is_within_hard_limits(hive_limits __limits) noexcept
> +    {
> +      hive_limits __hard = block_capacity_hard_limits();
> +      return __hard.min <= __limits.min
> +            && __limits.min <= __limits.max
> +            && __limits.max <= __hard.max;
> +    }
> +
> +    template<typename... _Args>
> +      iterator
> +      emplace(_Args&&... __args)
> +      {
> +       _BlockT* __block;
> +       if (_M_size == capacity())
> +         __block = _M_blocks._M_reserve_block();
> +       else
> +         __block = _M_blocks._M_next_free();
> +
> +       _InsertGuard __guard(*this, __block);
> +       __guard.construct(_M_blocks._M_alloc,
> std::forward<_Args>(__args)...);
> +       __guard._M_commit();
> +       return iterator(__block, __guard._M_res._M_pos);
> +      }
> +
> +    iterator
> +    insert(const _Tp& __val)
> +    { return emplace(__val); }
> +
> +    iterator
> +    insert(_Tp&& __val)
> +    { return emplace(std::move(__val)); }
> +
> +    template<typename... _Args>
> +      iterator
> +      emplace_hint(const_iterator, _Args&&... __args)
> +      { return emplace(std::forward<_Args>(__args)...); }
> +
> +    iterator
> +    insert(const_iterator, const _Tp& __val)
> +    { return emplace(__val); }
> +
> +    iterator
> +    insert(const_iterator, _Tp&& __val)
> +    { return emplace(std::move(__val)); }
> +
> +    template<__detail::__container_compatible_range<_Tp> _Rg>
> +      void
> +      insert_range(_Rg&& __rg)
> +      {
> +       if constexpr (ranges::contiguous_range<_Rg> &&
> ranges::sized_range<_Rg>)
> +         {
> +           span<remove_reference_t<ranges::range_reference_t<_Rg>>>
> +             __span(__rg);
> +           _M_insert_range(__span);
> +         }
> +       else
> +         _M_insert_range(__rg);
> +      }
> +
> +    template<__has_input_iter_cat _InputIterator>
> +      void insert(_InputIterator __first, _InputIterator __last)
> +      {
> +       if constexpr (contiguous_iterator<_InputIterator>)
> +         {
> +           span<remove_reference_t<iter_reference_t<_InputIterator>>>
> +             __span(__first, __last);
> +           _M_insert_range(__span);
> +         }
> +       else
> +         {
> +           ranges::subrange<_InputIterator> __range(__first, __last);
> +           _M_insert_range(__range);
> +         }
> +      }
> +
> +    void
> +    insert(initializer_list<_Tp> __il)
> +    {
> +      span<const _Tp> __span(__il);
> +      _M_insert_range(__span);
> +    }
> +
> +    void
> +    insert(size_type __count, const _Tp& __val)
> +    { _M_insert_n(__count, __val); }
> +
> +    iterator
> +    erase(const_iterator __it)
> +    {
> +      _BlockT* __block = const_cast<_BlockT*>(__it._M_block);
> +      _BlockT* __next_block = __block->_M_next;
> +      size_t __pos = __it._M_pos;
> +
> +      if (__block->_M_full())
> +       _M_blocks._M_append_free(__block);
> +
> +      _AllocT::destroy(_M_blocks._M_alloc, __block->_M_elem(__pos));
> +      _M_size -= 1;
> +
> +      if (__block->_M_release_slots(__pos, 1))
> +       {
> +         _M_blocks._M_unlink_free(__block);
> +         _M_blocks._M_hide(__block);
> +       }
> +
> +      if (__pos != __block->_M_capacity)
> +       return iterator(__block, __pos);
> +      else
> +       return iterator(__next_block);
> +    }
> +
> +    iterator
> +    erase(const_iterator __first, const_iterator __last)
> +    {
> +      _BlockT* __fblock = const_cast<_BlockT*>(__first._M_block);
> +      _BlockT* __lblock = const_cast<_BlockT*>(__last._M_block);
> +      if (__fblock == __lblock)
> +       {
> +         // Erase of range in single block, clear elements if any.
> +         if (__first._M_pos != __last._M_pos)
> +           _M_erase_range(__fblock, __first._M_pos, __last._M_pos);
> +         return iterator(__last._M_block, __last._M_pos);
> +       }
> +
> +      // Remove any elements designated in last block
> +      if (auto __lfirst = __lblock->_M_first_occupied(); __last._M_pos !=
> __lfirst)
> +       _M_erase_range(__lblock, __lfirst, __last._M_pos);
> +
> +      // If __first block is not set to be fully cleared, remove
> designated elements
> +      if (__first._M_pos != __fblock->_M_first_occupied())
> +       {
> +         _M_erase_range(__fblock, __first._M_pos, __fblock->_M_capacity);
> +         __fblock = __fblock->_M_next;
> +         if (__fblock == __lblock)
> +           return iterator(__last._M_block, __last._M_pos);
> +       }
> +
> +      // Clear elements in fully erased block, and move to reserved list.
> +      _M_clear(__fblock, __lblock);
> +      _M_blocks._M_hide(__fblock, __lblock->_M_prev);
> +      return iterator(__last._M_block, __last._M_pos);
> +    }
> +
> +    void
> +    clear()
> +    {
> +      if (empty())
> +       return;
> +
> +      _M_clear(_M_blocks._M_first, &_M_blocks._M_sent);
> +      _M_blocks._M_hide(_M_blocks._M_first, _M_blocks._M_sent._M_prev);
> +    }
> +
> +    void
> +    splice(hive& __other)
> +    {
> +      __glibcxx_assert(get_allocator() == __other.get_allocator());
> +      if (this == std::addressof(__other)) [[unlikely]]
> +       {
> +         __glibcxx_assert(this == std::addressof(__other));
> +         return;
> +       }
> +
> +      if (__other.empty())
> +       return;
> +
> +      _BlockListT& __src = __other._M_blocks;
> +      size_t __moved_cap = 0;
> +      for (const _BlockT* __block = __other._M_blocks._M_first;
> +          !__block->_M_sentinel(); __block = __block->_M_next)
> +       {
> +         const auto __cap = __block->_M_capacity;
> +         if (__cap  < _M_blocks._M_min_cap || __cap >
> _M_blocks._M_max_cap)
> +           std::__throw_length_error("hive::splice");
> +         __moved_cap += __cap;
> +       }
> +
> +      _M_blocks._M_splice_active(__other._M_blocks, __moved_cap);
> +      _M_size += __other._M_size;
> +      __other._M_size = 0;
> +    }
> +
> +    void
> +    splice(hive&& __other)
> +    { splice(__other); }
> +
> +    template<class _Predicate = equal_to<_Tp>>
> +      size_type
> +      unique(_Predicate __bin_pred = _Predicate())
> +      {
> +       _Tp* __last = nullptr;
> +       auto __pred = [&__last, &__bin_pred](_Tp& __e)
> +       {
> +         if (__last) [[likely]]
> +           if (__bin_pred(*__last, __e))
> +             return true;
> +
> +         __last = std::addressof(__e);
> +         return false;
> +       };
> +       return _M_erase_if(__pred);
> +      }
> +
> +    // TODO: sort
> +
> +    iterator
> +    get_iterator(const_pointer __ptr) noexcept
> +    {
> +      auto __eptr = reinterpret_cast<const
> _SlotT*>(std::to_address(__ptr));
> +      return _M_get_iterator(__eptr);
> +    }
> +
> +    const_iterator
> +    get_iterator(const_pointer __ptr) const noexcept
> +    {
> +      auto __eptr = reinterpret_cast<const
> _SlotT*>(std::to_address(__ptr));
> +      return _M_get_iterator(__eptr);
> +    }
> +
> +  private:
> +    // Used to value initialize elements
> +    struct _ValueInitTag
> +    { };
> +
> +    // Handles insertion of the elements to the single free node in the
> block.
> +    // In case of exceptions commits already constructed elements.
> +    struct _InsertGuard
> +    {
> +      hive& _M_self;
> +      _BlockT* _M_block;
> +      typename _BlockT::_Reservation _M_res;
> +      size_t _M_count = 0;
> +
> +      _InsertGuard(hive& __self, _BlockT* __block)
> +       : _M_self(__self)
> +       , _M_block(__block)
> +       , _M_res(_M_block->_M_reserve_slots())
> +      { }
> +
> +      [[__gnu__::__always_inline__]]
> +      bool
> +      _M_filled() const noexcept
> +      { return _M_count == _M_res._M_capacity; }
> +
> +      template<typename... _Args>
> +       void
> +       construct(_Alloc& __alloc, _Args&&... __args)
> +       {
> +         auto* __space = _M_block->_M_elem(_M_res._M_pos + _M_count);
> +         _AllocT::construct(__alloc, __space,
> std::forward<_Args>(__args)...);
> +         ++_M_count;
> +       }
> +
> +      void
> +      construct(_Alloc& __alloc, _ValueInitTag)
> +      { construct(__alloc); }
> +
> +      void
> +      _M_commit()
> +      {
> +       if (_M_count == 0) [[unlikely]]
> +         // Restore free slot node, that maybe overriden by
> +         // cosntruction attempt, block status does not change.
> +         _M_block->_M_commit_slots(_M_res, 0);
> +       else if (_M_res._M_capacity == _M_block->_M_capacity)
> +         {
> +           // Insertion into reserved block expose it to iteration,
> +           // and link to partially free list if not filled.
> +           _M_self._M_blocks._M_expose(_M_block);
> +           if (!_M_block->_M_commit_slots(_M_res, _M_count))
> +             _M_self._M_blocks._M_append_free(_M_block);
> +         }
> +       else if (_M_block->_M_commit_slots(_M_res, _M_count))
> +         // Unlink active block that was filled out.
> +         _M_self._M_blocks._M_unlink_free(_M_block);
> +
> +       _M_self._M_size += _M_count;
> +       _M_block = nullptr;
> +      }
> +
> +      ~_InsertGuard()
> +      {
> +       if (_M_block)
> +         _M_commit();
> +      }
> +    };
> +
> +    // Handles relocation of elements between blocks inside the same hive
> structure.
> +    // The blocks from which elements needs to be removed, are attached
> to the _M_aside
> +    // member, then transfered block by block by _M_transfer function
> (they emptied block
> +    // are linked as reverved in _M_blocks), and deallocated in guard
> destructuctor.
> +    //
> +    // In case if exception is throw during transfer, the destructor
> splices the blocks
> +    // back to the _M_self, and if the __first transfered back block have
> moved-from
> +    // elements remove them. For that reason, the elements inside the
> blocks are always
> +    // included in hvie size (and substracted when removed).
> +    struct _RelocateGuard
> +    {
> +      hive& _M_self;
> +      _BlockListT _M_aside;
> +      move_iterator<const_iterator> _M_last;
> +
> +      _RelocateGuard(hive& __self)
> +      : _M_self(__self)
> +      , _M_aside(__self.block_capacity_limits(), __self.get_allocator())
> +      , _M_last(const_iterator(&_M_aside._M_sent, 0))
> +      { }
> +
> +      ~_RelocateGuard()
> +      {
> +       _M_aside._M_trim_capacity();
> +       if (_M_last.base() == const_iterator(&_M_aside._M_sent, 0))
> +          return;
> +
> +       _BlockT* __last = _M_aside._M_first;
> +       _M_self._M_blocks._M_splice_active(_M_aside, _M_aside._M_capacity);
> +       // If exception was thrown during transfer from block, the starting
> +       // elements of the block until _M_last will be in moved from state,
> +       // erase them.
> +       _M_self.erase(const_iterator(__last), _M_last.base());
> +      }
> +
> +      void
> +      _M_move_active(_BlockT* __block)
> +      {
> +       _M_self._M_blocks._M_detach_active(__block, __block);
> +       _M_self._M_blocks._M_capacity -= __block->_M_capacity;
> +       _M_aside._M_append_active(__block, __block);
> +       _M_aside._M_capacity += __block->_M_capacity;
> +
> +       if (__block->_M_full())
> +         return;
> +
> +       _M_self._M_blocks._M_unlink_free(__block);
> +       _M_aside._M_append_free(__block);
> +      }
> +
> +      void
> +      _M_transfer()
> +      {
> +       _BlockT* __srcblock = _M_aside._M_first;
> +       _M_last = make_move_iterator(const_iterator(__srcblock));
> +       while (!__srcblock->_M_sentinel())
> +         {
> +           _BlockT* __nextblock = __srcblock->_M_next;
> +           auto __nextit =
> make_move_iterator(const_iterator(__nextblock));
> +
> +           while (_BlockT* __dstblock = _M_self._M_blocks._M_next_free())
> +             if (_M_self._M_fill_block(__dstblock, _M_last, __nextit))
> +               break;
> +
> +           if (!__srcblock->_M_full())
> +             _M_aside._M_unlink_free(__srcblock);
> +           _M_self._M_size -=
> __srcblock->_M_clear_elems(_M_self._M_blocks._M_alloc);
> +           _M_aside._M_hide(__srcblock);
> +
> +           __srcblock = __nextblock;
> +           _M_last = __nextit;
> +         }
> +      }
> +    };
> +
> +    // Checks the user provided limits, agains defined limits. The
> behavior of
> +    // erronous case (limits are not withing hard limits) is to:
> +    //  * use default limits if limits does not form a range
> +    //  * clamp provided value to the hard limits.
> +    static constexpr hive_limits
> +    _S_clamp_limits(hive_limits __limits)
> +    {
> +      __glibcxx_assert(is_within_hard_limits(__limits));
> +      if (__limits.min > __limits.max) [[unlikely]]
> +       return block_capacity_default_limits();
> +
> +      static constexpr auto __hard = block_capacity_hard_limits();
> +      if (__limits.max <= __hard.min) [[unlikely]]
> +       return hive_limits(__hard.min, __hard.min);
> +      if (__limits.min >= __hard.max) [[unlikely]]
> +       return hive_limits(__hard.max, __hard.max);
> +
> +      if (__limits.min < __hard.min) [[unlikely]]
> +       __limits.min = __hard.min;
> +      if (__limits.max > __hard.max) [[unlikely]]
> +       __limits.max = __hard.max;
> +      return __limits;
> +    }
> +
> +    iterator
> +    _M_get_iterator(const _SlotT* __ptr) const
> +    {
> +      std::less<const _SlotT*> __ptrlt;
> +      for (_BlockT* __block = _M_blocks._M_first;
> +          !__block->_M_sentinel(); __block = __block->_M_next)
> +       if (auto __pos = __block->_M_contains(__ptr); __pos !=
> _BlockT::npos)
> +         if (__block->_M_occupied(__pos))
> +           return iterator(__block, __pos);
> +         else
> +           break;
> +
> +      // Standard says that the behavior is undefined in case when __ptr
> does
> +      // not point to container. We return end() iterator for cases that
> can
> +      // be detected.
> +      __glibcxx_assert(false && "pointer does not point to element in
> container");
> +      return iterator(&_M_blocks._M_sent, 0);
> +    }
> +
> +    void
> +    _M_swap(hive& __other) noexcept
> +    {
> +      std::swap(_M_blocks._M_min_cap, __other._M_blocks._M_min_cap);
> +      std::swap(_M_blocks._M_max_cap, __other._M_blocks._M_max_cap);
> +      std::swap(_M_blocks._M_last_cap, __other._M_blocks._M_last_cap);
> +
> +      _M_blocks._M_swap_blocks(__other._M_blocks);
> +      std::swap(_M_size, __other._M_size);
> +    }
> +
> +    void
> +    _M_reserve(size_type __n, hive_limits __limits)
> +    {
> +      if (__n <= capacity())
> +       return;
> +
> +      // Rerved blocks are added to the front of the list, so we append
> larger
> +      // first, so they will be used from smallest to largest.
> +      for (__n -= capacity(); __n / 2 >= __limits.max; __n -=
> __limits.max)
> +       _M_blocks._M_reserve_block(__limits.max);
> +
> +      if (__n >= __limits.max)
> +       {
> +         _M_blocks._M_last_cap = __limits.max;
> +
> +         // If last block would be smaller than minum limit, try to
> +         // split last two blocks equally, to avoid going over capacity
> +         if ((__n > __limits.max)
> +             && (__n < __limits.max + __limits.min)
> +             && (__n >= 2 * __limits.min))
> +           {
> +             _M_blocks._M_reserve_block(__n - __n / 2);
> +             _M_blocks._M_reserve_block(__n / 2);
> +             return;
> +           }
> +
> +         _M_blocks._M_reserve_block(__limits.max);
> +         __n -= __limits.max;
> +       }
> +
> +      if (__n >= __limits.min)
> +       _M_blocks._M_reserve_block(__n);
> +      else if (__n > 0)
> +       _M_blocks._M_reserve_block(__limits.min);
> +    }
> +
> +
> +    // Returns position of element after last inserted element, or
> _M_capacity otherwise.
> +    template<typename _Iterator, typename _Sentinel>
> +      size_t
> +      _M_fill_free_head(_BlockT* __block, _Iterator& __first, _Sentinel
> __last)
> +      {
> +       _InsertGuard __guard(*this, __block);
> +       while ((__first != __last) && !__guard._M_filled())
> +         {
> +           __guard.construct(_M_blocks._M_alloc, *__first);
> +           ++__first;
> +         }
> +       __guard._M_commit();
> +       return __guard._M_res._M_pos + __guard._M_res._M_capacity;
> +      }
> +
> +    // Returns true if the whole range was inserted.
> +    template<typename _Iterator, typename _Sentinel>
> +      bool
> +      _M_fill_block(_BlockT* __block, _Iterator& __first, _Sentinel
> __last)
> +      {
> +       while (!__block->_M_full())
> +         {
> +           _M_fill_free_head(__block, __first, __last);
> +           if (__first == __last)
> +             return true;
> +         }
> +       return false;
> +      }
> +
> +    template<typename _Rg>
> +      void
> +      _M_insert_range(_Rg& __rg)
> +      {
> +       auto __it = std::ranges::begin(__rg);
> +       auto __end = std::ranges::end(__rg);
> +       if (__it == __end) [[unlikely]]
> +         return;
> +
> +       if constexpr (ranges::sized_range<_Rg>)
> +         {
> +           const auto __new_size = _M_size + size_t(ranges::size(__rg));
> +           reserve(__new_size);
> +
> +           // Fillout initial blocks, we do not need to check against end
> +           // TODO: should we store freee space in block, for better
> condition
> +           for (_BlockT* __block = _M_blocks._M_next_free();
> +                _M_size + __block->_M_capacity < __new_size;
> +                __block = _M_blocks._M_next_free())
> +             _M_fill_block(__block, __it, unreachable_sentinel);
> +
> +           // For the black that we are not sure will be filled fully,
> +           // check against end
> +           while (_BlockT* __block = _M_blocks._M_next_free())
> +             if (_M_fill_block(__block, __it, __end))
> +               return;
> +         }
> +       else
> +         {
> +           // Fill out empty spaces in existing blocks.
> +           while (_BlockT* __block = _M_blocks._M_next_free())
> +             if (_M_fill_block(__block, __it, __end))
> +               return;
> +
> +           // Allocate new blocks for remaining elements
> +           while (true)
> +             {
> +               _BlockT* __block = _M_blocks._M_reserve_block();
> +               if (_M_fill_block(__block, __it, __end))
> +                 return;
> +             }
> +         }
> +      }
> +
> +    template<typename _Up>
> +      void
> +      _M_insert_n(size_type __count, const _Up& __val)
> +      {
> +       insert(std::__make_repeat_iterator(__val, size_type(0)),
> +              std::__make_repeat_iterator(__val, __count));
> +      }
> +
> +    // Returns position of element after last assigned/inserted element,
> or _M_capacity otherwise.
> +    template<typename _Iterator, typename _Sentinel>
> +      size_t
> +      _M_assign_block(_BlockT* __block, _Iterator& __first, _Sentinel
> __last)
> +      {
> +       size_t __pos = 0;
> +       while ((__pos != __block->_M_capacity) && (__first != __last))
> +         if (__block->_M_occupied(__pos))
> +           {
> +             *__block->_M_elem(__pos++) = *__first;
> +             ++__first;
> +           }
> +         else
> +           {
> +             // Preserve order of elements, by inserting at that position.
> +             __block->_M_move_free_head(__pos);
> +             __pos = _M_fill_free_head(__block, __first, __last);
> +           }
> +       return __pos;
> +      }
> +
> +    template<__detail::__container_compatible_range<_Tp> _Rg>
> +      void
> +      _M_assign_range(_Rg& __rg)
> +      {
> +       if (empty())
> +         return _M_insert_range(__rg);
> +
> +       auto __it = std::ranges::begin(__rg);
> +       auto __end = std::ranges::end(__rg);
> +       if (__it == __end)
> +          return clear();
> +
> +       auto __erase_from = [&](_BlockT* __block, size_t __pos)
> +         {
> +           if (__pos == __block->_M_capacity)
> +             erase(const_iterator(__block->_M_next), end());
> +           else if (__block->_M_occupied(__pos))
> +             erase(const_iterator(__block, __pos), end());
> +           else
> +            {
> +              // Move to first occupied slot or end of block
> +              __pos += __block->_M_free_count(__pos);
> +              if (__pos == __block->_M_capacity)
> +                erase(const_iterator(__block->_M_next), end());
> +              else
> +                erase(const_iterator(__block, __pos), end());
> +            }
> +         };
> +
> +       if constexpr (ranges::sized_range<_Rg>)
> +         {
> +           const auto __size = size_t(ranges::size(__rg));
> +           reserve(__size);
> +
> +           size_t __assigned = 0;
> +           // Assing/inserter elements to existing active blocks
> +           for (_BlockT* __block = _M_blocks._M_first;
> +                !__block->_M_sentinel(); __block = __block->_M_next)
> +             if (__assigned == __size)
> +               {
> +                 erase(const_iterator(__block), end());
> +                 return;
> +               }
> +             else if (__assigned + __block->_M_capacity > __size)
> +               {
> +                 // Block is partially filled, insert until end,
> +                 // and then erase rest of the container elements.
> +                 size_t __last = _M_assign_block(__block, __it, __end);
> +                 __erase_from(__block, __last);
> +                 return;
> +               }
> +             else
> +               {
> +                 // Fully assign block, we do not need to check end
> +                 _M_assign_block(__block, __it, unreachable_sentinel);
> +                 __assigned += __block->_M_capacity;
> +               }
> +
> +           // Insert remaining elements
> +           insert_range(ranges::subrange(std::move(__it), __end,
> +                                         __size - __assigned));
> +         }
> +       else
> +         {
> +           // Assing/inserter elements to existing active blocks
> +           for (_BlockT* __block = _M_blocks._M_first;
> +                !__block->_M_sentinel(); __block = __block->_M_next)
> +             {
> +               size_t __last = _M_assign_block(__block, __it, __end);
> +               if (__it == __end)
> +                 return __erase_from(__block, __last);
> +             }
> +
> +           // Insert remaining elements
> +           insert_range(ranges::subrange(std::move(__it), __end));
> +         }
> +      }
> +
> +    // Erase elements from the block from which predicate is true.
> +    template<typename _Pred>
> +      void
> +      _M_block_erase_if(_BlockT* __block, _Pred __pred,
> +                       size_t __from, size_t __to)
> +      {
> +       static constexpr bool __always
> +         = is_same_v<_Pred, __gnu_cxx::__ops::_Always>;
> +
> +       // We know that blcok have at least one element, so
> +       // add it to free list now.
> +       if constexpr (__always)
> +         if (__block->_M_full())
> +           _M_blocks._M_append_free(__block);
> +
> +         auto __release = [&] (size_t __count)
> +                {
> +           if constexpr (!__always)
> +             if (__block->_M_full())
> +               _M_blocks._M_append_free(__block);
> +
> +           __block->_M_release_slots(__from, __count);
> +           _M_size -= __count;
> +           return __from;
> +         };
> +
> +       size_t __pos = __from;
> +       while (__pos != __to)
> +         {
> +           if (!__block->_M_occupied(__pos))
> +             {
> +               if (__always || __pos >= __from)
> +                 __pos = __release(__pos - __from);
> +               else
> +                 __from = (__pos += __block->_M_free_count(__pos));
> +               continue;
> +             }
> +
> +           if (__pred(*__block->_M_elem(__pos)))
> +             _AllocT::destroy(_M_blocks._M_alloc,
> __block->_M_elem(__pos));
> +           else if constexpr (!__always)
> +             {
> +               if (__pos > __from)
> +                 __release(__pos - __from);
> +               __from = __pos + 1;
> +             }
> +           ++__pos;
> +         }
> +
> +       if (size_t __count = __pos - __from)
> +         __release(__count);
> +      }
> +
> +    void
> +    _M_erase_range(_BlockT* __block, size_t __from, size_t __to)
> +    {
> +      __gnu_cxx::__ops::_Always __always;
> +      _M_block_erase_if(__block, __always, __from, __to);
> +    }
> +
> +    template<typename _Pred>
> +      size_t
> +      _M_erase_if(_Pred __pred)
> +      {
> +       size_t __old_size = _M_size;
> +
> +       _BlockT* __block = _M_blocks._M_first;
> +       while (!__block->_M_sentinel())
> +         {
> +           _M_block_erase_if(__block, __pred,
> __block->_M_first_occupied(),
> +                             __block->_M_capacity);
> +
> +           _BlockT* __next = __block->_M_next;
> +           if (__block->_M_empty())
> +             {
> +               _M_blocks._M_unlink_free(__block);
> +               _M_blocks._M_hide(__block);
> +             }
> +           __block = __next;
> +         }
> +
> +       return __old_size - _M_size;
> +      }
> +
> +    // Destroy all elements from actvive blocks in given range
> +    void
> +    _M_clear(_BlockT* __from, _BlockT* __to)
> +    {
> +      for (; __from != __to; __from = __from->_M_next)
> +       {
> +         if (!__from->_M_full())
> +           _M_blocks._M_unlink_free(__from);
> +
> +         _M_size -= __from->_M_clear_elems(_M_blocks._M_alloc);
> +         __from->_M_clear_slots();
> +       }
> +    }
> +
> +    // Destroy all elments in the active block and deallocate all
> +    // of them.
> +    void
> +    _M_clear_and_trim()
> +    {
> +      for (_BlockT* __block = _M_blocks._M_first;
> +          __block != &_M_blocks._M_sent;
> +          __block = __block->_M_next)
> +       __block->_M_clear_elems(_M_blocks._M_alloc);
> +
> +      _M_blocks._M_drop_blocks();
> +      _M_size = 0;
> +    }
> +
> +    _BlockListT _M_blocks;
> +    size_type _M_size = 0;
> +
> +    template<typename _Up, typename _OAlloc, typename _Predicate>
> +      friend typename hive<_Up, _OAlloc>::size_type
> +      erase_if(hive<_Up, _OAlloc>& __cont, _Predicate __pred);
> +  };
> +
> +  template<class _Tp, class _Alloc>
> +    void swap(hive<_Tp, _Alloc>& __lhs, hive<_Tp, _Alloc>& __rhs)
> +    noexcept(noexcept(__lhs.swap(__rhs)))
> +    { __lhs.swap(__rhs); }
> +
> +  template<typename _Tp, typename _Alloc, typename _Predicate>
> +    typename hive<_Tp, _Alloc>::size_type
> +    erase_if(hive<_Tp, _Alloc>& __hive, _Predicate __pred)
> +    { return __hive._M_erase_if(std::move(__pred)); }
> +
> +  template<typename _Tp, typename _Alloc, typename _Up = _Tp>
> +    typename hive<_Tp, _Alloc>::size_type
> +    erase(hive<_Tp, _Alloc>& __hive, const _Up& __value)
> +    { return std::erase_if(__hive,
> __gnu_cxx::__ops::__equal_to(__value)); }
> +
> +_GLIBCXX_END_NAMESPACE_VERSION
> +} // namespace std
> +
> +#endif /* __glibcxx_hive */
> +#endif /* _BITS_HIVE_H */
> diff --git a/libstdc++-v3/include/bits/predefined_ops.h
> b/libstdc++-v3/include/bits/predefined_ops.h
> index 83ce29b9231..c6ffa06c3fb 100644
> --- a/libstdc++-v3/include/bits/predefined_ops.h
> +++ b/libstdc++-v3/include/bits/predefined_ops.h
> @@ -203,6 +203,17 @@ namespace __ops
>      __equal_to(const _Value& __val)
>      { return _Comp_with_val_2nd<equal_to, _Value>(equal_to(), __val); }
>
> +  struct _Always
> +  {
> +#pragma GCC diagnostic push
> +#pragma GCC diagnostic ignored "-Wc++23-extensions" // static operator()
> +    template<typename _Tp>
> +      static _GLIBCXX_CONSTEXPR bool
> +      operator()(const _Tp&) _GLIBCXX_NOEXCEPT
> +      { return true; }
> +#pragma GCC diagnostic pop
> +  };
> +
>  } // namespace __ops
>  } // namespace __gnu_cxx
>
> diff --git a/libstdc++-v3/include/bits/version.def
> b/libstdc++-v3/include/bits/version.def
> index 9c523581c65..95214fc8546 100644
> --- a/libstdc++-v3/include/bits/version.def
> +++ b/libstdc++-v3/include/bits/version.def
> @@ -2518,6 +2518,15 @@ ftms = {
>    };
>  };
>
> +ftms = {
> +  name = hive;
> +  values = {
> +    v = 1; // set to 202502 when implemented
> +    cxxmin = 26;
> +    no_stdname = true;
> +  };
> +};
> +
>  ftms = {
>    name = within_lifetime;
>    // 202306 P2641R4 Checking if a union alternative is active
> diff --git a/libstdc++-v3/include/bits/version.h
> b/libstdc++-v3/include/bits/version.h
> index e0003054af6..340c892f978 100644
> --- a/libstdc++-v3/include/bits/version.h
> +++ b/libstdc++-v3/include/bits/version.h
> @@ -2774,6 +2774,15 @@
>  #endif /* !defined(__cpp_lib_valarray) */
>  #undef __glibcxx_want_valarray
>
> +#if !defined(__cpp_lib_hive)
> +# if (__cplusplus >  202302L)
> +#  define __glibcxx_hive 1L
> +#  if defined(__glibcxx_want_all) || defined(__glibcxx_want_hive)
> +#  endif
> +# endif
> +#endif /* !defined(__cpp_lib_hive) */
> +#undef __glibcxx_want_hive
> +
>  #if !defined(__cpp_lib_within_lifetime)
>  # if (__cplusplus >  202302L) &&
> (__has_builtin(__builtin_is_within_lifetime))
>  #  define __glibcxx_within_lifetime 202603L
> diff --git a/libstdc++-v3/include/std/hive b/libstdc++-v3/include/std/hive
> new file mode 100644
> index 00000000000..a4a532cd025
> --- /dev/null
> +++ b/libstdc++-v3/include/std/hive
> @@ -0,0 +1,55 @@
> +// <vector> -*- C++ -*-
> +
> +// Copyright (C) 2026 Free Software Foundation, Inc.
> +//
> +// This file is part of the GNU ISO C++ Library.  This library is free
> +// software; you can redistribute it and/or modify it under the
> +// terms of the GNU General Public License as published by the
> +// Free Software Foundation; either version 3, or (at your option)
> +// any later version.
> +
> +// This library is distributed in the hope that it will be useful,
> +// but WITHOUT ANY WARRANTY; without even the implied warranty of
> +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
> +// GNU General Public License for more details.
> +
> +// Under Section 7 of GPL version 3, you are granted additional
> +// permissions described in the GCC Runtime Library Exception, version
> +// 3.1, as published by the Free Software Foundation.
> +
> +// You should have received a copy of the GNU General Public License and
> +// a copy of the GCC Runtime Library Exception along with this program;
> +// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
> +// <http://www.gnu.org/licenses/>.
> +
> +/** @file include/hive
> + *  This is a Standard C++ Library header.
> + */
> +
> +#ifndef _GLIBCXX_HIVE
> +#define _GLIBCXX_HIVE 1
> +
> +#ifdef _GLIBCXX_SYSHDR
> +#pragma GCC system_header
> +#endif
> +
> +#define __glibcxx_want_hive
> +#include <bits/version.h>
> +
> +#ifdef __glibcxx_hive // C++ >= 26
> +
> +#include <bits/hive.h>
> +#include <bits/memory_resource.h>
> +
> +namespace std _GLIBCXX_VISIBILITY(default)
> +{
> +_GLIBCXX_BEGIN_NAMESPACE_VERSION
> +  namespace pmr {
> +    template<typename _Tp>
> +      using hive = std::hive<_Tp, polymorphic_allocator<_Tp>>;
> +  } // namespace pmr
> +_GLIBCXX_END_NAMESPACE_VERSION
> +} // namespace std
> +#endif // C++17
> +
> +#endif /* _GLIBCXX_HIVE */
> diff --git a/libstdc++-v3/testsuite/23_containers/hive/access.cc
> b/libstdc++-v3/testsuite/23_containers/hive/access.cc
> new file mode 100644
> index 00000000000..d4aefaa5772
> --- /dev/null
> +++ b/libstdc++-v3/testsuite/23_containers/hive/access.cc
> @@ -0,0 +1,67 @@
> +// { dg-do run { target c++26 } }
> +
> +#include <hive>
> +
> +#include <algorithm>
> +#include <array>
> +#include <ranges>
> +#include <testsuite_hooks.h>
> +
> +void
> +test_access(std::hive_limits hl)
> +{
> +  std::size_t n = 100;
> +  auto iota = std::views::indices(n);
> +  std::hive<int> h(std::from_range, iota, hl);
> +  const std::hive<int>& ch = h;
> +
> +  VERIFY( std::ranges::equal(
> +    h.begin(), h.end(),
> +    std::ranges::begin(iota), std::ranges::end(iota)) );
> +  VERIFY( std::ranges::equal(
> +    h.cbegin(), h.cend(),
> +    std::ranges::begin(iota), std::ranges::end(iota)) );
> +  VERIFY( std::ranges::equal(
> +    ch.begin(), ch.end(),
> +    std::ranges::begin(iota), std::ranges::end(iota)) );
> +
> +  VERIFY( std::ranges::equal(
> +    h.rbegin(), h.rend(),
> +    std::ranges::rbegin(iota), std::ranges::rend(iota)) );
> +  VERIFY( std::ranges::equal(
> +    h.crbegin(), h.crend(),
> +    std::ranges::rbegin(iota), std::ranges::rend(iota)) );
> +  VERIFY( std::ranges::equal(
> +    ch.rbegin(), ch.rend(),
> +    std::ranges::rbegin(iota), std::ranges::rend(iota)) );
> +
> +
> +  for (size_t i = 0; i < n; i += 13)
> +  {
> +    auto it = std::next(h.begin(), i);
> +    auto ptr = &*it;
> +    VERIFY( *it == i );
> +    auto cit = std::next(ch.begin(), i);
> +    VERIFY( it == cit );
> +    VERIFY( &*cit == ptr );
> +
> +    auto rit = std::prev(h.end(), n - i);
> +    VERIFY( &*rit == ptr );
> +    auto crit = std::prev(ch.end(), n - i);
> +    VERIFY( &*crit == ptr );
> +
> +    auto pit = h.get_iterator(ptr);
> +    VERIFY( pit == it );
> +    VERIFY( &*pit == ptr );
> +    auto cpit = ch.get_iterator(ptr);
> +    VERIFY( cpit == it );
> +    VERIFY( &*cpit == ptr );
> +  }
> +}
> +
> +int main()
> +{
> +  test_access(std::hive<int>::block_capacity_default_limits());
> +  test_access(std::hive_limits(10, 50));
> +  test_access(std::hive_limits(2, 7));
> +}
> diff --git a/libstdc++-v3/testsuite/23_containers/hive/assign.cc
> b/libstdc++-v3/testsuite/23_containers/hive/assign.cc
> new file mode 100644
> index 00000000000..258c0dd1f7f
> --- /dev/null
> +++ b/libstdc++-v3/testsuite/23_containers/hive/assign.cc
> @@ -0,0 +1,158 @@
> +// { dg-do run { target c++26 } }
> +
> +#include <hive>
> +
> +#include <algorithm>
> +#include <testsuite_hooks.h>
> +
> +struct Tracker
> +{
> +  static inline size_t copy = 0;
> +  static inline size_t assign = 0;
> +  static inline size_t create = 0;
> +  static inline size_t destroy = 0;
> +
> +  static void resetCounters()
> +  { create = copy = assign = destroy = 0; }
> +
> +  Tracker()
> +  : Tracker(0)
> +  {}
> +
> +  Tracker(int p)
> +  : x(p)
> +  { ++create; }
> +
> +  ~Tracker()
> +  { ++destroy; }
> +
> +  Tracker(const Tracker& other)
> +  : x(other.x)
> +  { ++copy; }
> +
> +  Tracker& operator=(const Tracker& other)
> +  { ++assign; this->x = other.x; return *this; }
> +
> +  int x;
> +
> +  friend constexpr bool
> +  operator==(const Tracker&, const Tracker&) = default;
> +
> +  friend constexpr bool
> +  operator==(const Tracker& nm, int y)
> +  { return nm.x == y; }
> +};
> +
> +template<typename Op>
> +void test_limits(Op&& op, std::hive_limits hl)
> +{
> +  std::hive<Tracker> h(hl);
> +  Tracker::resetCounters();
> +  op(h);
> +  VERIFY( Tracker::copy == 10 );
> +  VERIFY( Tracker::assign == 0 );
> +  VERIFY( Tracker::destroy == 0 );
> +
> +  h.insert(10, Tracker(20));
> +  Tracker::resetCounters();
> +  op(h);
> +  VERIFY( Tracker::copy == 0 );
> +  VERIFY( Tracker::assign == 10 );
> +  VERIFY( Tracker::destroy == 10 );
> +
> +  h.erase(std::next(h.begin(), 3), h.end());
> +  Tracker::resetCounters();
> +  op(h);
> +  VERIFY( Tracker::copy == 7 );
> +  VERIFY( Tracker::assign == 3 );
> +  VERIFY( Tracker::destroy == 0 );
> +
> +  h.erase(h.begin(), std::next(h.begin(), 6));
> +  Tracker::resetCounters();
> +  op(h);
> +  VERIFY( Tracker::copy == 6 );
> +  VERIFY( Tracker::assign == 4 );
> +  VERIFY( Tracker::destroy == 0 );
> +
> +  auto it = h.begin();
> +  it = h.erase(++it);
> +  it = h.erase(++it);
> +  it = h.erase(++it);
> +  it = h.erase(++it);
> +  Tracker::resetCounters();
> +
> +  op(h);
> +  VERIFY( Tracker::copy == 4 );
> +  VERIFY( Tracker::assign == 6 );
> +  VERIFY( Tracker::destroy == 0 );
> +
> +  h.insert(7, Tracker(10));
> +  it = h.begin();
> +  it = h.erase(++it);
> +  it = h.erase(++it);
> +  it = h.erase(++it);
> +  it = h.erase(++it);
> +  it = h.erase(++it);
> +  it = h.erase(++it);
> +  it = h.erase(++it);
> +  it = h.erase(++it);
> +  Tracker::resetCounters();
> +
> +  op(h);
> +  // Block need to have at least 2 elements, so all remain active
> +  VERIFY( Tracker::copy == 5 );
> +  VERIFY( Tracker::assign == 5 );
> +  VERIFY( Tracker::destroy == 4 );
> +
> +  h.insert(11, Tracker(10));
> +  it = h.begin();
> +  it = h.erase(std::next(it, 2), std::next(it, 7));
> +  it = h.erase(std::next(it, 2), std::next(it, 7));
> +  it = h.erase(std::next(it, 2), std::next(it, 7));
> +  Tracker::resetCounters();
> +
> +  op(h);
> +  // Whole blocks may be cleared, so check total operations
> +  VERIFY( Tracker::copy + Tracker::assign == 10 );
> +  VERIFY( Tracker::assign + Tracker::destroy == 6 );
> +}
> +
> +template<typename Op>
> +void test_assign(Op&& op)
> +{
> +  test_limits(op, std::hive<Tracker>::block_capacity_default_limits());
> +  test_limits(op, std::hive_limits(20, 50));
> +  test_limits(op, std::hive_limits(5, 10));
> +  test_limits(op, std::hive_limits(10, 10));
> +  test_limits(op, std::hive_limits(2, 4));
> +}
> +
> +int main()
> +{
> +  std::initializer_list<Tracker> il{11, 12, 13, 14, 15, 26, 27, 28, 29,
> 30};
> +  const std::hive<Tracker> src(il);
> +
> +  test_assign([il, &src](std::hive<Tracker>& dst) {
> +    dst = src;
> +    VERIFY( std::ranges::equal(dst, il) );
> +    VERIFY( std::ranges::equal(src, il) );
> +  });
> +  test_assign([il, &src](std::hive<Tracker>& dst) {
> +    dst = il;
> +    VERIFY( std::ranges::equal(dst, il) );
> +    VERIFY( std::ranges::equal(src, il) );
> +  });
> +  test_assign([il](std::hive<Tracker>& dst) {
> +    dst.assign_range(il);
> +    VERIFY( std::ranges::equal(dst, il) );
> +  });
> +  test_assign([il](std::hive<Tracker>& dst) {
> +    dst.assign(il.begin(), il.end());
> +    VERIFY( std::ranges::equal(dst, il) );
> +  });
> +  test_assign([il](std::hive<Tracker>& dst) {
> +    dst.assign(il);
> +    VERIFY( std::ranges::equal(dst, il) );
> +  });
> +
> +}
> diff --git a/libstdc++-v3/testsuite/23_containers/hive/capacity.cc
> b/libstdc++-v3/testsuite/23_containers/hive/capacity.cc
> new file mode 100644
> index 00000000000..03947577035
> --- /dev/null
> +++ b/libstdc++-v3/testsuite/23_containers/hive/capacity.cc
> @@ -0,0 +1,383 @@
> +// { dg-do run { target c++26 } }
> +
> +#include <hive>
> +
> +#include <algorithm>
> +#include <array>
> +#include <ranges>
> +#include <testsuite_hooks.h>
> +
> +struct BlockCounter
> +{
> +  size_t count = 0;
> +  size_t min = size_t(-1);
> +  size_t max = 0;
> +
> +  void resetBounds()
> +  {
> +    min = size_t(-1);
> +    max = 0;
> +  }
> +};
> +
> +template<typename T, typename SizeType = size_t, size_t Max =
> SizeType(-1)>
> +struct TrackingAlloc
> +{
> +  using value_type = T;
> +  using size_type = SizeType;
> +
> +  template<typename U>
> +    struct rebind
> +    { using other = TrackingAlloc<U, SizeType, Max>; };
> +
> +  constexpr
> +  TrackingAlloc(BlockCounter& param)
> +  : counter(&param)
> +  { }
> +
> +  template<typename U, typename OSizeType, OSizeType OMax>
> +  constexpr
> +  TrackingAlloc(const TrackingAlloc<U, OSizeType, OMax>& other)
> +  : counter(other.counter)
> +  { }
> +
> +  static constexpr
> +  size_type max_size() noexcept
> +    requires (Max != size_type(-1))
> +  { return size_type(Max); }
> +
> +  T* allocate(size_t n)
> +  {
> +    if (n < counter->min)
> +      counter->min = n;
> +    if (n > counter->max)
> +      counter->max = n;
> +    ++counter->count;
> +    return std::allocator<T>{}.allocate(n);
> +  }
> +
> +  void deallocate(T* ptr, size_t n)
> +  {
> +    --counter->count;
> +    std::allocator<T>{}.deallocate(ptr, n);
> +  }
> +
> +private:
> +  BlockCounter* counter;
> +
> +  template<typename, typename, size_t>
> +    friend class TrackingAlloc;
> +};
> +
> +constexpr bool
> +limits_eq(std::hive_limits lhs, std::hive_limits rhs)
> +{ return lhs.min == rhs.min && lhs.max == rhs.max; }
> +
> +template<typename Hive>
> +constexpr bool
> +limits_eq(const Hive& hive, std::hive_limits rhs)
> +{ return limits_eq(hive.block_capacity_limits(), rhs); }
> +
> +template<typename Tp, typename Alloc>
> +constexpr size_t
> +adjusted_count(size_t n)
> +{
> +  // This peeks into implementation to provide actual counter,
> +  // as block is allocated inside memnory region,
> +  return n + std::__hive::_Block_list<Tp,
> Alloc>::_BlockT::_S_extra_slots(n);
> +}
> +
> +template<typename Tp, typename Alloc>
> +constexpr size_t
> +adjusted_count(const std::hive<Tp, Alloc>&, size_t n)
> +{ return adjusted_count<Tp, Alloc>(n); }
> +
> +template<typename SizeType = size_t, size_t Max = SizeType(-1)>
> +constexpr bool
> +max_size_respected()
> +{
> +  using T = std::array<size_t, 4>;
> +  using Alloc = TrackingAlloc<T, SizeType, Max>;
> +
> +  BlockCounter bc;
> +  std::hive_limits hl = std::hive<T, Alloc>::block_capacity_hard_limits();
> +  return adjusted_count<T, Alloc>(hl.max)
> +          <= std::allocator_traits<Alloc>::max_size(Alloc(bc));
> +}
> +
> +static_assert( max_size_respected<unsigned char>() );
> +static_assert( max_size_respected<unsigned char, 12>() );
> +static_assert( max_size_respected<unsigned short>() );
> +static_assert( max_size_respected<unsigned short, 1024>() );
> +static_assert( max_size_respected<unsigned int>() );
> +static_assert( max_size_respected<unsigned int, 66'000>() );
> +
> +void
> +test_over()
> +{
> +  BlockCounter bc;
> +  std::hive<int, TrackingAlloc<int>> h(140, 10, std::hive_limits(30, 40),
> bc);
> +  VERIFY( h.capacity() == 140 );
> +  VERIFY( bc.count == 4 );
> +  VERIFY( bc.min >= adjusted_count(h, 30) );
> +  VERIFY( bc.max <= adjusted_count(h, 40) );
> +
> +  h.reserve(160);
> +  VERIFY( h.capacity() == 170 );
> +  VERIFY( bc.count == 5 );
> +  VERIFY( bc.min >= adjusted_count(h, 30) );
> +  VERIFY( bc.max <= adjusted_count(h, 40) );
> +
> +  // Elements are not removed
> +  h.trim_capacity(110);
> +  VERIFY( h.capacity() == 140 );
> +  VERIFY( bc.count == 4 );
> +
> +  h.trim_capacity();
> +  VERIFY( h.capacity() == 140 );
> +  VERIFY( bc.count == 4 );
> +
> +  h.clear();
> +  h.trim_capacity(120);
> +  VERIFY( h.capacity() == 140 );
> +  VERIFY( bc.count == 4 );
> +
> +  h.trim_capacity(80);
> +  VERIFY( h.capacity() == 80 );
> +  VERIFY( bc.count == 2 );
> +
> +  h.trim_capacity();
> +  VERIFY( h.capacity() == 0 );
> +  VERIFY( bc.count == 0 );
> +
> +  // Allocates blocks of size 40 and 30
> +  h.reserve(50);
> +  VERIFY( h.capacity() == 70 );
> +  VERIFY( bc.count == 2 );
> +}
> +
> +void
> +test_exact()
> +{
> +  BlockCounter bc;
> +  std::hive<int, TrackingAlloc<int>> h(std::hive_limits(2, 10), bc);
> +
> +  h.reserve(10);
> +  VERIFY( h.capacity() == 10 );
> +  VERIFY( bc.count == 1 );
> +  VERIFY( bc.min == adjusted_count(h, 10) );
> +  VERIFY( bc.max == adjusted_count(h, 10) );
> +
> +  h.reserve(14);
> +  VERIFY( h.capacity() == 14 );
> +  VERIFY( bc.count == 2 );
> +  VERIFY( bc.min == adjusted_count(h, 4) );
> +  VERIFY( bc.max == adjusted_count(h, 10) );
> +
> +  h.reserve(16);
> +  VERIFY( h.capacity() == 16 );
> +  VERIFY( bc.count == 3 );
> +  VERIFY( bc.min == adjusted_count(h, 2) );
> +  VERIFY( bc.max == adjusted_count(h, 10) );
> +
> +  h.reserve(20);
> +  VERIFY( h.capacity() == 20 );
> +  VERIFY( bc.count == 4 );
> +  VERIFY( bc.min == adjusted_count(h, 2) );
> +  VERIFY( bc.max == adjusted_count(h, 10) );
> +
> +  h.reserve(30);
> +  VERIFY( h.capacity() == 30 );
> +  VERIFY( bc.count == 5 );
> +  VERIFY( bc.min == adjusted_count(h, 2) );
> +  VERIFY( bc.max == adjusted_count(h, 10) );
> +
> +  // h has now blocks 10,4,2,4,10, remove 10 and 2
> +  h.trim_capacity(18);
> +  VERIFY( h.capacity() == 18 );
> +  VERIFY( bc.count == 3 );
> +
> +  h.trim_capacity(10);
> +  VERIFY( h.capacity() == 10 );
> +  VERIFY( bc.count == 1 );
> +}
> +
> +void
> +test_shrink_to_fit()
> +{
> +  BlockCounter bc;
> +  std::hive<int, TrackingAlloc<int>> h(std::hive_limits(10, 50), bc);
> +  h.insert_range(std::views::iota(0, 10));
> +  h.insert_range(std::views::iota(10, 20));
> +  h.insert_range(std::views::iota(20, 120));
> +  h.erase(std::next(h.begin(), 100), h.end());
> +  VERIFY( h.size() == 100 );
> +  VERIFY( h.capacity() == 120 );
> +  VERIFY( bc.count == 4 );
> +  VERIFY( bc.min == adjusted_count(h, 10) );
> +  VERIFY( bc.max == adjusted_count(h, 50) );
> +
> +  bc.resetBounds();
> +  // Replace two initial moved to last block
> +  h.shrink_to_fit();
> +  VERIFY( h.size() == 100 );
> +  VERIFY( h.capacity() == 100 );
> +  VERIFY( bc.count == 2 );
> +  VERIFY( bc.max == 0 ); // no allocations
> +  VERIFY( std::ranges::is_permutation(h, std::views::iota(0, 100)) );
> +
> +  // Add block of size 40
> +  h.reserve(140);
> +  VERIFY( h.capacity() == 140 );
> +  VERIFY( bc.count == 3 );
> +  std::erase_if(h, [](int x) { return x >= 70; });
> +  bc.resetBounds();
> +
> +  // Replace block of size 50 with one of size 20,
> +  // and remove reserved blocks
> +  h.shrink_to_fit();
> +  VERIFY( h.size() == 70 );
> +  VERIFY( h.capacity() == 70 );
> +  VERIFY( bc.count == 2 );
> +  VERIFY( bc.min == adjusted_count(h, 20) );
> +  VERIFY( bc.max == adjusted_count(h, 20) );
> +  VERIFY( std::ranges::is_permutation(h, std::views::iota(0, 70)) );
> +
> +  std::erase_if(h, [](int x) { return x < 15; });
> +  bc.resetBounds();
> +
> +  // We have [50, 20) blocks, so 20 is reduced to 10
> +  // This guaranteed that capacity() - size() is always smaller than
> +  // minimum block size
> +  h.shrink_to_fit();
> +  VERIFY( h.size() == 55 );
> +  VERIFY( h.capacity() == 60 );
> +  VERIFY( bc.count == 2 );
> +  VERIFY( bc.min == adjusted_count(h, 10) );
> +  VERIFY( bc.max == adjusted_count(h, 10) );
> +  VERIFY( std::ranges::is_permutation(h, std::views::iota(15, 70)) );
> +
> +  // We iterator blocks in reverse order, as they are usually placed
> +  // in increasing order.
> +  h.reserve(70);
> +  h.reserve(100);
> +  h.insert_range(std::views::iota(0, 15));
> +  h.insert_range(std::views::iota(70, 100));
> +  VERIFY( h.capacity() == 100 );
> +  VERIFY( bc.count == 4 ); // 50, 10, 10, 30
> +  std::erase_if(h, [](int x) { return x % 2; });
> +  VERIFY( std::ranges::is_permutation(h, std::views::iota(0, 100) |
> std::views::stride(2)) );
> +  bc.resetBounds();
> +
> +  // This remove 10,10,30 blocks from the last
> +  h.shrink_to_fit();
> +  VERIFY( h.size() == 50 );
> +  VERIFY( h.capacity() == 50 );
> +  VERIFY( bc.count == 1 ); // 10, 10, 30
> +  VERIFY( bc.max == 0 ); // no allocations
> +  VERIFY( std::ranges::is_permutation(h, std::views::iota(0, 100) |
> std::views::stride(2)) );
> +}
> +
> +void
> +test_reshape()
> +{
> +  BlockCounter bc;
> +  std::hive<int, TrackingAlloc<int>> h(std::hive_limits(2, 50), bc);
> +
> +  h.insert_range(std::views::iota(0, 5));
> +  VERIFY( h.capacity() == 5 );
> +  VERIFY( bc.count == 1 );
> +  VERIFY( bc.min == adjusted_count(h, 5) );
> +  VERIFY( bc.max == adjusted_count(h, 5) );
> +
> +  h.insert_range(std::views::iota(5, 10));
> +  VERIFY( h.capacity() == 10 );
> +  VERIFY( bc.count == 2 );
> +  VERIFY( bc.min == adjusted_count(h, 5) );
> +  VERIFY( bc.max == adjusted_count(h, 5) );
> +
> +  h.insert_range(std::views::iota(10, 20));
> +  VERIFY( h.capacity() == 20 );
> +  VERIFY( bc.count == 3 );
> +  VERIFY( bc.min == adjusted_count(h, 5) );
> +  VERIFY( bc.max == adjusted_count(h, 10) );
> +
> +  h.insert_range(std::views::iota(20, 30));
> +  VERIFY( h.capacity() == 30 );
> +  VERIFY( bc.count == 4 );
> +  VERIFY( bc.min == adjusted_count(h, 5) );
> +  VERIFY( bc.max == adjusted_count(h, 10) );
> +
> +  h.insert_range(std::views::iota(30, 50));
> +  VERIFY( h.capacity() == 50 );
> +  VERIFY( bc.count == 5 );
> +  VERIFY( bc.min == adjusted_count(h, 5) );
> +  VERIFY( bc.max == adjusted_count(h, 20) );
> +
> +  h.insert_range(std::views::iota(50, 100));
> +  VERIFY( h.capacity() == 100 );
> +  VERIFY( bc.count == 6 );
> +  VERIFY( bc.min == adjusted_count(h, 5) );
> +  VERIFY( bc.max == adjusted_count(h, 50) );
> +
> +  h.insert_range(std::views::iota(100, 200));
> +  VERIFY( h.capacity() == 200 );
> +  VERIFY( bc.count == 8 );
> +  VERIFY( bc.min == adjusted_count(h, 5) );
> +  VERIFY( bc.max == adjusted_count(h, 50) );
> +
> +  h.reserve(280);
> +  VERIFY( h.capacity() == 280 );
> +  VERIFY( bc.count == 10 );
> +  VERIFY( bc.min == adjusted_count(h, 5) );
> +  VERIFY( bc.max == adjusted_count(h, 50) );
> +
> +  // h now has blocks of capacity 5,5,10,10,20,50,50,50,50,30
> +  VERIFY( std::ranges::equal(h, std::views::iota(0, 200)) );
> +
> +  h.reshape({5, 100});
> +  VERIFY( limits_eq(h, {5, 100}) );
> +  VERIFY( h.capacity() == 280 );
> +  VERIFY( bc.count == 10 );
> +  VERIFY( bc.min == adjusted_count(h, 5) );
> +  VERIFY( bc.max == adjusted_count(h, 50) );
> +  VERIFY( std::ranges::equal(h, std::views::iota(0, 200)) );
> +
> +  bc.resetBounds();
> +  // Removes reserved block of size 50, and replaces 3x50
> +  // blocks with 5x30, using one reserved
> +  h.reshape({5, 30});
> +  VERIFY( limits_eq(h, {5, 30}) );
> +  VERIFY( h.capacity() == 200 );
> +  VERIFY( bc.count == 10 );
> +  VERIFY( bc.min == adjusted_count(h, 30) );
> +  VERIFY( bc.max == adjusted_count(h, 30) );
> +  VERIFY( std::ranges::is_permutation(h, std::views::iota(0, 200)) );
> +
> +  // Replaces intial 5,5,10,10 blocks with one 30 block
> +  h.reshape(std::hive_limits(20, 30));
> +  VERIFY( limits_eq(h, {20, 30}) );
> +  VERIFY( h.capacity() == 200 );
> +  VERIFY( bc.count == 7 );
> +  VERIFY( bc.min == adjusted_count(h, 30) );
> +  VERIFY( bc.max == adjusted_count(h, 30) );
> +  VERIFY( std::ranges::is_permutation(h, std::views::iota(0, 200)) );
> +
> +  // Reallocate everything with 80 size blocks
> +  bc.resetBounds();
> +  h.reshape(std::hive_limits(80, 80));
> +  VERIFY( limits_eq(h, {80, 80}) );
> +  VERIFY( h.capacity() == 240 );
> +  VERIFY( bc.count == 3 );
> +  VERIFY( bc.min == adjusted_count(h, 80) );
> +  VERIFY( bc.max == adjusted_count(h, 80) );
> +  VERIFY( std::ranges::is_permutation(h, std::views::iota(0, 200)) );
> +}
> +
> +int main()
> +{
> +  test_over();
> +  test_exact();
> +  test_shrink_to_fit();
> +  test_reshape();
> +}
> diff --git a/libstdc++-v3/testsuite/23_containers/hive/copy_alloc.cc
> b/libstdc++-v3/testsuite/23_containers/hive/copy_alloc.cc
> new file mode 100644
> index 00000000000..e0ac6aa555f
> --- /dev/null
> +++ b/libstdc++-v3/testsuite/23_containers/hive/copy_alloc.cc
> @@ -0,0 +1,335 @@
> +// { dg-do run { target c++26 } }
> +
> +#include <hive>
> +
> +#include <memory>
> +#include <scoped_allocator>
> +#include <utility>
> +#include <vector>
> +#include <testsuite_hooks.h>
> +#include <testsuite_allocator.h>
> +
> +using __gnu_test::propagating_allocator;
> +using __gnu_test::tracker_allocator;
> +using Counter = __gnu_test::tracker_allocator_counter;
> +
> +constexpr bool
> +limits_eq(std::hive_limits lhs, std::hive_limits rhs)
> +{ return lhs.min == rhs.min && lhs.max == rhs.max; }
> +
> +template<typename Hive>
> +constexpr bool
> +limits_eq(const Hive& hive, std::hive_limits rhs)
> +{ return limits_eq(hive.block_capacity_limits(), rhs); }
> +
> +template<typename Hive>
> +int
> +elem_alloc_personality(const Hive& hive)
> +{
> +  int front = hive.begin()->get_allocator().get_personality();
> +  int back = std::prev(hive.end())->get_allocator().get_personality();
> +  VERIFY( front == back );
> +  return front;
> +}
> +
> +template<bool Propagate>
> +void
> +test_ctor()
> +{
> +  using PropAlloc = propagating_allocator<int, Propagate>;
> +  using Vector = std::vector<int, PropAlloc>;
> +  using ScopedAlloc = std::scoped_allocator_adaptor<
> +    propagating_allocator<Vector, Propagate, tracker_allocator<Vector>>,
> +    PropAlloc>;
> +  using Hive = std::hive<Vector, ScopedAlloc>;
> +
> +  const std::hive_limits sl(10, 20);
> +  const Hive src({Vector{1, 2, 3}, Vector{4, 5, 6}},
> +                sl, ScopedAlloc{11, 22});
> +
> +  Counter::reset();
> +  Hive s1(src);
> +  VERIFY( std::ranges::equal(s1, src) );
> +  VERIFY( limits_eq(s1, sl) );
> +  if (Propagate)
> +  {
> +    VERIFY( s1.get_allocator().get_personality() == 11 );
> +    VERIFY( elem_alloc_personality(s1) == 22 );
> +  }
> +  else
> +  {
> +    VERIFY( s1.get_allocator().get_personality() == 0 );
> +    VERIFY( elem_alloc_personality(s1) == 0 );
> +  }
> +  VERIFY( Counter::get_allocation_count() >= 2 * sizeof(Vector) );
> +  VERIFY( Counter::get_deallocation_count() == 0 );
> +  VERIFY( Counter::get_construct_count() == 2 );
> +  VERIFY( Counter::get_destruct_count() == 0 );
> +
> +  Counter::reset();
> +  Hive d1(src, ScopedAlloc{33, 44});
> +  VERIFY( std::ranges::equal(d1, src) );
> +  VERIFY( limits_eq(d1, sl) );
> +  VERIFY( d1.get_allocator().get_personality() == 33 );
> +  VERIFY( elem_alloc_personality(d1) == 44 );
> +  VERIFY( Counter::get_allocation_count() >= sizeof(Vector) );
> +  VERIFY( Counter::get_deallocation_count() == 0 );
> +  VERIFY( Counter::get_construct_count() == 2 );
> +  VERIFY( Counter::get_destruct_count() == 0 );
> +}
> +
> +template<bool Propagate>
> +void
> +test_assign()
> +{
> +  using PropAlloc = propagating_allocator<int, Propagate>;
> +  using Vector = std::vector<int, PropAlloc>;
> +  using ScopedAlloc = std::scoped_allocator_adaptor<
> +    propagating_allocator<Vector, Propagate, tracker_allocator<Vector>>,
> +    PropAlloc>;
> +  using Hive = std::hive<Vector, ScopedAlloc>;
> +
> +  const std::hive_limits dl(30, 50);
> +  const Vector vc{11, 12, 13};
> +  const Hive src({Vector{1, 2, 3}, Vector{4, 5, 6}},
> +                 std::hive_limits(10, 20), ScopedAlloc{11, 22});
> +
> +  Hive s0(dl, ScopedAlloc{11, 22});
> +  Counter::reset();
> +
> +  s0 = src;
> +  VERIFY( std::ranges::equal(s0, src) );
> +  VERIFY( limits_eq(s0, dl) );
> +  VERIFY( s0.get_allocator().get_personality() == 11 );
> +  VERIFY( elem_alloc_personality(s0) == 22 );
> +  VERIFY( Counter::get_allocation_count() >= 2 * sizeof(Vector) );
> +  VERIFY( Counter::get_deallocation_count() == 0 );
> +  VERIFY( Counter::get_construct_count() == 2 );
> +  VERIFY( Counter::get_destruct_count() == 0 );
> +
> +  Hive s1(1, vc, dl, ScopedAlloc{11, 22});
> +  Counter::reset();
> +
> +  s1 = src;
> +  VERIFY( std::ranges::equal(s1, src) );
> +  VERIFY( limits_eq(s1, dl) );
> +  VERIFY( s1.get_allocator().get_personality() == 11 );
> +  VERIFY( elem_alloc_personality(s1) == 22 );
> +  VERIFY( Counter::get_allocation_count() >= 0 );
> +  VERIFY( Counter::get_deallocation_count() == 0 );
> +  VERIFY( Counter::get_construct_count() == 1 );
> +  VERIFY( Counter::get_destruct_count() == 0 );
> +
> +  Hive s2(2, vc, dl, ScopedAlloc{11, 22});
> +  Counter::reset();
> +
> +  s2 = src;
> +  VERIFY( std::ranges::equal(s2, src) );
> +  VERIFY( limits_eq(s2, dl) );
> +  VERIFY( s2.get_allocator().get_personality() == 11 );
> +  VERIFY( elem_alloc_personality(s2) == 22 );
> +  VERIFY( Counter::get_allocation_count() == 0 );
> +  VERIFY( Counter::get_deallocation_count() == 0 );
> +  VERIFY( Counter::get_construct_count() == 0 );
> +  VERIFY( Counter::get_destruct_count() == 0 );
> +
> +  Hive s3(3, vc, dl, ScopedAlloc{11, 22});
> +  Counter::reset();
> +
> +  s3 = src;
> +  VERIFY( std::ranges::equal(s2, src) );
> +  VERIFY( limits_eq(s3, dl) );
> +  VERIFY( s3.get_allocator().get_personality() == 11 );
> +  VERIFY( elem_alloc_personality(s3) == 22 );
> +  VERIFY( Counter::get_allocation_count() == 0 );
> +  VERIFY( Counter::get_deallocation_count() == 0 );
> +  VERIFY( Counter::get_construct_count() == 0 );
> +  VERIFY( Counter::get_destruct_count() == 1 );
> +
> +  Hive d0(dl, ScopedAlloc{33, 44});
> +  Counter::reset();
> +
> +  d0 = src;
> +  VERIFY( std::ranges::equal(d0, src) );
> +  VERIFY( limits_eq(d0, dl) );
> +  if (Propagate)
> +  {
> +    VERIFY( d0.get_allocator().get_personality() == 11 );
> +    VERIFY( elem_alloc_personality(d0) == 22 );
> +  }
> +  else
> +  {
> +    VERIFY( d0.get_allocator().get_personality() == 33 );
> +    VERIFY( elem_alloc_personality(d0) == 44 );
> +  }
> +  VERIFY( Counter::get_allocation_count() >= 2 * sizeof(Vector) );
> +  VERIFY( Counter::get_deallocation_count() == 0 );
> +  VERIFY( Counter::get_construct_count() == 2 );
> +  VERIFY( Counter::get_destruct_count() == 0 );
> +
> +  Hive d1(1, vc, dl, ScopedAlloc{33, 44});
> +  Counter::reset();
> +
> +  d1 = src;
> +  VERIFY( std::ranges::equal(d1, src) );
> +  VERIFY( limits_eq(d1, dl) );
> +  if (Propagate)
> +  {
> +    VERIFY( d1.get_allocator().get_personality() == 11 );
> +    VERIFY( elem_alloc_personality(d1) == 22 );
> +    VERIFY( Counter::get_allocation_count() >= 2 * sizeof(Vector) );
> +    VERIFY( Counter::get_deallocation_count() >= sizeof(Vector) );
> +    VERIFY( Counter::get_construct_count() == 2 );
> +    VERIFY( Counter::get_destruct_count() == 1 );
> +  }
> +  else
> +  {
> +    VERIFY( d1.get_allocator().get_personality() == 33 );
> +    VERIFY( elem_alloc_personality(d1) == 44 );
> +    VERIFY( Counter::get_allocation_count() >= 0 );
> +    VERIFY( Counter::get_deallocation_count() == 0 );
> +    VERIFY( Counter::get_construct_count() == 1 );
> +    VERIFY( Counter::get_destruct_count() == 0 );
> +  }
> +
> +  Hive d2(2, vc, dl, ScopedAlloc{33, 44});
> +  Counter::reset();
> +
> +  d2 = src;
> +  VERIFY( std::ranges::equal(d2, src) );
> +  VERIFY( limits_eq(d2, dl) );
> +  if (Propagate)
> +  {
> +    VERIFY( d2.get_allocator().get_personality() == 11 );
> +    VERIFY( elem_alloc_personality(d2) == 22 );
> +    VERIFY( Counter::get_allocation_count() >= 2 * sizeof(Vector) );
> +    VERIFY( Counter::get_deallocation_count() >= 2 * sizeof(Vector) );
> +    VERIFY( Counter::get_construct_count() == 2 );
> +    VERIFY( Counter::get_destruct_count() == 2 );
> +  }
> +  else
> +  {
> +    VERIFY( d2.get_allocator().get_personality() == 33 );
> +    VERIFY( elem_alloc_personality(d2) == 44 );
> +    VERIFY( Counter::get_allocation_count() == 0 );
> +    VERIFY( Counter::get_deallocation_count() == 0 );
> +    VERIFY( Counter::get_construct_count() == 0 );
> +    VERIFY( Counter::get_destruct_count() == 0 );
> +  }
> +
> +  Hive d3(3, vc, dl, ScopedAlloc{33, 44});
> +  Counter::reset();
> +
> +  d3 = src;
> +  VERIFY( std::ranges::equal(d3, src) );
> +  VERIFY( limits_eq(d3, dl) );
> +  if (Propagate)
> +  {
> +    VERIFY( d3.get_allocator().get_personality() == 11 );
> +    VERIFY( elem_alloc_personality(d3) == 22 );
> +    VERIFY( Counter::get_allocation_count() >= 2 * sizeof(Vector) );
> +    VERIFY( Counter::get_deallocation_count() >= 3 * sizeof(Vector) );
> +    VERIFY( Counter::get_construct_count() == 2 );
> +    VERIFY( Counter::get_destruct_count() == 3 );
> +  }
> +  else
> +  {
> +    VERIFY( d3.get_allocator().get_personality() == 33 );
> +    VERIFY( elem_alloc_personality(d3) == 44 );
> +    VERIFY( Counter::get_allocation_count() == 0 );
> +    VERIFY( Counter::get_deallocation_count() == 0 );
> +    VERIFY( Counter::get_construct_count() == 0 );
> +    VERIFY( Counter::get_destruct_count() == 1 );
> +  }
> +}
> +
> +template<bool Propagate>
> +void
> +test_empty()
> +{
> +  using PropAlloc = propagating_allocator<int, Propagate>;
> +  using Vector = std::vector<int, PropAlloc>;
> +  using ScopedAlloc = std::scoped_allocator_adaptor<
> +    propagating_allocator<Vector, Propagate, tracker_allocator<Vector>>,
> +    PropAlloc>;
> +  using Hive = std::hive<Vector, ScopedAlloc>;
> +
> +  const std::hive_limits dl(30, 50);
> +  const Vector vc{11, 12, 13};
> +  const Hive empty(std::hive_limits(10, 20), ScopedAlloc{11, 22});
> +
> +  Hive s0(dl, ScopedAlloc{11, 22});
> +  Counter::reset();
> +
> +  s0 = empty;
> +  VERIFY( s0.empty() );
> +  VERIFY( limits_eq(s0, dl) );
> +  VERIFY( s0.get_allocator().get_personality() == 11 );
> +  VERIFY( Counter::get_allocation_count() == 0 );
> +  VERIFY( Counter::get_deallocation_count() == 0 );
> +  VERIFY( Counter::get_construct_count() == 0 );
> +  VERIFY( Counter::get_destruct_count() == 0 );
> +
> +  Hive s3(3, vc, dl, ScopedAlloc{11, 22});
> +  Counter::reset();
> +
> +  s3 = empty;
> +  VERIFY( s3.empty() );
> +  VERIFY( limits_eq(s3, dl) );
> +  VERIFY( s3.get_allocator().get_personality() == 11 );
> +  VERIFY( Counter::get_allocation_count() == 0 );
> +  VERIFY( Counter::get_deallocation_count() == 0 );
> +  VERIFY( Counter::get_construct_count() == 0 );
> +  VERIFY( Counter::get_destruct_count() == 3 );
> +
> +  Hive d0(dl, ScopedAlloc{33, 44});
> +  Counter::reset();
> +
> +  d0 = empty;
> +  VERIFY( d0.empty() );
> +  VERIFY( limits_eq(d0, dl) );
> +  if (Propagate)
> +    VERIFY( d0.get_allocator().get_personality() == 11 );
> +  else
> +    VERIFY( d0.get_allocator().get_personality() == 33 );
> +  VERIFY( Counter::get_allocation_count() == 0 );
> +  VERIFY( Counter::get_deallocation_count() == 0 );
> +  VERIFY( Counter::get_construct_count() == 0 );
> +  VERIFY( Counter::get_destruct_count() == 0 );
> +
> +  Hive d3(3, vc, dl, ScopedAlloc{33, 44});
> +  Counter::reset();
> +
> +  d3 = empty;
> +  VERIFY( d3.empty() );
> +  VERIFY( limits_eq(d3, dl) );
> +  if (Propagate)
> +  {
> +    VERIFY( d3.get_allocator().get_personality() == 11 );
> +    VERIFY( Counter::get_allocation_count() == 0 );
> +    VERIFY( Counter::get_deallocation_count() >= 2 * sizeof(Vector) );
> +  }
> +  else
> +  {
> +    VERIFY( d3.get_allocator().get_personality() == 33 );
> +    VERIFY( Counter::get_allocation_count() == 0 );
> +    VERIFY( Counter::get_deallocation_count() == 0 );
> +  }
> +  VERIFY( Counter::get_construct_count() == 0 );
> +  VERIFY( Counter::get_destruct_count() == 3 );
> +}
> +
> +template<bool Propagate>
> +void
> +test_all()
> +{
> +  test_ctor<Propagate>();
> +  test_assign<Propagate>();
> +  test_empty<Propagate>();
> +}
> +
> +int main()
> +{
> +  test_all<true>();
> +  test_all<false>();
> +}
> diff --git a/libstdc++-v3/testsuite/23_containers/hive/ctor.cc
> b/libstdc++-v3/testsuite/23_containers/hive/ctor.cc
> new file mode 100644
> index 00000000000..1f53db5837e
> --- /dev/null
> +++ b/libstdc++-v3/testsuite/23_containers/hive/ctor.cc
> @@ -0,0 +1,238 @@
> +// { dg-do run { target c++26 } }
> +
> +#include <hive>
> +
> +#include <algorithm>
> +#include <memory>
> +#include <scoped_allocator>
> +#include <testsuite_hooks.h>
> +#include <testsuite_allocator.h>
> +
> +struct NonMovable
> +{
> +  NonMovable() = default;
> +  NonMovable(int p) : x(p) { }
> +
> +  NonMovable(NonMovable&&) = delete;
> +
> +  int x;
> +
> +  friend constexpr bool
> +  operator==(const NonMovable& nm, int y)
> +  { return nm.x == y; }
> +};
> +
> +struct MoveOnly
> +{
> +  MoveOnly() = default;
> +  MoveOnly(int p) : x(p) { }
> +
> +  MoveOnly(MoveOnly&&) = default;
> +  MoveOnly& operator=(MoveOnly&&) = default;
> +
> +  int x;
> +
> +  friend constexpr bool
> +  operator==(const MoveOnly& nm, int y)
> +  { return nm.x == y; }
> +};
> +
> +constexpr bool
> +limits_eq(std::hive_limits lhs, std::hive_limits rhs)
> +{ return lhs.min == rhs.min && lhs.max == rhs.max; }
> +
> +template<typename Hive>
> +constexpr bool
> +limits_eq(const Hive& hive, std::hive_limits rhs)
> +{ return limits_eq(hive.block_capacity_limits(), rhs); }
> +
> +template<typename Hive>
> +constexpr bool
> +limits_default(const Hive& hive)
> +{ return limits_eq(hive, Hive::block_capacity_default_limits()); }
> +
> +template<typename T, typename Check, typename... Args>
> +void
> +verify_alloc(Check&& check, const Args&... args)
> +{
> +  using __gnu_test::default_init_allocator;
> +  using Hive = std::hive<int, default_init_allocator<int>>;
> +  default_init_allocator<T> a{};
> +  a.state = 5;
> +
> +  auto h1 = Hive(args...);
> +  VERIFY( h1.get_allocator().state == 0 );
> +  VERIFY( limits_default(h1) );
> +  VERIFY( check(h1, args...) );
> +
> +  auto h2 = Hive(args..., a);
> +  VERIFY( h2.get_allocator().state == 5 );
> +  VERIFY( limits_default(h1) );
> +  VERIFY( check(h2, args...) );
> +
> +  std::hive_limits hl(5, 50);
> +  auto h3 = Hive(args..., hl);
> +  VERIFY( h3.get_allocator().state == 0 );
> +  VERIFY( limits_eq(h3, hl) );
> +  VERIFY( check(h3, args...) );
> +
> +  auto h4 = Hive(args..., hl, a);
> +  VERIFY( h4.get_allocator().state == 5 );
> +  VERIFY( limits_eq(h4, hl) );
> +  VERIFY( check(h4, args...) );
> +}
> +
> +void
> +test_empty()
> +{
> +  std::hive<int> h;
> +  VERIFY( h.empty() );
> +  verify_alloc<int>([](const auto& hive) {
> +    return hive.empty();
> +  });
> +}
> +
> +constinit std::hive<int> gh1;
> +constinit std::hive<int> gh2(std::hive_limits(5, 50));
> +
> +void
> +test_copy()
> +{
> +  std::hive_limits hl(5, 50);
> +  std::initializer_list<int> il{1, 2, 3, 4, 5};
> +
> +  const std::hive<int> s1(il);
> +  const std::hive<int> s2(il, hl);
> +
> +  std::hive<int> h1(s1);
> +  VERIFY( std::ranges::equal(h1, il) );
> +  VERIFY( limits_default(h1) );
> +
> +  std::hive<int> h2(s2);
> +  VERIFY( std::ranges::equal(h2, il) );
> +  VERIFY( limits_eq(h2, hl) );
> +
> +  using __gnu_test::default_init_allocator;
> +  using Hive = std::hive<int, default_init_allocator<int>>;
> +  default_init_allocator<int> a{};
> +  a.state = 5;
> +
> +  const Hive sd1(il);
> +  const Hive sd2(il, hl);
> +
> +  auto d1 = Hive(sd1);
> +  VERIFY( d1.get_allocator().state == 0 );
> +  VERIFY( limits_default(d1) );
> +  VERIFY( std::ranges::equal(d1, il) );
> +
> +  auto d2 = Hive(sd1, a);
> +  VERIFY( d2.get_allocator().state == 5 );
> +  VERIFY( limits_default(d1) );
> +  VERIFY( std::ranges::equal(d2, il) );
> +
> +  auto d3 = Hive(sd2);
> +  VERIFY( d3.get_allocator().state == 0 );
> +  VERIFY( limits_eq(d3, hl) );
> +  VERIFY( std::ranges::equal(d3, il) );
> +
> +  auto d4 = Hive(sd2, a);
> +  VERIFY( d4.get_allocator().state == 5 );
> +  VERIFY( limits_eq(d4, hl) );
> +  VERIFY( std::ranges::equal(d4, il) );
> +}
> +
> +void
> +test_move()
> +{
> +  std::hive_limits hl(5, 50);
> +  std::initializer_list<int> il{1, 2, 3, 4, 5};
> +
> +  std::hive<MoveOnly> s1(std::from_range, il);
> +  std::hive<MoveOnly> s2(std::from_range, il, hl);
> +
> +  std::hive<MoveOnly> h1(std::move(s1));
> +  VERIFY( std::ranges::equal(h1, il, std::equal_to{}) );
> +  VERIFY( limits_default(h1) );
> +
> +  std::hive<MoveOnly> h2(std::move(s2));
> +  VERIFY( std::ranges::equal(h2, il, std::equal_to{}) );
> +  VERIFY( limits_eq(h2, hl) );
> +
> +  using __gnu_test::default_init_allocator;
> +  using Hive = std::hive<MoveOnly, default_init_allocator<MoveOnly>>;
> +  default_init_allocator<MoveOnly> a{};
> +  a.state = 5;
> +
> +  Hive sd1a(std::from_range, il);
> +  Hive sd1b(std::from_range, il);
> +  Hive sd2a(std::from_range, il, hl);
> +  Hive sd2b(std::from_range, il, hl);
> +
> +  auto d1 = Hive(std::move(sd1a));
> +  VERIFY( d1.get_allocator().state == 0 );
> +  VERIFY( limits_default(d1) );
> +  VERIFY( std::ranges::equal(d1, il, std::equal_to{}) );
> +
> +  auto d2 = Hive(std::move(sd1b), a);
> +  VERIFY( d2.get_allocator().state == 5 );
> +  VERIFY( limits_default(d1) );
> +  VERIFY( std::ranges::equal(d2, il, std::equal_to{}) );
> +
> +  auto d3 = Hive(std::move(sd2a));
> +  VERIFY( d3.get_allocator().state == 0 );
> +  VERIFY( limits_eq(d3, hl) );
> +  VERIFY( std::ranges::equal(d3, il, std::equal_to{}) );
> +
> +  auto d4 = Hive(std::move(sd2b), a);
> +  VERIFY( d4.get_allocator().state == 5 );
> +  VERIFY( limits_eq(d4, hl) );
> +  VERIFY( std::ranges::equal(d4, il, std::equal_to{}) );
> +}
> +
> +void
> +test_n()
> +{
> +  auto check = [](const auto& hive, size_t n, auto... vs)
> +  {
> +    int v = (0, ..., vs);
> +    return hive.size() == n
> +     && std::ranges::all_of(hive, [v](const auto& e) { return e == v; });
> +  };
> +
> +  std::hive<NonMovable> h1(10);
> +  VERIFY( check(h1, 10) );
> +  verify_alloc<NonMovable>(check, 15);
> +
> +  std::hive<int> h2(20, 7);
> +  VERIFY( check(h2, 20, 7) );
> +  verify_alloc<int>(check, 20, 13);
> +}
> +
> +void
> +test_range()
> +{
> +  std::initializer_list<int> il{1, 2, 3, 4, 5, 6, 7, 8};
> +  auto check = [il](const auto& hive, const auto&... args)
> +  { return std::ranges::equal(hive, il); };
> +
> +  std::hive<int> h1(il);
> +  VERIFY( check(h1) );
> +  verify_alloc<int>(check, il);
> +
> +  std::hive<int> h2(il.begin(), il.end());
> +  VERIFY( check(h2) );
> +  verify_alloc<int>(check, il.begin(), il.end());
> +
> +  std::hive<int> h3(std::from_range, il);
> +  VERIFY( check(h3) );
> +  verify_alloc<int>(check, std::from_range, il);
> +}
> +
> +int main()
> +{
> +  test_empty();
> +  test_copy();
> +  test_move();
> +  test_n();
> +  test_range();
> +}
> diff --git a/libstdc++-v3/testsuite/23_containers/hive/erasure.cc
> b/libstdc++-v3/testsuite/23_containers/hive/erasure.cc
> new file mode 100644
> index 00000000000..f410592bc5a
> --- /dev/null
> +++ b/libstdc++-v3/testsuite/23_containers/hive/erasure.cc
> @@ -0,0 +1,291 @@
> +// { dg-do run { target c++26 } }
> +
> +#include <hive>
> +
> +#include <algorithm>
> +#include <ranges>
> +#include <testsuite_hooks.h>
> +
> +struct Tracker
> +{
> +  static inline size_t copy = 0;
> +  static inline size_t assign = 0;
> +  static inline size_t create = 0;
> +  static inline size_t destroy = 0;
> +
> +  static void resetCounters()
> +  { create = copy = assign = destroy = 0; }
> +
> +  Tracker()
> +  : Tracker(0)
> +  {}
> +
> +  Tracker(int p)
> +  : x(p)
> +  { ++create; }
> +
> +  ~Tracker()
> +  { ++destroy; }
> +
> +  Tracker(const Tracker& other)
> +  : x(other.x)
> +  { ++copy; }
> +
> +  Tracker& operator=(const Tracker& other)
> +  { ++assign; this->x = other.x; return *this; }
> +
> +  int x;
> +
> +  friend constexpr bool
> +  operator==(const Tracker&, const Tracker&) = default;
> +
> +  friend constexpr bool
> +  operator==(const Tracker& nm, int y)
> +  { return nm.x == y; }
> +};
> +
> +bool eq(const std::hive<Tracker>& h, std::initializer_list<int> il)
> +{
> +  if (!std::ranges::equal(h, il, std::equal_to{}, &Tracker::x))
> +    return false;
> +  return std::ranges::equal(std::rbegin(h), std::rend(h),
> +                           std::rbegin(il), std::rend(il),
> +                           std::equal_to{}, &Tracker::x);
> +}
> +
> +void
> +test_erase(std::hive_limits hl)
> +{
> +  std::initializer_list<Tracker> il
> +  {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16};
> +
> +  std::hive<Tracker> h(il, hl);
> +  size_t cap = h.capacity();
> +  Tracker::resetCounters();
> +
> +  h.clear();
> +  VERIFY( h.empty() );
> +  VERIFY( Tracker::destroy == 16 );
> +
> +  h = il;
> +  Tracker::resetCounters();
> +  auto it = h.erase(h.begin(), h.end());
> +  VERIFY( it == h.end() );
> +  VERIFY( h.empty() );
> +  VERIFY( h.capacity() == cap );
> +  VERIFY( Tracker::destroy == 16 );
> +
> +  h = il;
> +  Tracker::resetCounters();
> +  it = h.erase(std::next(h.begin(), 5), std::next(h.begin(), 10));
> +  VERIFY( eq(h, {1,2,3,4,5,11,12,13,14,15,16}) );
> +  VERIFY( it->x == 11 );
> +  VERIFY( Tracker::destroy == 5 );
> +
> +  it = h.erase(h.begin(), std::next(h.begin(), 5));
> +  VERIFY( eq(h, {11,12,13,14,15,16}) );
> +  VERIFY( it->x == 11 );
> +  VERIFY( h.capacity() == cap );
> +  VERIFY( Tracker::destroy == 10 );
> +
> +  it = h.erase(h.begin(), std::next(h.begin(), 5));
> +  VERIFY( eq(h, {16}) );
> +  VERIFY( it->x == 16 );
> +  VERIFY( h.capacity() == cap );
> +  VERIFY( Tracker::destroy == 15 );
> +
> +  it = h.erase(h.begin());
> +  VERIFY( it == h.end() );
> +  VERIFY( h.empty() );
> +  VERIFY( h.capacity() == cap );
> +  VERIFY( Tracker::destroy == 16 );
> +
> +  h = il;
> +  Tracker::resetCounters();
> +  for (auto it = h.begin(); it != h.end();)
> +    it = h.erase(++it);
> +  VERIFY( eq(h, {1,3,5,7,9,11,13,15}) );
> +  VERIFY( h.capacity() == cap );
> +  VERIFY( Tracker::destroy == 8 );
> +
> +  auto erase_step = [&](size_t step)
> +  {
> +    for (auto it = h.begin(); it != h.end(); std::ranges::advance(it,
> step, h.end()))
> +      {
> +       auto n = it;
> +       std::ranges::advance(n, step, h.end());
> +       it = h.erase(it, n);
> +      }
> +  };
> +
> +  erase_step(2);
> +  VERIFY( eq(h, {5,7,13,15}) );
> +  VERIFY( h.capacity() == cap );
> +  VERIFY( Tracker::destroy == 12 );
> +
> +  erase_step(2);
> +  VERIFY( eq(h, {13,15}) );
> +  VERIFY( h.capacity() == cap );
> +  VERIFY( Tracker::destroy == 14 );
> +
> +  erase_step(2);
> +  VERIFY( h.empty() );
> +  VERIFY( h.capacity() == cap );
> +  VERIFY( Tracker::destroy == 16 );
> +
> +  h = il;
> +  Tracker::resetCounters();
> +
> +  it = h.erase(h.begin());
> +  VERIFY( it->x == 2 );
> +  VERIFY( eq(h, {2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}) );
> +  VERIFY( h.capacity() == cap );
> +  VERIFY( Tracker::destroy == 1 );
> +
> +  erase_step(2);
> +  VERIFY( eq(h, {4,5,8,9,12,13,16}) );
> +  VERIFY( h.capacity() == cap );
> +  VERIFY( Tracker::destroy == 9 );
> +
> +  erase_step(3);
> +  VERIFY( eq(h, {9,12,13}) );
> +  VERIFY( h.capacity() == cap );
> +  VERIFY( Tracker::destroy == 13 );
> +
> +  erase_step(1);
> +  VERIFY( eq(h, {12}) );
> +  VERIFY( h.capacity() == cap );
> +  VERIFY( Tracker::destroy == 15 );
> +
> +  h.clear();
> +  h.trim_capacity();
> +  VERIFY( h.empty() );
> +  VERIFY( h.capacity() == 0 );
> +  VERIFY( Tracker::destroy == 16 );
> +
> +  std::hive<Tracker> h2(500, -1, hl);
> +  std::ranges::copy(std::views::iota(1, 5), h2.begin());
> +  std::ranges::copy(std::views::iota(5, 10), std::prev(h2.end(), 5));
> +  cap = h2.capacity();
> +  Tracker::resetCounters();
> +
> +  it = h2.erase(std::next(h2.begin(), 4), std::prev(h2.end(), 5));
> +  VERIFY( it->x == 5 );
> +  VERIFY( eq(h2, {1,2,3,4,5,6,7,8,9}) );
> +  VERIFY( h2.capacity() == cap );
> +  VERIFY( Tracker::destroy == 491 );
> +}
> +
> +void
> +test_unique(std::hive_limits hl)
> +{
> +  std::initializer_list<Tracker> il
> +  {1,1,2,2,2,3,4,5,5,7,7,8,8,8,8,8,10,12,11,11,15,15};
> +
> +  std::hive<Tracker> h(il, hl);
> +  const size_t cap = h.capacity();
> +  Tracker::resetCounters();
> +
> +  auto rem = h.unique();
> +  VERIFY( rem == 11 );
> +  VERIFY( eq(h, {1,2,3,4,5,7,8,10,12,11,15}) );
> +  VERIFY( h.capacity() == cap );
> +  VERIFY( Tracker::destroy == 11 );
> +
> +  rem = h.unique([](const Tracker& lhs, const Tracker& rhs)
> +  { return (lhs.x % 2) == (rhs.x %2); });
> +  VERIFY( rem == 4 );
> +  VERIFY( eq(h, {1,2,3,4,5,8,11}) );
> +  VERIFY( h.capacity() == cap );
> +  VERIFY( Tracker::destroy == 15 );
> +
> +  rem = h.unique([](const Tracker& lhs, const Tracker& rhs)
> +  { return std::abs(lhs.x - rhs.x) <= 2; });
> +  VERIFY( rem == 3 );
> +  VERIFY( eq(h, {1,4,8,11}) );
> +  VERIFY( h.capacity() == cap );
> +  VERIFY( Tracker::destroy == 18 );
> +
> +  rem = h.unique([](const Tracker& lhs, const Tracker& rhs)
> +  { return true; });
> +  VERIFY( rem == 3 );
> +  VERIFY( eq(h, {1}) );
> +  VERIFY( h.capacity() == cap );
> +  VERIFY( Tracker::destroy == 21 );
> +}
> +
> +void
> +test_erase_if(std::hive_limits hl)
> +{
> +  std::initializer_list<Tracker> il
> +  {0, 1, 2, 3, 11, 12, 13, 14, 4, 15,
> +   5, 5, 5, 6, 17, 17, 7, 18, 8, 9, 19, 10, 20};
> +
> +  std::hive<Tracker> h(il, hl);
> +  size_t cap = h.capacity();
> +  Tracker::resetCounters();
> +
> +  auto rem = std::erase_if(h, [](const Tracker& t) { return t.x > 10; });
> +  VERIFY( rem == 10 );
> +  VERIFY( eq(h, {0,1,2,3,4,5,5,5,6,7,8,9,10}) );
> +  VERIFY( h.capacity() == cap );
> +  VERIFY( Tracker::destroy == 10 );
> +
> +  rem = std::erase(h, 5);
> +  VERIFY( rem == 3 );
> +  VERIFY( eq(h, {0,1,2,3,4,6,7,8,9,10}) );
> +  VERIFY( h.capacity() == cap );
> +  VERIFY( Tracker::destroy == 13 );
> +
> +  rem = std::erase_if(h, [](const Tracker& t) { return t.x % 2; });
> +  VERIFY( rem == 4 );
> +  VERIFY( eq(h, {0,2,4,6,8,10}) );
> +  VERIFY( h.capacity() == cap );
> +  VERIFY( Tracker::destroy == 17 );
> +
> +  rem = std::erase(h, 0);
> +  VERIFY( rem == 1 );
> +  VERIFY( eq(h, {2,4,6,8,10}) );
> +  VERIFY( h.capacity() == cap );
> +  VERIFY( Tracker::destroy == 18 );
> +
> +  rem = std::erase(h, 10);
> +  VERIFY( rem == 1 );
> +  VERIFY( eq(h, {2,4,6,8}) );
> +  VERIFY( h.capacity() == cap );
> +  VERIFY( Tracker::destroy == 19 );
> +
> +  rem = std::erase_if(h, [](const Tracker& t) { return true; });
> +  VERIFY( rem == 4 );
> +  VERIFY( h.empty() );
> +  VERIFY( h.capacity() == cap );
> +  VERIFY( Tracker::destroy == 23 );
> +
> +  std::hive<Tracker> h2(500, -1, hl);
> +  std::ranges::copy(std::views::iota(1, 10),
> +                   (h2 | std::views::stride(50)).begin());
> +  cap = h2.capacity();
> +  Tracker::resetCounters();
> +
> +  rem = std::erase_if(h2, [](const Tracker& t) { return t.x < 0; });
> +  VERIFY( rem == 491 );
> +  VERIFY( eq(h2, {1,2,3,4,5,6,7,8,9}) );
> +  VERIFY( h2.capacity() == cap );
> +  VERIFY( Tracker::destroy == 491 );
> +}
> +
> +void test_limits(std::hive_limits hl)
> +{
> +  test_erase(hl);
> +  test_unique(hl);
> +  test_erase_if(hl);
> +}
> +
> +int main()
> +{
> +  test_limits(std::hive<Tracker>::block_capacity_default_limits());
> +  test_limits(std::hive_limits(20, 50));
> +  test_limits(std::hive_limits(5, 10));
> +  test_limits(std::hive_limits(10, 10));
> +  test_limits(std::hive_limits(2, 4));
> +}
> diff --git a/libstdc++-v3/testsuite/23_containers/hive/insert.cc
> b/libstdc++-v3/testsuite/23_containers/hive/insert.cc
> new file mode 100644
> index 00000000000..112131ff26c
> --- /dev/null
> +++ b/libstdc++-v3/testsuite/23_containers/hive/insert.cc
> @@ -0,0 +1,93 @@
> +// { dg-do run { target c++26 } }
> +
> +#include <hive>
> +
> +#include <algorithm>
> +#include <flat_set>
> +#include <testsuite_hooks.h>
> +
> +void test_inserts(std::hive<int>& hive)
> +{
> +  std::flat_set<int> expected(std::from_range, hive);
> +
> +  auto it = hive.emplace(1);
> +  VERIFY( *it == 1 );
> +  expected.insert(1);
> +  VERIFY( std::flat_set<int>(std::from_range, hive) == expected );
> +
> +  std::vector<int> v{11, 12, 13, 14, 15};
> +  hive.insert(v.begin(), v.end());
> +  expected.insert(v.begin(), v.end());
> +  VERIFY( std::flat_set<int>(std::from_range, hive) == expected );
> +
> +  v = {16, 17, 18};
> +  hive.insert_range(v);
> +  expected.insert(v.begin(), v.end());
> +  VERIFY( std::flat_set<int>(std::from_range, hive) == expected );
> +
> +  it = hive.insert(2);
> +  VERIFY( *it == 2 );
> +  expected.insert(2);
> +
> +  it = hive.insert(hive.end(), 3);
> +  VERIFY( *it == 3 );
> +  expected.insert(3);
> +
> +  it = hive.emplace_hint(hive.end(), 4);
> +  VERIFY( *it == 4 );
> +  expected.insert(4);
> +
> +  VERIFY( std::flat_set<int>(std::from_range, hive) == expected );
> +
> +  hive.insert(10, 20);
> +  expected.insert(20);
> +  VERIFY( std::ranges::count(hive, 20) == 10 );
> +  VERIFY( std::flat_set<int>(std::from_range, hive) == expected );
> +
> +  std::initializer_list<int> il{11, 12, 13, 14};
> +  hive.insert(il);
> +  expected.insert(il.begin(), il.end());
> +  VERIFY( std::flat_set<int>(std::from_range, hive) == expected );
> +}
> +
> +void test_limits(std::hive_limits hl =
> std::hive<int>::block_capacity_default_limits())
> +{
> +  std::hive<int> h0(hl);
> +  test_inserts(h0);
> +
> +  std::hive<int> h1(hl);
> +  h1.reserve(4);
> +  h1.reserve(3);
> +  test_inserts(h1);
> +
> +  std::hive<int> h2({-1, -2, -3, -4, -5}, hl);
> +  test_inserts(h2);
> +
> +  std::hive<int> h3(100, -1, hl);
> +  for (auto it = h3.begin(); it != h3.end(); )
> +    it = h3.erase(++it);
> +  test_inserts(h3);
> +
> +  std::hive<int> h4(80, -2, hl);
> +  for (auto it = h4.begin(); it != h4.end(); std::advance(it, 10))
> +    it = h4.erase(it, std::next(it, 10));
> +  test_inserts(h4);
> +
> +  std::hive<int> h5(50, -3, hl);
> +  h5.erase(std::next(h5.begin(), 42), std::next(h5.begin(), 48));
> +  h5.erase(std::next(h5.begin(), 33), std::next(h5.begin(), 35));
> +  h5.erase(std::next(h5.begin(), 36), std::next(h5.begin(), 38));
> +  h5.erase(std::next(h5.begin(), 24), std::next(h5.begin(), 28));
> +  h5.erase(std::next(h5.begin(), 12), std::next(h5.begin(), 19));
> +  h5.erase(std::next(h5.begin()), std::next(h5.begin(), 5));
> +  test_inserts(h5);
> +}
> +
> +int main()
> +{
> +  test_limits();
> +  test_limits(std::hive_limits(20, 50));
> +  test_limits(std::hive_limits(5, 10));
> +  test_limits(std::hive_limits(10, 10));
> +  test_limits(std::hive_limits(2, 4));
> +}
> diff --git a/libstdc++-v3/testsuite/23_containers/hive/move_alloc.cc
> b/libstdc++-v3/testsuite/23_containers/hive/move_alloc.cc
> new file mode 100644
> index 00000000000..8bea84df2a2
> --- /dev/null
> +++ b/libstdc++-v3/testsuite/23_containers/hive/move_alloc.cc
> @@ -0,0 +1,444 @@
> +// { dg-do run { target c++26 } }
> +
> +#include <hive>
> +
> +#include <memory>
> +#include <optional>
> +#include <scoped_allocator>
> +#include <utility>
> +#include <vector>
> +#include <testsuite_hooks.h>
> +#include <testsuite_allocator.h>
> +
> +using __gnu_test::propagating_allocator;
> +using __gnu_test::tracker_allocator;
> +using Counter = __gnu_test::tracker_allocator_counter;
> +
> +constexpr bool
> +limits_eq(std::hive_limits lhs, std::hive_limits rhs)
> +{ return lhs.min == rhs.min && lhs.max == rhs.max; }
> +
> +template<typename Hive>
> +constexpr bool
> +limits_eq(const Hive& hive, std::hive_limits rhs)
> +{ return limits_eq(hive.block_capacity_limits(), rhs); }
> +
> +template<typename Hive>
> +int
> +elem_alloc_personality(const Hive& hive)
> +{
> +  int front = hive.begin()->get_allocator().get_personality();
> +  int back = std::prev(hive.end())->get_allocator().get_personality();
> +  VERIFY( front == back );
> +  return front;
> +}
> +
> +template<bool Propagate>
> +void
> +test_ctor()
> +{
> +  using PropAlloc = propagating_allocator<int, Propagate>;
> +  using Vector = std::vector<int, PropAlloc>;
> +  using ScopedAlloc = std::scoped_allocator_adaptor<
> +    propagating_allocator<Vector, Propagate, tracker_allocator<Vector>>,
> +    PropAlloc>;
> +  using Hive = std::hive<Vector, ScopedAlloc>;
> +
> +  const std::hive_limits sl(10, 20);
> +  const std::initializer_list<Vector> il = {Vector{1, 2, 3}, Vector{4, 5,
> 6}};
> +  std::optional<Hive> opt;
> +  auto make = [&] -> Hive&&
> +  {
> +    opt.emplace(il, sl, ScopedAlloc{11, 22});
> +    Counter::reset();
> +    return std::move(*opt);
> +  };
> +
> +  Hive s1(make());
> +  VERIFY( std::ranges::equal(s1, il) );
> +  VERIFY( opt->empty() );
> +  VERIFY( limits_eq(s1, sl) );
> +  VERIFY( s1.get_allocator().get_personality() == 11 );
> +  VERIFY( elem_alloc_personality(s1) == 22 );
> +  VERIFY( Counter::get_allocation_count() == 0 );
> +  VERIFY( Counter::get_deallocation_count() == 0 );
> +  VERIFY( Counter::get_construct_count() == 0 );
> +  VERIFY( Counter::get_destruct_count() == 0 );
> +
> +  Hive d1(make(), ScopedAlloc{33, 44});
> +  VERIFY( std::ranges::equal(d1, il) );
> +  VERIFY( opt->empty() );
> +  VERIFY( limits_eq(d1, sl) );
> +  VERIFY( d1.get_allocator().get_personality() == 33 );
> +  VERIFY( elem_alloc_personality(d1) == 44 );
> +  VERIFY( Counter::get_allocation_count() >= 2 * sizeof(Vector) );
> +  VERIFY( Counter::get_deallocation_count() == 0 );
> +  VERIFY( Counter::get_construct_count() == 2 );
> +  VERIFY( Counter::get_destruct_count() == 2 );
> +}
> +
> +template<bool Propagate>
> +void
> +test_assign()
> +{
> +  using PropAlloc = propagating_allocator<int, Propagate>;
> +  using Vector = std::vector<int, PropAlloc>;
> +  using ScopedAlloc = std::scoped_allocator_adaptor<
> +    propagating_allocator<Vector, Propagate, tracker_allocator<Vector>>,
> +    PropAlloc>;
> +  using Hive = std::hive<Vector, ScopedAlloc>;
> +
> +  const std::hive_limits sl(10, 20);
> +  const std::hive_limits dl(30, 50);
> +  const Vector vc{11, 12, 13};
> +  const std::initializer_list<Vector> il = {Vector{1, 2, 3}, Vector{4, 5,
> 6}};
> +  std::optional<Hive> opt;
> +  auto make = [&] -> Hive&&
> +  {
> +    opt.emplace(il, sl, ScopedAlloc{11, 22});
> +    Counter::reset();
> +    return std::move(*opt);
> +  };
> +
> +  Hive s0(dl, ScopedAlloc{11, 22});
> +
> +  s0 = make();
> +  VERIFY( std::ranges::equal(s0, il) );
> +  VERIFY( opt->empty() );
> +  VERIFY( limits_eq(s0, sl) );
> +  VERIFY( s0.get_allocator().get_personality() == 11 );
> +  VERIFY( elem_alloc_personality(s0) == 22 );
> +  VERIFY( Counter::get_allocation_count() == 0 );
> +  VERIFY( Counter::get_construct_count() == 0 );
> +  VERIFY( Counter::get_deallocation_count() == 0 );
> +  VERIFY( Counter::get_destruct_count() == 0 );
> +
> +  Hive s1(1, vc, dl, ScopedAlloc{11, 22});
> +
> +  s1 = make();
> +  VERIFY( std::ranges::equal(s1, il) );
> +  VERIFY( opt->empty() );
> +  VERIFY( limits_eq(s1, sl) );
> +  VERIFY( s1.get_allocator().get_personality() == 11 );
> +  VERIFY( elem_alloc_personality(s1) == 22 );
> +  VERIFY( Counter::get_allocation_count() == 0 );
> +  VERIFY( Counter::get_construct_count() == 0 );
> +  VERIFY( Counter::get_deallocation_count() == 0 );
> +  VERIFY( Counter::get_destruct_count() == 1 );
> +
> +  Hive s2(2, vc, dl, ScopedAlloc{11, 22});
> +
> +  s2 = make();
> +  VERIFY( std::ranges::equal(s2, il) );
> +  VERIFY( opt->empty() );
> +  VERIFY( limits_eq(s2, sl) );
> +  VERIFY( s2.get_allocator().get_personality() == 11 );
> +  VERIFY( elem_alloc_personality(s2) == 22 );
> +  VERIFY( Counter::get_allocation_count() == 0 );
> +  VERIFY( Counter::get_construct_count() == 0 );
> +  VERIFY( Counter::get_deallocation_count() == 0 );
> +  VERIFY( Counter::get_destruct_count() == 2 );
> +
> +  Hive s3(3, vc, dl, ScopedAlloc{11, 22});
> +
> +  s3 = make();
> +  VERIFY( std::ranges::equal(s2, il) );
> +  VERIFY( opt->empty() );
> +  VERIFY( limits_eq(s3, sl) );
> +  VERIFY( s3.get_allocator().get_personality() == 11 );
> +  VERIFY( elem_alloc_personality(s3) == 22 );
> +  VERIFY( Counter::get_allocation_count() == 0 );
> +  VERIFY( Counter::get_construct_count() == 0 );
> +  VERIFY( Counter::get_deallocation_count() == 0 );
> +  VERIFY( Counter::get_destruct_count() == 3 );
> +
> +  Hive d0(dl, ScopedAlloc{33, 44});
> +
> +  d0 = make();
> +  VERIFY( std::ranges::equal(d0, il) );
> +  VERIFY( opt->empty() );
> +  if (Propagate)
> +  {
> +    VERIFY( d0.get_allocator().get_personality() == 11 );
> +    VERIFY( elem_alloc_personality(d0) == 22 );
> +    VERIFY( limits_eq(d0, sl) );
> +    VERIFY( Counter::get_allocation_count() == 0 );
> +    VERIFY( Counter::get_construct_count() == 0 );
> +    VERIFY( Counter::get_deallocation_count() == 0 );
> +    VERIFY( Counter::get_destruct_count() == 0 );
> +  }
> +  else
> +  {
> +    VERIFY( limits_eq(d0, dl) );
> +    VERIFY( d0.get_allocator().get_personality() == 33 );
> +    VERIFY( elem_alloc_personality(d0) == 44 );
> +    VERIFY( Counter::get_allocation_count() >= 2 * sizeof(Vector) );
> +    VERIFY( Counter::get_construct_count() == 2 );
> +    VERIFY( Counter::get_deallocation_count() == 0 );
> +    VERIFY( Counter::get_destruct_count() == 2 );
> +  }
> +
> +  Hive d1(1, vc, dl, ScopedAlloc{33, 44});
> +
> +  d1 = make();
> +  VERIFY( std::ranges::equal(d1, il) );
> +  VERIFY( opt->empty() );
> +  if (Propagate)
> +  {
> +    VERIFY( limits_eq(d1, sl) );
> +    VERIFY( d1.get_allocator().get_personality() == 11 );
> +    VERIFY( elem_alloc_personality(d1) == 22 );
> +    VERIFY( Counter::get_allocation_count() == 0 );
> +    VERIFY( Counter::get_construct_count() == 0 );
> +    VERIFY( Counter::get_deallocation_count() >= sizeof(Vector) );
> +    VERIFY( Counter::get_destruct_count() == 1 );
> +  }
> +  else
> +  {
> +    VERIFY( limits_eq(d1, dl) );
> +    VERIFY( d1.get_allocator().get_personality() == 33 );
> +    VERIFY( elem_alloc_personality(d1) == 44 );
> +    VERIFY( Counter::get_allocation_count() >= 0 );
> +    VERIFY( Counter::get_construct_count() == 1 );
> +    VERIFY( Counter::get_deallocation_count() == 0 );
> +    VERIFY( Counter::get_destruct_count() == 2 );
> +  }
> +
> +  Hive d2(2, vc, dl, ScopedAlloc{33, 44});
> +
> +  d2 = make();
> +  VERIFY( std::ranges::equal(d2, il) );
> +  VERIFY( opt->empty() );
> +  if (Propagate)
> +  {
> +    VERIFY( d2.get_allocator().get_personality() == 11 );
> +    VERIFY( elem_alloc_personality(d2) == 22 );
> +    VERIFY( Counter::get_allocation_count() == 0 );
> +    VERIFY( Counter::get_construct_count() == 0 );
> +    VERIFY( Counter::get_deallocation_count() >= 2 * sizeof(Vector) );
> +    VERIFY( Counter::get_destruct_count() == 2 );
> +  }
> +  else
> +  {
> +    VERIFY( limits_eq(d2, dl) );
> +    VERIFY( d2.get_allocator().get_personality() == 33 );
> +    VERIFY( elem_alloc_personality(d2) == 44 );
> +    VERIFY( Counter::get_allocation_count() == 0 );
> +    VERIFY( Counter::get_construct_count() == 0 );
> +    VERIFY( Counter::get_deallocation_count() == 0 );
> +    VERIFY( Counter::get_destruct_count() == 2 );
> +  }
> +
> +  Hive d3(3, vc, dl, ScopedAlloc{33, 44});
> +  Counter::reset();
> +
> +  d3 = make();
> +  VERIFY( std::ranges::equal(d3, il) );
> +  VERIFY( opt->empty() );
> +  if (Propagate)
> +  {
> +    VERIFY( limits_eq(d3, sl) );
> +    VERIFY( d3.get_allocator().get_personality() == 11 );
> +    VERIFY( elem_alloc_personality(d3) == 22 );
> +    VERIFY( Counter::get_allocation_count() == 0 );
> +    VERIFY( Counter::get_construct_count() == 0 );
> +    VERIFY( Counter::get_deallocation_count() >= 3 * sizeof(Vector) );
> +    VERIFY( Counter::get_destruct_count() == 3 );
> +  }
> +  else
> +  {
> +    VERIFY( limits_eq(d3, dl) );
> +    VERIFY( d3.get_allocator().get_personality() == 33 );
> +    VERIFY( elem_alloc_personality(d3) == 44 );
> +    VERIFY( Counter::get_allocation_count() == 0 );
> +    VERIFY( Counter::get_construct_count() == 0 );
> +    VERIFY( Counter::get_deallocation_count() == 0 );
> +    VERIFY( Counter::get_destruct_count() == 3 );
> +  }
> +}
> +
> +template<bool Propagate>
> +void
> +test_empty()
> +{
> +  using PropAlloc = propagating_allocator<int, Propagate>;
> +  using Vector = std::vector<int, PropAlloc>;
> +  using ScopedAlloc = std::scoped_allocator_adaptor<
> +    propagating_allocator<Vector, Propagate, tracker_allocator<Vector>>,
> +    PropAlloc>;
> +  using Hive = std::hive<Vector, ScopedAlloc>;
> +
> +  const std::hive_limits sl(10, 20);
> +  const std::hive_limits dl(30, 50);
> +  const Vector vc{11, 12, 13};
> +  std::optional<Hive> opt;
> +  auto make = [&] -> Hive&&
> +  {
> +    opt.emplace(sl, ScopedAlloc{11, 22});
> +    Counter::reset();
> +    return std::move(*opt);
> +  };
> +
> +  Hive s0(dl, ScopedAlloc{11, 22});
> +
> +  s0 = make();
> +  VERIFY( s0.empty() );
> +  VERIFY( opt->empty() );
> +  VERIFY( limits_eq(s0, sl) );
> +  VERIFY( s0.get_allocator().get_personality() == 11 );
> +  VERIFY( Counter::get_allocation_count() == 0 );
> +  VERIFY( Counter::get_deallocation_count() == 0 );
> +  VERIFY( Counter::get_construct_count() == 0 );
> +  VERIFY( Counter::get_destruct_count() == 0 );
> +
> +  Hive s3(3, vc, dl, ScopedAlloc{11, 22});
> +
> +  s3 = make();
> +  VERIFY( s3.empty() );
> +  VERIFY( opt->empty() );
> +  VERIFY( limits_eq(s3, sl) );
> +  VERIFY( s3.get_allocator().get_personality() == 11 );
> +  VERIFY( Counter::get_allocation_count() == 0 );
> +  VERIFY( Counter::get_deallocation_count() == 0 );
> +  VERIFY( Counter::get_construct_count() == 0 );
> +  VERIFY( Counter::get_destruct_count() == 3 );
> +
> +  Hive d0(dl, ScopedAlloc{33, 44});
> +
> +  d0 = make();
> +  VERIFY( d0.empty() );
> +  VERIFY( opt->empty() );
> +  if (Propagate)
> +  {
> +    VERIFY( limits_eq(d0, sl) );
> +    VERIFY( d0.get_allocator().get_personality() == 11 );
> +  }
> +  else
> +  {
> +    VERIFY( limits_eq(d0, dl) );
> +    VERIFY( d0.get_allocator().get_personality() == 33 );
> +  }
> +  VERIFY( Counter::get_allocation_count() == 0 );
> +  VERIFY( Counter::get_deallocation_count() == 0 );
> +  VERIFY( Counter::get_construct_count() == 0 );
> +  VERIFY( Counter::get_destruct_count() == 0 );
> +
> +  Hive d3(3, vc, dl, ScopedAlloc{33, 44});
> +
> +  d3 = make();
> +  VERIFY( d3.empty() );
> +  VERIFY( opt->empty() );
> +  if (Propagate)
> +  {
> +    VERIFY( limits_eq(d3, sl) );
> +    VERIFY( d3.get_allocator().get_personality() == 11 );
> +    VERIFY( Counter::get_allocation_count() == 0 );
> +    VERIFY( Counter::get_deallocation_count() >= 2 * sizeof(Vector) );
> +  }
> +  else
> +  {
> +    VERIFY( limits_eq(d3, dl) );
> +    VERIFY( d3.get_allocator().get_personality() == 33 );
> +    VERIFY( Counter::get_allocation_count() == 0 );
> +    VERIFY( Counter::get_deallocation_count() == 0 );
> +  }
> +  VERIFY( Counter::get_construct_count() == 0 );
> +  VERIFY( Counter::get_destruct_count() == 3 );
> +}
> +
> +template<bool Propagate>
> +void
> +test_swap()
> +{
> +  using PropAlloc = propagating_allocator<int, Propagate>;
> +  using Vector = std::vector<int, PropAlloc>;
> +  using ScopedAlloc = std::scoped_allocator_adaptor<
> +    propagating_allocator<Vector, Propagate, tracker_allocator<Vector>>,
> +    PropAlloc>;
> +  using Hive = std::hive<Vector, ScopedAlloc>;
> +
> +  const std::initializer_list<Vector> il1 = {Vector{1, 2, 3}, Vector{4,
> 5, 6}};
> +  const std::initializer_list<Vector> il2 = {Vector{11, 12, 13}};
> +  const std::hive_limits hl1(10, 20);
> +  const std::hive_limits hl2(30, 50);
> +
> +  Hive h1(il1, hl1, ScopedAlloc{11, 22});
> +  Hive h2(il2, hl2, ScopedAlloc{11, 22});
> +  Hive h3(il2, hl2, ScopedAlloc{33, 44});
> +  Counter::reset();
> +
> +  h1.swap(h2);
> +  VERIFY( std::ranges::equal(h1, il2) );
> +  VERIFY( std::ranges::equal(h2, il1) );
> +  VERIFY( limits_eq(h1, hl2) );
> +  VERIFY( limits_eq(h2, hl1) );
> +  VERIFY( h1.get_allocator().get_personality() == 11 );
> +  VERIFY( elem_alloc_personality(h1) == 22 );
> +  VERIFY( h2.get_allocator().get_personality() == 11 );
> +  VERIFY( elem_alloc_personality(h2) == 22 );
> +  VERIFY( Counter::get_allocation_count() == 0 );
> +  VERIFY( Counter::get_deallocation_count() == 0 );
> +  VERIFY( Counter::get_construct_count() == 0 );
> +  VERIFY( Counter::get_destruct_count() == 0 );
> +
> +  std::swap(h1, h2);
> +  VERIFY( std::ranges::equal(h1, il1) );
> +  VERIFY( std::ranges::equal(h2, il2) );
> +  VERIFY( limits_eq(h1, hl1) );
> +  VERIFY( limits_eq(h2, hl2) );
> +  VERIFY( h1.get_allocator().get_personality() == 11 );
> +  VERIFY( elem_alloc_personality(h1) == 22 );
> +  VERIFY( h2.get_allocator().get_personality() == 11 );
> +  VERIFY( elem_alloc_personality(h2) == 22 );
> +  VERIFY( Counter::get_allocation_count() == 0 );
> +  VERIFY( Counter::get_deallocation_count() == 0 );
> +  VERIFY( Counter::get_construct_count() == 0 );
> +  VERIFY( Counter::get_destruct_count() == 0 );
> +
> +  if constexpr (Propagate)
> +  {
> +    h1.swap(h3);
> +    VERIFY( std::ranges::equal(h1, il2) );
> +    VERIFY( std::ranges::equal(h3, il1) );
> +    VERIFY( limits_eq(h1, hl2) );
> +    VERIFY( limits_eq(h3, hl1) );
> +    VERIFY( h1.get_allocator().get_personality() == 33 );
> +    VERIFY( elem_alloc_personality(h1) == 44 );
> +    VERIFY( h3.get_allocator().get_personality() == 11 );
> +    VERIFY( elem_alloc_personality(h3) == 22 );
> +    VERIFY( Counter::get_allocation_count() == 0 );
> +    VERIFY( Counter::get_deallocation_count() == 0 );
> +    VERIFY( Counter::get_construct_count() == 0 );
> +    VERIFY( Counter::get_destruct_count() == 0 );
> +
> +    std::swap(h1, h3);
> +    VERIFY( std::ranges::equal(h1, il1) );
> +    VERIFY( std::ranges::equal(h3, il2) );
> +    VERIFY( limits_eq(h1, hl1) );
> +    VERIFY( limits_eq(h3, hl2) );
> +    VERIFY( h1.get_allocator().get_personality() == 11 );
> +    VERIFY( elem_alloc_personality(h1) == 22 );
> +    VERIFY( h3.get_allocator().get_personality() == 33 );
> +    VERIFY( elem_alloc_personality(h3) == 44 );
> +    VERIFY( Counter::get_allocation_count() == 0 );
> +    VERIFY( Counter::get_deallocation_count() == 0 );
> +    VERIFY( Counter::get_construct_count() == 0 );
> +    VERIFY( Counter::get_destruct_count() == 0 );
> +  }
> +}
> +
> +template<bool Propagate>
> +void
> +test_all()
> +{
> +  test_ctor<Propagate>();
> +  test_assign<Propagate>();
> +  test_empty<Propagate>();
> +  test_swap<Propagate>();
> +}
> +
> +int main()
> +{
> +  test_all<true>();
> +  test_all<false>();
> +}
> diff --git a/libstdc++-v3/testsuite/23_containers/hive/ranges.cc
> b/libstdc++-v3/testsuite/23_containers/hive/ranges.cc
> new file mode 100644
> index 00000000000..41b6316425b
> --- /dev/null
> +++ b/libstdc++-v3/testsuite/23_containers/hive/ranges.cc
> @@ -0,0 +1,86 @@
> +// { dg-do run { target c++26 } }
> +// { dg-timeout-factor 2 }
> +
> +#include <hive>
> +
> +#include <algorithm>
> +#include <span>
> +#include <testsuite_hooks.h>
> +#include <testsuite_iterators.h>
> +
> +template<typename V, typename Range>
> +void
> +do_test(std::hive_limits hl =
> std::hive<V>::block_capacity_default_limits())
> +{
> +  // The range's value_type.
> +  using T = std::ranges::range_value_t<Range>;
> +  T a[]{1,2,3,4,5,6,7,8,9,10};
> +
> +  auto eq = [](const std::hive<V>& l, std::span<T> r) {
> +    return std::ranges::equal(l, r, std::equal_to<>{});
> +  };
> +
> +  std::hive<V> h(std::from_range, Range(a, a+4), hl);
> +  VERIFY( eq(h, {a, 4}) );
> +
> +  h.insert_range(Range(a+4, a+9));
> +  VERIFY( eq(h, {a, 9}) );
> +
> +  h.assign_range(Range(a, a+10));
> +  VERIFY( eq(h, {a, 10}) );
> +
> +  if constexpr (std::ranges::forward_range<Range>)
> +  {
> +    Range r(a, a+10);
> +    auto it = r.begin();
> +    std::hive<V> h2(it, std::next(it, 3), hl);
> +    VERIFY( eq(h2, {a, 3}) );
> +
> +    h2.insert(std::next(it, 3), std::next(it, 10));
> +    VERIFY( eq(h2, {a, 10}) );
> +
> +    h2.assign(it, std::next(it, 6));
> +    VERIFY( eq(h2, {a, 6}) );
> +  }
> +}
> +
> +template<typename Range>
> +void
> +do_test_l()
> +{
> +  do_test<int, Range>();
> +  do_test<int, Range>(std::hive_limits(2, 3));
> +  do_test<int, Range>(std::hive_limits(4, 8));
> +}
> +
> +int main()
> +{
> +  using namespace __gnu_test;
> +
> +  do_test_l<test_forward_range<int>>();
> +  do_test_l<test_forward_sized_range<int>>();
> +  do_test_l<test_sized_range_sized_sent<int, forward_iterator_wrapper>>();
> +
> +  do_test_l<test_input_range<int>>();
> +  do_test_l<test_input_sized_range<int>>();
> +  do_test_l<test_sized_range_sized_sent<int, input_iterator_wrapper>>();
> +
> +  do_test_l<test_range<int, input_iterator_wrapper_nocopy>>();
> +  do_test_l<test_sized_range<int, input_iterator_wrapper_nocopy>>();
> +  do_test_l<test_sized_range_sized_sent<int,
> input_iterator_wrapper_nocopy>>();
> +
> +  do_test_l<test_forward_range<short>>();
> +  do_test_l<test_input_range<short>>();
> +
> +  // Not lvalue-convertible to int
> +  struct C {
> +    constexpr C(int v) : val(v) { }
> +    constexpr operator int() && { return val; }
> +    constexpr bool operator==(int b) const { return b == val; }
> +    int val;
> +  };
> +  using rvalue_input_range = test_range<C, input_iterator_wrapper_rval>;
> +  do_test<int, rvalue_input_range>();
> +
> +  return true;
> +}
> diff --git a/libstdc++-v3/testsuite/23_containers/hive/splice.cc
> b/libstdc++-v3/testsuite/23_containers/hive/splice.cc
> new file mode 100644
> index 00000000000..43e4a79f5f4
> --- /dev/null
> +++ b/libstdc++-v3/testsuite/23_containers/hive/splice.cc
> @@ -0,0 +1,200 @@
> +// { dg-do run { target c++26 } }
> +
> +#include <hive>
> +
> +#include <algorithm>
> +#include <ranges>
> +#include <flat_set>
> +#include <testsuite_hooks.h>
> +
> +template<typename T>
> +void
> +check_inserts(std::hive<T>& hive)
> +{
> +  std::flat_set<int> expected(std::from_range, hive);
> +
> +  auto it = hive.emplace(1);
> +  VERIFY( *it == 1 );
> +  expected.insert(1);
> +  VERIFY( std::flat_set<int>(std::from_range, hive) == expected );
> +
> +  std::vector<int> v{11, 12, 13, 14, 15};
> +  hive.insert(v.begin(), v.end());
> +  expected.insert(v.begin(), v.end());
> +  VERIFY( std::flat_set<int>(std::from_range, hive) == expected );
> +
> +  v = {16, 17, 18};
> +  hive.insert_range(v);
> +  expected.insert(v.begin(), v.end());
> +  VERIFY( std::flat_set<int>(std::from_range, hive) == expected );
> +
> +  it = hive.insert(2);
> +  VERIFY( *it == 2 );
> +  expected.insert(2);
> +
> +  it = hive.insert(hive.end(), 3);
> +  VERIFY( *it == 3 );
> +  expected.insert(3);
> +
> +  it = hive.emplace_hint(hive.end(), 4);
> +  VERIFY( *it == 4 );
> +  expected.insert(4);
> +  VERIFY( std::flat_set<int>(std::from_range, hive) == expected );
> +}
> +
> +template<typename Cont>
> +std::ranges::subrange<typename Cont::iterator>
> +woend(Cont& cont)
> +{ return {cont.begin(), std::prev(cont.end())}; }
> +
> +template<typename T>
> +void
> +splice(std::hive<T>& dst, std::hive<T>& src, size_t reserved)
> +{
> +  using subhive = std::ranges::subrange<typename std::hive<T>::iterator>;
> +
> +  std::vector<int> din(std::from_range, dst);
> +  subhive dsr(dst.begin(), std::prev(dst.end()));
> +  size_t dcap = dst.capacity();
> +
> +  std::vector<int> sin(std::from_range, src);
> +  subhive ssr(src.begin(), std::prev(src.end()));
> +  size_t scap = src.capacity();
> +
> +  dst.splice(src);
> +  VERIFY( src.empty() );
> +  VERIFY( src.capacity() == reserved );
> +
> +  VERIFY( dst.size() == din.size() + sin.size() );
> +  VERIFY( dst.capacity() == dcap + scap - reserved );
> +  VERIFY( std::ranges::equal(dst, std::views::concat(din, sin)) );
> +
> +  // Verify iterator stabilty
> +  auto sstart = std::next(dst.begin(), din.size());
> +  auto last = std::prev(sstart);
> +  VERIFY( std::ranges::equal(dsr, woend(din)) );
> +  VERIFY( dsr.begin() == dst.begin() );
> +  VERIFY( dsr.end() == std::prev(sstart) );
> +  VERIFY( std::ranges::equal(ssr, woend(sin)) );
> +  VERIFY( ssr.begin() == sstart );
> +  VERIFY( ssr.end() == std::prev(dst.end()) );
> +
> +  // Validate free list by inserting elements
> +  check_inserts(dst);
> +  check_inserts(src);
> +}
> +
> +template<typename T>
> +void
> +swap(std::hive<T>& dst, std::hive<T>& src, size_t)
> +{
> +  using subhive = std::ranges::subrange<typename std::hive<T>::iterator>;
> +
> +  std::vector<int> din(std::from_range, dst);
> +  auto dsr = woend(dst);
> +  size_t dcap = dst.capacity();
> +
> +  std::vector<int> sin(std::from_range, src);
> +  auto ssr = woend(src);
> +  size_t scap = src.capacity();
> +
> +  dst.swap(src);
> +  VERIFY( src.size() == din.size() );
> +  VERIFY( src.capacity() == dcap );
> +  VERIFY( std::ranges::equal(src, din) );
> +
> +  VERIFY( dst.size() == sin.size() );
> +  VERIFY( dst.capacity() == scap );
> +  VERIFY( std::ranges::equal(dst, sin) );
> +
> +  // Verify iterator stabilty
> +  VERIFY( std::ranges::equal(dsr, woend(din)) );
> +  VERIFY( dsr.begin() == src.begin() );
> +  VERIFY( dsr.end() == std::prev(src.end()) );
> +  VERIFY( std::ranges::equal(ssr, woend(sin)) );
> +  VERIFY( ssr.begin() == dst.begin() );
> +  VERIFY( ssr.end() == std::prev(dst.end()) );
> +
> +  dsr.front() = 33;
> +  ssr.front() = 44;
> +  VERIFY( *dst.begin() == 44 );
> +  VERIFY( *src.begin() == 33 );
> +
> +  // Validate free list by inserting elements
> +  check_inserts(dst);
> +  check_inserts(src);
> +}
> +
> +template<typename T>
> +using op_t = void(*)(std::hive<T>&, std::hive<T>&, size_t);
> +
> +void
> +test_limits(op_t<int> op, std::hive_limits hl)
> +{
> +  std::hive<int> d1(std::from_range, std::views::iota(0, 10), hl);
> +  std::hive<int> s1(std::from_range, std::views::iota(10, 20), hl);
> +  op(d1, s1, 0);
> +
> +  std::hive<int> d2(std::from_range, std::views::iota(0, 10), hl);
> +  std::hive<int> s2(std::from_range, std::views::iota(10, 20), hl);
> +  size_t c2 = s2.capacity();
> +  d2.reserve(d2.capacity() + 50);
> +  s2.reserve(s2.capacity() + 30);
> +  op(d2, s2, s2.capacity() - c2);
> +
> +  auto erase_even = [](auto& hive)
> +  {
> +    for (auto it = hive.begin(); it != hive.end(); ++it)
> +      it = hive.erase(it);
> +  };
> +
> +  std::hive<int> d3(std::from_range, std::views::iota(0, 50), hl);
> +  std::hive<int> s3(std::from_range, std::views::iota(100, 150), hl);
> +  erase_even(s3);
> +  op(d3, s3, 0);
> +
> +  std::hive<int> d4(std::from_range, std::views::iota(0, 50), hl);
> +  std::hive<int> s4(std::from_range, std::views::iota(100, 150), hl);
> +  erase_even(d4);
> +  erase_even(s4);
> +  op(d4, s4, 0);
> +
> +  std::hive<int> d5(std::from_range, std::views::iota(0, 50), hl);
> +  std::hive<int> s5(std::from_range, std::views::iota(100, 150), hl);
> +  erase_even(d5);
> +  op(d5, s5, 0);
> +}
> +
> +void
> +test_op(op_t<int> op)
> +{
> +  test_limits(op, std::hive<int>::block_capacity_default_limits());
> +  test_limits(op, std::hive_limits(20, 50));
> +  test_limits(op, std::hive_limits(5, 10));
> +  test_limits(op, std::hive_limits(10, 10));
> +  test_limits(op, std::hive_limits(2, 4));
> +}
> +
> +void
> +test_limits_mismatch()
> +{
> +  std::hive<int> dst(std::from_range, std::views::iota(0, 50),
> std::hive_limits(10, 20));
> +  std::hive<int> src(std::from_range, std::views::iota(100, 150),
> std::hive_limits(20, 50));
> +  try
> +  {
> +    dst.splice(src);
> +    VERIFY(false);
> +  }
> +  catch (const std::length_error&)
> +  { }
> +
> +  VERIFY( std::ranges::equal(dst, std::views::iota(0, 50)) );
> +  VERIFY( std::ranges::equal(src, std::views::iota(100, 150)) );
> +}
> +
> +int main()
> +{
> +  test_op(splice);
> +  test_op(swap);
> +  test_limits_mismatch();
> +}
> diff --git a/libstdc++-v3/testsuite/23_containers/hive/throws.cc
> b/libstdc++-v3/testsuite/23_containers/hive/throws.cc
> new file mode 100644
> index 00000000000..f6be21b10e4
> --- /dev/null
> +++ b/libstdc++-v3/testsuite/23_containers/hive/throws.cc
> @@ -0,0 +1,352 @@
> +// { dg-do run { target c++26 } }
> +
> +#include <hive>
> +
> +#include <algorithm>
> +#include <ranges>
> +#include <vector>
> +#include <testsuite_hooks.h>
> +
> +struct Thrower
> +{
> +  struct Exception {};
> +
> +  static inline size_t copy = 0;
> +  static inline size_t assign = 0;
> +  static inline size_t create = 0;
> +  static inline size_t destroy = 0;
> +  static inline size_t throwAfter = -1;
> +
> +  static void resetCounters()
> +  {
> +    create = copy = assign = destroy = 0;
> +    throwAfter = -1;
> +  }
> +
> +  Thrower()
> +  : Thrower(0)
> +  {}
> +
> +  Thrower(int p)
> +  : x(p)
> +  { ++create; }
> +
> +  ~Thrower()
> +  { ++destroy; }
> +
> +  Thrower(const Thrower& other)
> +  : x(other.x)
> +  {
> +    if (copy + assign >= throwAfter)
> +      throw Exception();
> +    ++copy;
> +  }
> +
> +  Thrower& operator=(const Thrower& other)
> +  {
> +    if (copy + assign >= throwAfter)
> +      throw Exception();
> +
> +    ++assign;
> +    this->x = other.x;
> +    return *this;
> +  }
> +
> +  int x;
> +
> +  friend constexpr bool
> +  operator==(const Thrower&, const Thrower&) = default;
> +
> +  friend constexpr bool
> +  operator==(const Thrower& nm, int y)
> +  { return nm.x == y; }
> +};
> +
> +constexpr bool
> +limits_eq(std::hive_limits lhs, std::hive_limits rhs)
> +{ return lhs.min == rhs.min && lhs.max == rhs.max; }
> +
> +template<typename Hive>
> +constexpr bool
> +limits_eq(const Hive& hive, std::hive_limits rhs)
> +{ return limits_eq(hive.block_capacity_limits(), rhs); }
> +
> +void
> +test_inserts(std::hive<Thrower>& hive)
> +{
> +  const std::vector<int> source(std::from_range, hive |
> std::views::transform(&Thrower::x));
> +  auto is_subset = [&source](std::span<const int> s, const
> std::hive<Thrower>& h)
> +  {
> +    auto sit = s.begin(), send = s.end();
> +    auto hit = h.begin(), hend = h.end();
> +    for (auto hit = h.begin(), hend = h.end();
> +        sit != send && hit != hend;
> +        ++hit)
> +      if (hit->x == *sit)
> +       ++sit;
> +    return sit == send;
> +  };
> +
> +  std::vector<Thrower> v{1,2,3,4,5,6,7,8,9,10};
> +
> +  Thrower::resetCounters();
> +  Thrower::throwAfter = 0;
> +  try {
> +    hive.emplace(v.front());
> +    VERIFY( false );
> +  } catch (const Thrower::Exception&) {
> +  }
> +  VERIFY( hive.size() == source.size() );
> +  VERIFY( is_subset(source, hive) );
> +  VERIFY( Thrower::copy == 0 );
> +  VERIFY( Thrower::assign == 0 );
> +
> +  try {
> +    hive.insert_range(v);
> +    VERIFY( false );
> +  } catch (const Thrower::Exception&) {
> +  }
> +  VERIFY( hive.size() == source.size() );
> +  VERIFY( is_subset(source, hive) );
> +  VERIFY( Thrower::copy == 0 );
> +  VERIFY( Thrower::assign == 0 );
> +
> +  try {
> +    hive.assign_range(v);
> +    VERIFY( false );
> +  } catch (const Thrower::Exception&) {
> +  }
> +  VERIFY( hive.size() == source.size() );
> +  VERIFY( is_subset(source, hive) );
> +  VERIFY( Thrower::copy == 0 );
> +  VERIFY( Thrower::assign == 0 );
> +
> +  Thrower::resetCounters();
> +  Thrower::throwAfter = 3;
> +  try {
> +    hive.insert_range(v);
> +    VERIFY( false );
> +  } catch (const Thrower::Exception&) {
> +  }
> +  VERIFY( hive.size() == source.size() + 3 );
> +  VERIFY( is_subset(source, hive) );
> +  VERIFY( Thrower::copy == 3 );
> +  VERIFY( Thrower::assign == 0 );
> +
> +  Thrower::resetCounters();
> +  Thrower::throwAfter = 7;
> +  try {
> +    hive.assign_range(v);
> +    VERIFY( false );
> +  } catch (const Thrower::Exception&) {
> +  }
> +  VERIFY( hive.size() >= source.size() + 0 );
> +  VERIFY( hive.size() <= source.size() + 7 );
> +  VERIFY( is_subset(source | std::views::drop(7), hive) );
> +  VERIFY( Thrower::copy + Thrower::assign == 7 );
> +
> +  Thrower::resetCounters();
> +}
> +
> +void
> +test_inserts()
> +{
> +  const auto hl = std::hive<Thrower>::block_capacity_default_limits();
> +  std::hive<Thrower> h0(hl);
> +  test_inserts(h0);
> +
> +  std::hive<Thrower> h1(hl);
> +  h1.reserve(4);
> +  h1.reserve(3);
> +  test_inserts(h1);
> +
> +  std::hive<Thrower> h2({-1, -2, -3, -4, -5}, hl);
> +  test_inserts(h2);
> +
> +  std::hive<Thrower> h3(100, -1, hl);
> +  for (auto it = h3.begin(); it != h3.end(); )
> +    it = h3.erase(++it);
> +  test_inserts(h3);
> +
> +  std::hive<Thrower> h4(80, -2, hl);
> +  for (auto it = h4.begin(); it != h4.end(); std::advance(it, 10))
> +    it = h4.erase(it, std::next(it, 10));
> +  test_inserts(h4);
> +
> +  std::hive<Thrower> h5(50, -3, hl);
> +  h5.erase(std::next(h5.begin(), 42), std::next(h5.begin(), 48));
> +  h5.erase(std::next(h5.begin(), 33), std::next(h5.begin(), 35));
> +  h5.erase(std::next(h5.begin(), 36), std::next(h5.begin(), 38));
> +  h5.erase(std::next(h5.begin(), 24), std::next(h5.begin(), 28));
> +  h5.erase(std::next(h5.begin(), 12), std::next(h5.begin(), 19));
> +  h5.erase(std::next(h5.begin()), std::next(h5.begin(), 5));
> +  test_inserts(h5);
> +}
> +
> +void
> +test_shrink_to_fit()
> +{
> +  std::initializer_list<Thrower> il
> +  { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 };
> +  std::initializer_list<Thrower> ex
> +  { 0, 2, 4, 6, 8, 10, 12, 14 };
> +  std::hive<Thrower> h1(il, std::hive_limits(2, 5));
> +  std::erase_if(h1, [](const Thrower& t) { return t.x % 2; });
> +  VERIFY( std::ranges::equal(h1, ex) );
> +
> +  Thrower::resetCounters();
> +  Thrower::throwAfter = 0;
> +  try {
> +    h1.shrink_to_fit();
> +    VERIFY( false );
> +  } catch (const Thrower::Exception&) {
> +  }
> +  VERIFY( h1.size() == 8 );
> +  // 3x5 active block, and 1x3 reserved
> +  VERIFY( h1.capacity() == 18 );
> +  VERIFY( std::ranges::is_permutation(h1, ex)  );
> +  VERIFY( Thrower::copy == 0 );
> +  VERIFY( Thrower::destroy == 0 );
> +
> +  Thrower::throwAfter = 3;
> +  try {
> +    h1.shrink_to_fit();
> +    VERIFY( false );
> +  } catch (const Thrower::Exception&) {
> +  }
> +  VERIFY( h1.size() == 8 );
> +  // 2x5 and 1x3 active block
> +  VERIFY( h1.capacity() == 13 );
> +  VERIFY( std::ranges::is_permutation(h1, ex)  );
> +  VERIFY( Thrower::copy == 3 );
> +  VERIFY( Thrower::destroy == 3 );
> +
> +  Thrower::throwAfter = 5;
> +  h1.shrink_to_fit();
> +  // 1x5, 1x3 active block
> +  VERIFY( h1.capacity() == 8 );
> +  VERIFY( std::ranges::is_permutation(h1, ex)  );
> +  VERIFY( Thrower::copy == 5 );
> +  VERIFY( Thrower::destroy == 5 );
> +
> +  Thrower::resetCounters();
> +}
> +
> +void
> +test_reshape()
> +{
> +  std::initializer_list<Thrower> il
> +  { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 };
> +  const std::hive_limits hl(4, 4);
> +  std::hive<Thrower> h1(il, hl);
> +
> +  Thrower::resetCounters();
> +  Thrower::throwAfter = 0;
> +  try {
> +    h1.reshape({5, 5});
> +    VERIFY( false );
> +  } catch (const Thrower::Exception&) {
> +  }
> +  VERIFY( limits_eq(h1, {4, 5}) );
> +  VERIFY( h1.size() == 12 );
> +  // 3x4 active block, 3x5 reserved
> +  VERIFY( h1.capacity() == 27 );
> +  VERIFY( std::ranges::equal(h1, il)  );
> +  VERIFY( Thrower::copy == 0 );
> +  VERIFY( Thrower::destroy == 0 );
> +
> +  // Throw after first active block of size 4
> +  Thrower::throwAfter = 4;
> +  try {
> +    h1.reshape({5, 5});
> +    VERIFY( false );
> +  } catch (const Thrower::Exception&) {
> +  }
> +  VERIFY( limits_eq(h1, {4, 5}) );
> +  VERIFY( h1.size() == 12 );
> +  // 2x4+1x5 active block, 2x5 reserved
> +  VERIFY( h1.capacity() == 23 );
> +  VERIFY( std::ranges::is_permutation(h1, il)  );
> +  VERIFY( Thrower::copy == 4 );
> +  VERIFY( Thrower::destroy == 4 );
> +
> +  // Throw in middle of active block of size 4
> +  Thrower::throwAfter = 10;
> +  try {
> +    h1.reshape({5, 5});
> +    VERIFY( false );
> +  } catch (const Thrower::Exception&) {
> +  }
> +  VERIFY( limits_eq(h1, {4, 5}) );
> +  VERIFY( h1.size() == 12 );
> +  // 1x4+2x5 active block, 1x5 reserved
> +  VERIFY( h1.capacity() == 19 );
> +  VERIFY( std::ranges::is_permutation(h1, il)  );
> +  VERIFY( Thrower::copy == 10 );
> +  VERIFY( Thrower::destroy == 10 );
> +
> +  // Going back to blocks of size 4, throw in mid of first block
> +  Thrower::resetCounters();
> +  Thrower::throwAfter = 4;
> +  try {
> +    h1.reshape({4, 4});
> +    VERIFY( false );
> +  } catch (const Thrower::Exception&) {
> +  }
> +  VERIFY( limits_eq(h1, {4, 5}) );
> +  VERIFY( h1.size() == 12 );
> +  // 2x4+2x5 active block, 1x4 reserved
> +  VERIFY( h1.capacity() == 22 );
> +  VERIFY( std::ranges::is_permutation(h1, il)  );
> +  VERIFY( Thrower::copy == 4 );
> +  VERIFY( Thrower::destroy == 4 );
> +
> +  // Finish that first block of size 5
> +  Thrower::throwAfter = 5;
> +  try {
> +    h1.reshape({4, 4});
> +    VERIFY( false );
> +  } catch (const Thrower::Exception&) {
> +  }
> +  VERIFY( limits_eq(h1, {4, 5}) );
> +  VERIFY( h1.size() == 12 );
> +  // 2x4+1x5 active block, 1x4 reserved
> +  VERIFY( h1.capacity() == 17 );
> +  VERIFY( std::ranges::is_permutation(h1, il)  );
> +  VERIFY( Thrower::copy == 5 );
> +  VERIFY( Thrower::destroy == 5 );
> +
> +  Thrower::throwAfter = 8;
> +  try {
> +    h1.reshape({4, 4});
> +    VERIFY( false );
> +  } catch (const Thrower::Exception&) {
> +  }
> +  VERIFY( limits_eq(h1, {4, 5}) );
> +  VERIFY( h1.size() == 12 );
> +  // 2x4+1x5 active block, 1x4 reserved
> +  VERIFY( h1.capacity() == 17 );
> +  VERIFY( std::ranges::is_permutation(h1, il)  );
> +  VERIFY( Thrower::copy == 8 );
> +  VERIFY( Thrower::destroy == 8 );
> +
> +  // Move remaining 2 elements
> +  Thrower::throwAfter = 10;
> +  h1.reshape({4, 4});
> +  VERIFY( limits_eq(h1, {4, 4}) );
> +  VERIFY( h1.size() == 12 );
> +  // 3x4 active blocks
> +  VERIFY( h1.capacity() == 12 );
> +  VERIFY( std::ranges::is_permutation(h1, il)  );
> +  VERIFY( Thrower::copy == 10 );
> +  VERIFY( Thrower::destroy == 10 );
> +
> +  Thrower::resetCounters();
> +}
> +
> +int main()
> +{
> +  test_inserts();
> +  test_shrink_to_fit();
> +  test_reshape();
> +}
> --
> 2.55.0
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://gcc.gnu.org/pipermail/gcc-patches/attachments/20261001/2cb0668b/attachment-0001.htm>


More information about the Gcc-patches mailing list