std::hive

来自cppreference.com
< cpp‎ | container

Template:cpp/container/hive/navbar

在标头 <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
(公开成员函数) [编辑]
将值赋给容器
(公开成员函数) [编辑]
将值赋给容器
(公开成员函数) [编辑]
(C++23)
 将范围的值赋给容器
(公开成员函数) [编辑]
返回关联的分配器
(公开成员函数) [编辑]
元素访问
访问第一个元素
(公开成员函数) [编辑]
迭代器
返回指向起始的迭代器
(公开成员函数) [编辑]
返回指向末尾的迭代器
(公开成员函数) [编辑]
返回指向起始的逆向迭代器
(公开成员函数) [编辑]
返回指向末尾的逆向迭代器
(公开成员函数) [编辑]
容量
检查容器是否为空
(公开成员函数) [编辑]
返回元素数
(公开成员函数) [编辑]
返回可容纳的最大元素数
(公开成员函数) [编辑]
返回当前存储空间能够容纳的元素数
(公开成员函数) [编辑]
预留存储空间
(公开成员函数) [编辑]
通过释放未使用的内存减少内存的使用
(公开成员函数) [编辑]
修改器
清除内容
(公开成员函数) [编辑]
插入元素
(公开成员函数) [编辑]
(C++23)
 插入元素范围
(公开成员函数) [编辑]
原位构造元素
(公开成员函数) [编辑]
使用提示原位构造元素
(公开成员函数) [编辑]
擦除元素
(公开成员函数) [编辑]
交换内容
(公开成员函数) [编辑]
操作
从另一个 hive 中转移元素
(公开成员函数) [编辑]
删除连续的重复元素
(公开成员函数) [编辑]
对元素进行排序
(公开成员函数) [编辑]

[编辑] 非成员函数

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

[编辑] 辅助类型

(C++26)
 有关 std::hive 中块容量极限的布局信息
(类) [编辑]

推导指引

 (C++17 起)

[编辑] 注解

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

[编辑] 示例

本节未完成
原因：暂无示例

[编辑] 参阅

(C++26)
 有关 std::hive 中块容量极限的布局信息
(类) [编辑]
来自“https://zh.cppreference.com/mwiki/index.php?title=cpp/container/hive&oldid=101315”