std::hive(C++26)

namespace std {
  template <class T, class Allocator = allocator<T>>
  class hive;

  namespace pmr {
    template <class T>
    using hive = std::hive<T, polymorphic_allocator<T>>;
  }
}

概要

std::hiveクラスは、要素のメモリ位置が安定したシーケンスコンテナである。要素の挿入と削除を定数時間で行いつつ、削除されなかった要素へのポインタ・参照・イテレータを無効化しない。

要素は複数のメモリブロック（要素ブロック、element block）に格納される。削除された要素の位置は、後続の要素を移動させる代わりに、定数時間の手法によってイテレーション時にスキップされる。削除によって空になった要素ブロックは、解放されるか、再利用のために予約ブロックとして保持される。

挿入位置はコンテナが決定し、削除された要素のメモリ位置が再利用されることがある。このため、std::hiveクラスは要素の順序を指定した挿入をサポートしない（順序は未規定である）。この性質により、std::hiveクラスはstd::listクラスよりもキャッシュ効率のよいメモリレイアウトと高速なイテレーションを実現しつつ、std::vectorクラスとは異なり要素の挿入・削除でポインタ・参照が無効化されない。

テンプレートパラメータは、以下を意味する：

• T: 格納される要素の型
• Allocator: メモリ確保に使用されるアロケータの型。デフォルトでは標準のstd::allocatorクラスが使用される。

この機能が必要になった背景・経緯

ゲーム開発やシミュレーション、GUIなどの分野では、多数のオブジェクトを頻繁に生成・破棄しながら、それらのオブジェクトを互いにポインタや参照で参照し合うことが多い。このような用途では、次の性質を同時に満たすコンテナが求められる。

• 要素の挿入・削除が高速（定数時間）であること
• 既存の要素へのポインタ・参照・イテレータが、他の要素の挿入・削除によって無効化されないこと
• イテレーションがキャッシュ効率よく行えること

std::vectorは連続したメモリにより高速なイテレーションが可能だが、再確保や要素の削除によってポインタ・参照が無効化される。std::listやstd::forward_listは挿入・削除でポインタ・参照が無効化されないが、要素ごとにノードを個別確保するためイテレーションのキャッシュ効率が悪い。

std::hiveクラスは、複数の要素ブロックに要素をまとめて格納し、削除された位置をスキップすることで、これらの要求を同時に満たす。この設計は、以前は「colony」という名称でBoost C++ Libraries等で提供されていたデータ構造をC++標準ライブラリに導入したものである。

メンバ関数

構築／コピー／破棄

イテレータ

領域

変更

hive操作

静的メンバ関数

メンバ型

非メンバ関数

推論補助

例

基本的な使い方

#include <hive>
#include <print>

int main()
{
  std::hive<int> h;

  // 要素を挿入する。挿入位置はコンテナが決定する
  h.insert(1);
  h.insert(2);
  h.insert(3);

  // 要素を順番に出力する
  for (int x : h) {
    std::print("{} ", x);
  }
  std::println("");

  std::println("size = {}", h.size());
}

出力例

1 2 3 
size = 3

要素のポインタ・参照が安定していることを利用する

std::hiveの最大の特徴は、要素の挿入・削除によって、削除されなかった要素へのポインタ・参照・イテレータが無効化されないことである。多数のオブジェクトを動的に生成・破棄しつつ、それらを互いにポインタで参照し合うような状況で有用となる。

#include <hive>
#include <print>

int main()
{
  std::hive<int> h;

  // 要素を挿入し、そのポインタを保持しておく
  int* p = &*h.insert(42);

  // 別の要素のイテレータも保持しておく
  auto other = h.insert(99);

  // 大量の要素を追加しても、既存要素へのポインタは無効化されない
  // (std::vectorでは再確保によってpが無効化されうる)
  for (int i = 0; i < 10000; ++i) {
    h.insert(i);
  }
  std::println("{}", *p); // 42

  // 任意の要素を定数時間で削除でき、他の要素のポインタ・イテレータは無効化されない
  // (std::vectorのeraseは後続要素を移動させ、ポインタを無効化する)
  h.erase(other);
  std::println("{}", *p); // 42（削除したのは別の要素なので有効なまま）
}

出力

42
42

バージョン

言語

• C++26

処理系

• Clang: 22 ❌
• GCC: 16.1 ❌
• Visual C++: 2026 Update 2 ❌

関連項目

• std::list
• std::forward_list
• std::deque
• std::vector

参照

• P0447R28 Introduction of std::hive to the standard library
  • C++26でhiveが追加された