std::hiveとは

std::hiveとは、C++26から標準ライブラリに追加されたコンテナーで、'bucket array'や'object pool'という名前でも知られています。当初はstd::colonyという名前で提案されていましたが、最終的にはstd::hiveという名前で採用されました。

提案文書:P0447R28

std::hiveは、要素をある程度の大きさのまとまりのブロックとして確保し、ブロック同士をリンクリストでつないだ構造をしています。

• 要素の追加/削除が高速
• 要素のイテレーションが高速

という特徴があり、std::vectorとstd::listの長所を併せ持っているということができます。
パフォーマンスクリティカルな領域(例えばトレーディング、3Dシミュレーション、物理シミュレーション etc)で需要があります。

要素の追加

std::vectorでは、要素を追加する時にキャパシティをオーバーした場合、新たにメモリを確保して既存の要素を全て移動します。std::hiveではキャパシティをオーバーしても、新たなブロックを確保してリンクリストにつなぐだけなので、既存要素の移動は発生しません。

要素の削除

std::vectorでは末尾以外の要素を削除したとき、それ以降の要素を前に移動する必要があります。std::hiveでは要素が削除されてもメモリ上の配置はそのままで、削除されたフラグを立てるだけです。

要素のイテレーション

std::listでは要素がメモリ上に散らばって確保されるため、キャッシュ効率が悪くなる可能性があります。std::hiveではブロック内の要素はメモリ上で隣接しているため(歯抜けになっていることはありますが)、ある程度キャッシュヒットすることが期待できます。
std::vectorのキャッシュ効率には敵いませんが、std::hiveもそれほど悪くないでしょう。

要素の順番は実装依存

std::hiveに追加した要素がどのような順番で並んでいるかは実装依存です。ブロックの先頭からできるだけ詰めて追加するかもしれませんし、そうでないかもしれません。そのため、順番に依存したような処理は書かないようにする必要があります。

std::hive<int> h;
h.emplace(10);
h.emplace(20);
// *h.begin() == 10 でない可能性がある

insertやemplace_hintにはhint引数を持つものがありますが、その引数は単に無視され、指定した位置に要素を追加することはできません。

また、要素へのインデックスアクセスはできませんので、インデックスアクセスしたい場合は別のコンテナーを使う必要があります。

要素のアドレスは安定

std::vectorでは要素の追加や削除に伴って要素の移動が発生することがあるため、要素へのポインタが無効になる可能性があります。そのため、ポインタを保存しておくことは一般的には危険です。

std::vector<int> v;
v.push_back(10);
int* p = &v[0];
v.push_back(20);
// pは無効化されている可能性がある

std::hiveでは要素の追加や削除ではポインタが無効化されることが無いため、それを前提とした処理をすることが可能です。
例えば、ポインタをstd::vectorに保存することで、std::hiveを使いつつインデックスアクセスを行うことができたりします。

std::hive<int> h;
std::vector<int*> v;
for (int i = 0; i < 10; ++i)
{
	it = h.insert(i * 10);
	v.push_back(&(*it));
}
assert(*v[0] == 0);
assert(*v[1] == 10);
assert(*v[2] == 20);

ただし、reshapeやsort等、一部のメンバ関数はポインタを無効化する場合があるので、それらを使う場合には注意が必要です。

まとめ

C++26から追加されるstd::hiveは、クセは強いですが特定の場面では力を発揮し、他のコンテナーと比べてパフォーマンスが良くなる可能性があります。
コンテナーの選択肢の一つとして検討してみてはいかがでしょうか？