Boost.Heap iteratorとordered_iterator

Boost.Heapの優先順位付きキューの特徴として、「イテレータを持っている」というのがあります。
さらに、iteratorに加えてordered_iteratorというを持っている優先順位付きキューのバリエーションがあります。
これらの違いを確認しようと思います。

まず、イテレータを使わない場合の操作。pushしてpopしていきます。
この操作では、優先順に処理されます。

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

int main ()
{
    boost::heap::fibonacci_heap<int> que;

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

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

4
3
1

次に、iteratorを使う場合。
通常の優先順付きキューの処理順ではなく、LIFOで処理されます。

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

int main ()
{
    boost::heap::fibonacci_heap<int> que;

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

    std::for_each(que.begin(), que.end(), [](int x) {
        std::cout << x << std::endl;
    });
}

4
1
3

最後にordered_iterator。これは通常のtop, popするのと同じく、優先順に処理されます。

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

int main ()
{
    boost::heap::fibonacci_heap<int> que;

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

    std::for_each(que.ordered_begin(), que.ordered_end(), [](int x) {
        std::cout << x << std::endl;
    });
}

4
3
1

ordered_iteratorを持っているかどうかは、PriorityQueue::has_ordered_iteratorsというbool値で判断できます。

#include <iostream>
#include <boost/utility/enable_if.hpp>
#include <boost/heap/fibonacci_heap.hpp>
#include <boost/heap/priority_queue.hpp>

template <class PriorityQueue>
typename boost::enable_if_c<PriorityQueue::has_ordered_iterators>::type
    foo(const PriorityQueue& que)
{
    std::for_each(que.ordered_begin(), que.ordered_end(), [](int x) {
        std::cout << x << ' ';
    });
    std::cout << std::endl;
}

template <class PriorityQueue>
typename boost::disable_if_c<PriorityQueue::has_ordered_iterators>::type
    foo(const PriorityQueue&)
{
    std::cout << "hasn't ordered iterator" << std::endl;
}

int main ()
{
    {
        boost::heap::fibonacci_heap<int> que;
        que.push(3);
        que.push(1);
        que.push(4);

        foo(que);
    }
    {
        boost::heap::priority_queue<int> que;
        que.push(3);
        que.push(1);
        que.push(4);

        foo(que);
    }
}

4 3 1
hasn't ordered iterator

なんとなく、Boost.MultiIndexっぽい。

しかし現状、orderedじゃないイテレータを使っても値を読み取り専用で参照するくらいしかできない気がする。イテレータ指定のpopがあれば、非優先順位付きキューとしても使える、みたいなのになりそう。