C++26にて追加されたstd::hiveですが、2025年12月現在ではまだ主要な標準ライブラリ(libstdc++, libc++, Microsoft-STL)には実装されていません。
とはいえ、リファレンス実装(plf_hive)もありますし、提案文書 (p0447r28)でも実装について詳細な考察がされていますので、これらを参考に実装することは可能だと思います。
というわけで拙作のライブラリ(HamonCore)にてhiveを実装しました。(hiveディレクトリを参照してください)
規格ではconstexprになっていませんが、特に支障がなかったのでconstexprに対応してあります。
ナイーブな実装
std::hiveの仕様を聞いたとき、単純に考えれば次のような実装を考えると思います。
template <typename T>
struct element_block
{
size_t capacity;
T* elements;
bool* active_flags;
element_block* next;
element_block* prev;
};
element_blockである程度の数の要素を確保し、これをリンクリストでつなぐ構造ですね。しかし、これでは仕様を満たすことができません。
これは、以下の2つの理由によります。
- イテレータのインクリメント/デクリメントは定数時間でなければならない
- 要素の挿入にかかる時間は定数時間でなければならない
イテレータのインクリメント/デクリメントは定数時間でなければならない
つまり「ブロック内でactive_flagsを順番に見ていって、次にtrueな要素が現れるまで進める」といった実装は許されません。次の有効な要素を、定数時間で取得できるようにする必要があります。
提案文書ではskipfieldというメンバを用意し、次に有効な要素までいくつ離れているかを取得できるようにしています。
また、有効な要素を１つも持っていないブロックについても考えなければいけません。イテレータが、そのブロック内で有効な最後の要素を指していた場合、次のブロックに移動するわけですが、「リストを順番にたどっていって有効な要素を持っているブロックまで進める」という実装は許されません。
要素の挿入にかかる時間は定数時間でなければならない
つまり「active_flagsを順番に見ていって、最初にfalseが現れた位置に挿入する」という実装は許されず、挿入するべき位置を定数時間で取得する必要があります。
また、ブロックに空きがあるかどうかも考慮しなければならず、「リストをたどっていって空きがあるブロックを見つけたら挿入する」という実装は許されません。空きがあるブロックを定数時間で見つける必要があります。
提案文書ではelementsのうちの使われていない要素をフリーリストとして再利用しています。
筆者の実装
上記を踏まえた上で、提案文書とは少し違ったアプローチで実装しました。
まず、説明をするためにブロックの状態を次のように分類します。
- Active ・・・ ブロック内に有効な要素が１つ以上存在する
- Open ・・・ ブロック内に有効でない要素が１つ以上存在する
- Reserved ・・・ ブロック内に有効な要素が１つも存在しない
そしてそれぞれをリンクリストでつなぎます。
Activeブロックのリストはイテレータのために必要で、「次に有効なブロック」を定数時間で取得することができます。
Openブロックのリストは要素の挿入のために必要で、「空きがあるブロック」を定数時間で取得することができます。
Reservedブロックのリストはtrim_capacityというメンバ関数のために必要となります。(後述します)
というわけで、ブロックの構造体は次のようになります。
template <typename T>
struct element_block
{
size_t capacity;
size_t index;
T* elements;
uint64_t active_flags;
element_block* active_next;
element_block* active_prev;
element_block* open_next;
element_block* open_prev;
element_block* reserved_next;
element_block* reserved_prev;
};
active_flagsメンバ
今回の実装での１番のポイントは、uint64_t active_flagsメンバだと思います。0番目のビットが立っていればelements[0]の要素が有効、1番目のビットが立っていればelements[1]の要素が有効、というように対応しています。
前述のbool配列と変わらないと思われるかもしれませんが、std::countr_zeroやstd::countl_zeroを使うことによって、「下位から数えて最初に1になっているビット」や「1になっているビットの次に1になっているビット」などを定数時間で計算することができるので、「ブロック内で最初に有効な要素のインデックス」、「次に有効な要素のインデックス」、「ブロック内で最初に空いている要素のインデックス」を定数時間で取得することができます。
ただし、ブロック内の要素数が最大でも64個に制限されてしまいます。これは少し工夫をすることによってもっと最大数を増やせるのですが(実際の実装では64×64=4096要素まで対応しています)、ここでは説明を簡潔にするために割愛します。
キャッシュ効率だけを考えると、ブロック内の要素数はそれほど多くする必要は無いかもしれません。(もしかしたら64要素でもじゅうぶんかも)
しかし、メモリ使用効率を考えるとある程度大きくできたほうがいいかもしれません。
このあたりは今後の課題としたいです。
indexメンバ
std::hiveのイテレータは大小比較(operator<, operator<=>)ができるようになっています。同じブロックを指しているイテレータ同士なら問題ないのですが、違うブロックを指しているイテレータ同士だと、単純にポインタを大小比較してしまうと未規定の結果となってしまいます。それを避けるために、ブロックにindexメンバ変数が必要となります。
そもそもstd::hiveのイテレータに大小比較って必要なんですかね…？大小比較できるようになっている理由を御存知の方は教えて下さい。
trim_capacityメンバ関数
trim_capacityはReservedブロックを解放する関数です。この関数の計算量ががReservedブロックの数に対して線形と定められているため、「OpenブロックをたどっていってそれがReservedブロックだった場合(要素が一つもない場合)は解放」という実装にはできず、Reservedブロックをあらかじめリストでつなぐようにしました。
この関数以外ではReservedリストが必要になる場面が無かったので、なんとかこの関数の計算量の要件が緩和されないですかね…。
sortメンバ関数
std::hiveはsortメンバ関数を持っています。ランダムアクセス可能でないのに、どうやって実装するのかと思ってリファレンス実装を見てみたところ、「いったんstd::vectorに要素をmoveして、それをソートして、最後にstd::hiveにmoveしなおす」という実装でした。確かにそうするしかないよね～って感じですね。
リファレンス実装では要素のサイズが大きい場合は、直接moveするのではなくてポインタを渡したりしているようですが、今回の実装ではそこまではしませんでした。
get_iteratorメンバ関数
get_iterator関数は、要素を指しているポインタからイテレータを取得する関数です。計算量が「Activeブロックの数に対して線形」と定められています。
そのポインタとpとした場合、elements <= p && p < (elements + capacity)となるブロックをみつけないといけないわけですが、これはポインタの大小比較により未規定の結果となります。
提案文書には
According to Jens Maurer, these difficulties can be bypassed via hidden channels between the library implementation and the compiler.
という記述があり、コンパイラマジックやコンパイラ依存の機能によって実装されることを想定しているようです。
現実的には、主要なコンパイラにおいて、ポインタの大小比較をしても期待通りの動作をしており、とりあえず問題なさそうです。
ただし、未規定の部分があるとconstexprにできないため、定数に評価される場合は異なる実装にしました。イテレータを順にインクリメントしていって、同じアドレスを指しているものを探すようにしました。これは計算量の規格を満たせないわけですが、妥協しました。
今後、規格でstd::hiveがconstexpr対応するとき、この関数はどうするんでしょうかね。get_iteratorだけconstexprにしない、というのも選択肢の一つだと思います。
今後の課題
まだパフォーマンスの計測ができていません。std::hiveはパフォーマンスを売りにしたコンテナだと思いますので、std::vectorやstd::list、リファレンス実装とのパフォーマンスを比較して最適化をする必要があるでしょう。
1つのブロックの最小・最大要素数によってキャッシュ効率が変わることが想定されますので、そのあたりのチューニングも行う必要があります。
今回はactive_flagsというビットフラグを使って要素が有効か無効かを管理したわけですが、他のやり方のほうがベターな可能性もありますので、そのあたりも探っていきたいです。
まとめ
C++26で追加されるstd::hiveを自前で実装しました。割とスムーズに実装でき、constexpr対応も特に問題ありませんでした(get_iterator以外)。
私は標準ライブラリのコンテナを(mdspanを除いて)全て自前実装しましたが、std::hiveは簡単な部類だったと思います。メンバ関数が少ないのがいいですね。
簡単な割に、実装の工夫のしどころがあると思いますので、皆様も実装してみてはいかがでしょうか。