c++ - 为固定大小的多索引多态容器 boost 多索引

Question

仍在深入研究 C++/boost，欢迎任何评论/反馈。

我正在玩 boost::unordered_maps 并使用形状创建了一个多态示例，大约是在我头脑清醒的时候围绕着它(大部分)我偶然发现了来自 boost multi_index 的 mru 示例。 http://www.boost.org/doc/libs/1_46_1/libs/multi_index/example/serialization.cpp

那时我想。嗯，一个固定大小的多索引多态容器，它将丢弃基于LRU，不实现听起来很疯狂。

    #include <boost/multi_index_container.hpp>
    #include <boost/multi_index/hashed_index.hpp>
    #include <boost/multi_index/identity.hpp>
    #include <boost/multi_index/sequenced_index.hpp>
    #include <boost/shared_ptr.hpp>
    #include <boost/tuple/tuple.hpp>
    #include "boost/tuple/tuple_comparison.hpp"

    enum shape_returns {
        SHAPE_ERROR = -1,
        SHAPE_OK = 0
    };

    // coordinates
    typedef boost::tuples::tuple<int, int, int> ShapeKey;

    class Shape {
    public:
        Shape() : pos() {}
        ~Shape() {}

        virtual int draw() { return SHAPE_ERROR; }

        ShapeKey pos;
    };
    typedef boost::shared_ptr<Shape> Shape_ptr;

    class Circle : public Shape {
    public:
        Circle() {}
        ~Circle() {}

        int radius;

        virtual int draw() { /* draw stuff */ return SHAPE_OK; }
    };
    typedef boost::shared_ptr<Circle> Circle_ptr;

    class Square : public Shape {
    public:
        Square() {}
        ~Square() {}

        int len;

        virtual int draw() { /* draw stuff */ return SHAPE_OK; }
    };
    typedef boost::shared_ptr<Square> Square_ptr;

    using namespace boost::multi_index;

    // multi index tags
    struct seq  {};
    struct hash {};

    class ShapesLRU {
        typedef boost::multi_index::multi_index_container<
          Shape_ptr,
          boost::multi_index::indexed_by<
            boost::multi_index::sequenced<boost::multi_index::tag<seq> >,
            boost::multi_index::hashed_unique<
              boost::multi_index::tag<hash>,
              boost::multi_index::identity<Shape_ptr>
            >
          >
        > shapes_list;

    public:
        typedef typename shapes_list::iterator iterator;
        typedef typename boost::multi_index::index<shapes_list, seq>::type seq_index;
        typedef typename boost::multi_index::index<shapes_list, hash>::type hashed_index;

        ShapesLRU (std::size_t max) : max_shapes(max) {}
        ~ShapesLRU() {}

        void insert(const Shape_ptr item)
        {
            std::pair<typename shapes_list::iterator, bool> ret = shapes.push_front(item);

            if (!ret.second) {
                // new item may be different
                erase(item->pos);
                ret = shapes.push_front(item);
            } else if (shapes.size() > max_shapes) {
                shapes.pop_back();
            }
        }

        typename shapes_list::iterator begin() { return shapes.begin(); }
        typename shapes_list::iterator end() { return shapes.end(); }

        typename hashed_index::iterator hash_begin() { return shapes.get<hash>().begin(); }
        typename hashed_index::iterator hash_end() { return shapes.get<hash>().end(); }

        typename hashed_index::iterator find(const ShapeKey &key)
        {
            Shape_ptr tmp(new Shape());
            tmp->pos = key;

            // XXX why compiler error w/o "using namespace boost::multi_index"
            return shapes.get<hash>().find(tmp);
        }

        void erase(const ShapeKey &key)
        {
            typename hashed_index::iterator itr = find(key);
            // XXX why compiler error w/o "using namespace boost::multi_index"
            shapes.get<hash>().erase(itr);
        }

    private:
        // The multi-indexed data store
        shapes_list shapes;

        // The size of the data store
        std::size_t max_shapes;
    };

    inline std::size_t
    hash_value(const Shape_ptr shape)
    {
        std::size_t seed = 0;

        boost::hash_combine(seed, shape->pos.get<0>());
        boost::hash_combine(seed, shape->pos.get<1>());
        boost::hash_combine(seed, shape->pos.get<2>());

        return seed;
    }

    int
    main()
    {
        ShapesLRU shapes(10);

        Circle_ptr cptr1(new Circle());
        ShapeKey pos1(1, 1, 1);
        cptr1->pos = pos1;
        cptr1->radius = 1;

        Circle_ptr cptr2(new Circle());
        ShapeKey pos2(2, 2, 2);
        cptr2->radius = 2;
        cptr2->pos = pos2;

        shapes.insert(cptr1);

        ShapesLRU::hashed_index::iterator itr = shapes.find(pos1);

        return 0;
    }

