Boost.Multi-index ランク付きインデックス

Boost 1.59.0から、Boost.Multi-indexに、ranked indiciesというのが入ります。

これは、キーが何番目に大きいかを対数時間で取得できる、連想配列のインデックスです。

イメージとしては、mapに対してit = m.find(key)をして得たイテレータに、distance(m.begin(), it)としてイテレータの位置を求めるのが、容易になるという感じです。

#include <iostream>
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ranked_index.hpp>
#include <boost/multi_index/member.hpp>

struct Person {
    int age = 0;
    std::string name;

    Person() {}
    Person(int age, const std::string& name)
        : age(age), name(name) {}
};

using namespace boost::multi_index;
using Container = boost::multi_index_container<
    Person,
    indexed_by<
        ranked_non_unique<member<Person, int, &Person::age>>
    >
>;

int main()
{
    Container c;

    c.emplace(3, "Alice");
    c.emplace(1, "Bob");
    c.emplace(4, "Carol");

    // キー値2を持つ要素が、何番目に大きいかを取得する
    auto it = c.emplace(2, "Hoge").first;
    std::size_t n = c.rank(it);
    std::cout << n << std::endl; // 1

    // キー値4の要素が、何番目に大きいかを取得する
    std::cout << c.find_rank(4) << std::endl; // 3

    // 最後尾にある要素へのイテレータを取得する
    std::cout << c.nth(c.size() - 1)->name << std::endl; // Carol
}

ランク用インタフェースのほかに、mapと同じくイテレータを扱うfind()やlower_bound()のインタフェースも持っています。