c++ - C++ Bimap左unordered_map右排序的可变多图

我需要为我的项目实现以下数据结构。我有一个关系

const MyClass*

至

uint64_t

对于每个指针，我想保存一个与其连接的计数器，该计数器可以随时间变化（实际上只是递增）。这没问题，我可以简单地将其存储在std :: map中。问题是我需要快速访问具有最高值的指针。

这就是为什么我得出结论使用boost :: bimap的原因。对于我的项目，定义如下：

typedef boost::bimaps::bimap<
        boost::bimaps::unordered_set_of< const MyClass* >,
        boost::bimaps::multiset_of< uint64_t, std::greater<uint64_t> >
> MyBimap;
MyBimap bimap;

这可以正常工作，但是我可以修改一次插入的对上的uint64_t吗？文档说multiset_of是常量，因此我不能在bimap中更改对的值。

我能做什么？在此bimap中更改一个键的值的正确方法是什么？还是有可能为该问题提供更简单的数据结构？

最佳答案

这是一个简单的手工解决方案。

在内部，它保留一个映射来存储由对象指针索引的计数，以及进一步的多个迭代器集，这些迭代器按其指针的降序排列。

每当您修改计数时，都必须重新编制索引。我已经完成了此零碎工作，但是您可以根据需要将其作为批处理更新来进行。

请注意，在c ++ 17中，建议对集合和映射使用splice操作，这将使重新索引变得非常快。

#include <map>
#include <set>
#include <vector>

struct MyClass { };


struct store
{

    std::uint64_t add_value(MyClass* p, std::uint64_t count = 0)
    {
        add_index(_map.emplace(p, count).first);
        return count;
    }

    std::uint64_t increment(MyClass* p)
    {
        auto it = _map.find(p);
        if (it == std::end(_map)) {
            // in this case, we'll create one - we could throw instead
            return add_value(p, 1);
        }
        else {
            remove_index(it);
            ++it->second;
            add_index(it);
            return it->second;
        }
    }

    std::uint64_t query(MyClass* p) const {
        auto it = _map.find(p);
        if (it == std::end(_map)) {
            // in this case, we'll create one - we could throw instead
            return 0;
        }
        else {
            return it->second;
        }
    }

    std::vector<std::pair<MyClass*, std::uint64_t>> top_n(std::size_t n)
    {
        std::vector<std::pair<MyClass*, std::uint64_t>> result;
        result.reserve(n);
        for (auto idx = _value_index.begin(), idx_end = _value_index.end() ;
             n && idx != idx_end ;
             ++idx, --n) {
            result.emplace_back((*idx)->first, (*idx)->second);
        }
        return result;
    }

private:
    using map_type = std::map<MyClass*, std::uint64_t>;
    struct by_count
    {
        bool operator()(map_type::const_iterator l, map_type::const_iterator r) const {
            // note: greater than orders by descending count
            return l->second > r->second;
        }
    };
    using value_index_type = std::multiset<map_type::iterator, by_count>;

    void add_index(map_type::iterator iter)
    {
        _value_index.emplace(iter->second, iter);
    }

    void remove_index(map_type::iterator iter)
    {
        for(auto range = _value_index.equal_range(iter);
            range.first != range.second;
            ++range.first)
        {
            if (*range.first == iter) {
                _value_index.erase(range.first);
                return;
            }
        }

    }

    map_type _map;
    value_index_type _value_index;
};