在完成大量工作后，我仍然有以下问题。

1. 在 insert() 中有没有办法从序列中得到一个 hashed_unique 迭代器迭代器以便我可以直接调用删除？

2. 有没有更好的方法来实现查找？如果我能找到类似的东西就好了仅使用键的 boost::unordered_map，而不必创建虚拟对象形状只是为了查找。

3. get<> 的正确路径是什么(请参阅代码中的 XXX 注释)我尝试了所有正确的方法，然后开始随机尝试，但没有成功。

4. 我真的很想要一个 [] 运算符，但我认为那是一种方式......shapes[cptr1->pos] = cptr1;

5. 如何从我的 hash_index::iterator 中获取项目(或理解它的一般意义)，打印它肯定没有帮助...

p itr$1 = {, std::allocator >> >, boost::multi_index::detail::bucket_array >> >, boost::shared_ptr, long, boost::shared_ptr const*, boost::shared_ptr const&>> = {, std::allocator >> >, boost::multi_index::detail::bucket_array >> >, boost::shared_ptr const*, boost::iterator, long, boost::shared_ptr const*, boost::shared_ptr const&>> > = {, std::allocator >> >, boost::multi_index::detail::bucket_array >> >, boost::shared_ptr const*, boost::iterator, long, boost::shared_ptr const*, boost::shared_ptr const&>>> = {, std::allocator >> >, boost::multi_index::detail::bucket_array >> >, boost::incrementable, std::allocator >> >, boost::multi_index::detail::bucket_array >> >, boost::dereferenceable, std::allocator >> >, boost::multi_index::detail::bucket_array >> >, boost::shared_ptr const*, boost::iterator, long, boost: :shared_ptr const*, boost::shared_ptr const&>> >>> = {, std::allocator >> >, boost::multi_index::detail::bucket_array >> >, boost::dereferenceable, std::allocator >> >, boost::multi_index::detail::bucket_array >> >, boost::shared_ptr const*, boost::iterator, long, boost::shared_ptr const*, boost::shared_ptr const&>> >> = {, std::allocator >> >, boost::multi_index::detail::bucket_array >> >, boost::shared_ptr const*, boost::iterator, long, boost::shared_ptr const*, boost::shared_ptr const&>> > = {, long, boost::shared_ptr const*, boost::shared_ptr const&>> = {, long, boost::shared_ptr const*, boost::shared_ptr const&>> = {, long, boost::shared_ptr const* , boost::shared_ptr const&>> = {}, }, }, }, }, }, }, }, }, 节点 = 0x60a010, 桶 = 0x7ffffffffdd88}

Answer 1

in insert() is there a way to get a hashed_unique iterator from the sequence iterator so I can call erase directly?

参见 iterator projection .

is there a better way implement find? It would nice if I could do a find like a boost::unordered_map using just the key, instead of having to create a dummy shape just for a lookup.

首先，我认为您当前的实现是错误的:您的散列索引基于 Shape_ptr平等，这不是你所追求的——你想要基于 Shape::ShapeKey 的平等.为了得到这个，只需将索引重新定义为

boost::multi_index::hashed_unique<
  boost::multi_index::tag<hash>,
  boost::multi_index::member<Shape,ShapeKey,&Shape::pos>
>

为此，您必须为 ShapeKey 实现哈希, 留作练习 :-) 现在实现 find就这么简单

hashed_index::iterator find(const ShapeKey &key)
{
    return shapes.get<hash>().find(key);
}

What is the correct path for get<> (see XXX comments in code) I tried everything I was correct and then just started trying random crap, nothing ever panned out.

我不明白为什么你的语法不起作用。应该的。

I would really like a [] operator, but I think that is a ways off... shapes[cptr1->pos] = cptr1;

Boost.MultiIndex 中的索引是根据 std::set 建模的和 std::unordered_set而不是 std::map和 std::unordered_map (出于根本原因，我们不需要在这里讨论。)但是考虑一个 map<T,Q>几乎是一个 set<mutable_pair<T,Q>> , 其中mutable_pair是一个对结构，其第二个成员是 mutable .您可以利用这种等价性来使用 Boost.MultiIndex 构建类似 map 的结构。

How can get the item (or make sense of this in general) from my hash_index::iterator, printing it certainly didn't help...

“打印”是什么意思？