std::hive

在标头 <hive> 定义
template<     class T,     class Allocator = allocator<T> > class hive;	(1)	(C++26 起)
namespace pmr {     template< class T >     using hive = std::hive<T, polymorphic_allocator<T>>; }	(2)	(C++26 起)

std::hive 是一种序列容器，但只提供有限的序列操作，并且插入顺序是未指定的。std::hive 允许快速插入删除、更快的遍历，且插入和删除元素时所有元素的内存位置绝不改变。这适用于需要动态创建、访问、修改、删除大量的对象且这些对象内持有其他对象的引用或指针的场景，例如游戏和粒子模拟。std::hive 还能从元素的指针获取对应的迭代器。

std::hive 将对象组织到多个尽可能连续的内存空间（块）中，以提高空间局部性，使得其顺序遍历比 std::list 更加缓存友好。删除元素时，会在块中产生空位，连续的空位自动连接成空泡。当块中无元素时则删除该块。每个元素或空位都对应着一个整数，这被称作跳跃域：跳跃域为 0 则意味着该处是元素；位于空泡边界的一个（当空泡仅有一个空位）或两个空位对应的跳跃域为空泡的长度；不位于空泡边缘的跳跃域的值无意义。通过跳跃域，std::hive 保证迭代器每次前进只需要按跳跃域的指示跳跃零次（下一个元素与当前元素相邻）、一次（下一个元素在同一个块内）或两次即可找到下一个元素。

除了跳跃域，每个块还维护一个空闲链表，它串联起块内的每个空泡。同时，std::hive 本身也维护一个空闲链表，它串联起每个存在空泡的块。这使得 std::hive 能够得知所有的空泡和空位，以重用已擦除元素的内存。

std::hive 满足容器 (Container) 、知分配器容器 (AllocatorAwareContainer) 、序列容器 (SequenceContainer) 和可逆容器 (ReversibleContainer) 。

迭代器失效

std::hive 迭代器的很少失效：

• 移动 inplace_vector 并且更换分配器会使所有迭代器失效；
• 当 allocator_traits<Allocator>::propagate_on_container_move_assignment::value 为 false 且两个 hive 的分配器不相等时，移动赋值运算符会使所有迭代器失效；
• 插入或删除元素时，end 迭代器和被删除元素的迭代器失效；
• unique 会使所有迭代器失效；
• sort 可能会使所有迭代器失效；
• shrink_to_fit 和 reshape 在发生重分配时使所有迭代器失效。

模板形参

T	-	元素的类型。 对元素的要求依赖于容器上进行的实际操作。一般地，要求元素类型是完整类型并满足可擦除 (Erasable) ，但许多成员函数附带了更严格的要求。
Allocator	-	用于获取/释放内存及构造/析构内存中元素的分配器。类型必须满足分配器 (Allocator) 。如果 Allocator::value_type 与 T 不同，那么行为未定义(C++20 前)程序非良构(C++20 起)。

成员类型

类型	定义
allocator_type	Allocator
reference	value_type&
const_reference	const value_type&
reverse_iterator	std::reverse_iterator<iterator>
const_reverse_iterator	std::reverse_iterator<const_iterator>

成员函数

Template:cpp/container/dsc trim capacityTemplate:cpp/container/dsc trim capacityTemplate:cpp/container/dsc block capacity limitsTemplate:cpp/container/dsc block capacity default limitsTemplate:cpp/container/dsc block capacity hard limitsTemplate:cpp/container/dsc reshapeTemplate:cpp/container/dsc get iterator

(构造函数)	构造 hive (公开成员函数)
(析构函数)	析构 hive (公开成员函数)
operator=	将值赋给容器 (公开成员函数)
assign	将值赋给容器 (公开成员函数)
assign_range (C++23)	将范围的值赋给容器 (公开成员函数)
get_allocator	返回关联的分配器 (公开成员函数)
元素访问
front	访问第一个元素 (公开成员函数)
迭代器
begincbegin	返回指向起始的迭代器 (公开成员函数)
endcend	返回指向末尾的迭代器 (公开成员函数)
rbegincrbegin	返回指向起始的逆向迭代器 (公开成员函数)
rendcrend	返回指向末尾的逆向迭代器 (公开成员函数)
容量
empty	检查容器是否为空 (公开成员函数)
size	返回元素数 (公开成员函数)
max_size	返回可容纳的最大元素数 (公开成员函数)
capacity	返回当前存储空间能够容纳的元素数 (公开成员函数)
reserve	预留存储空间 (公开成员函数)
shrink_to_fit	通过释放未使用的内存减少内存的使用 (公开成员函数)
修改器
clear	清除内容 (公开成员函数)
insert	插入元素 (公开成员函数)
insert_range (C++23)	插入元素范围 (公开成员函数)
emplace	原位构造元素 (公开成员函数)
emplace_hint	使用提示原位构造元素 (公开成员函数)
erase	擦除元素 (公开成员函数)
swap	交换内容 (公开成员函数)
操作
splice	从另一个 hive 中转移元素 (公开成员函数)
unique	删除连续的重复元素 (公开成员函数)
sort	对元素进行排序 (公开成员函数)

非成员函数

std::swap(std::hive) (C++26)	特化 std::swap 算法 (函数模板)
erase(std::hive)erase_if(std::hive) (C++20)	擦除所有满足特定判别标准的元素 (函数模板)

辅助类型

hive_limits (C++26)

有关 std::hive 中块容量极限的布局信息 (类)

推导指引

(C++17 起)

注解

功能特性测试宏	值	标准	功能特性
__cpp_lib_hive	202502L	(C++26)	std::hive: 一种基于桶的容器，可重用已擦除元素的内存位置

参阅

hive_limits (C++26)

有关 std::hive 中块容量极限的布局信息 (类)