Boost.Heap コンテナの設定

Boost.Heapのコンテナは、標準コンテナのようにアロケータや比較関数をカスタマイズできるPolicy-based Designに基づいています。
標準コンテナはこれらの設定がテンプレート引数の順番に依存していますが、Boost.Heapの場合は名前付きテンプレート引数を採用しているので、指定する順番はユーザーが好きに決めることができます。

• 優先順位を決めるための比較関数をカスタマイズしたい場合、Boost.Heapのコンテナにboost::heap::compareを指定します。デフォルトではboost::heap::compare>が設定されます。

• アロケータをカスタマイズしたい場合、Boost.Heapのコンテナにboost::heap::allocatorを指定します。デフォルトではboost::heap::compare>が設定されます。

• Boost.Heapのコンテナでは、size()メンバ関数がデフォルトで定数時間で計算されます。これは、サイズのためのメンバ変数を内部に保持することを意味します。size()メンバ関数に定数時間が必要ない場合、boost::heap::constant_time_sizeを指定することで線形時間にすることができます。デフォルトではboost::heap::constant_time_sizeが設定されます。

#include <iostream>
#include <boost/heap/fibonacci_heap.hpp>

namespace heap = boost::heap;

int main ()
{
    heap::fibonacci_heap<
        int,
        heap::allocator<std::allocator<int>>,
        heap::compare<std::greater<int>>,
        heap::constant_time_size<false>
    > que;

    que.push(3);
    que.push(1);
    que.push(4);

    std::cout << "size: " << que.size() << std::endl;

    while (!que.empty()) {
        std::cout << que.top() << std::endl;
        que.pop();
    }
}

size: 3
1
3
4

この他にも、stable、mutable_、stability_counter_type、arity、store_parent_pointerといった設定があります。

参照：
Data Structure Configuration - Boost Heap Documentation