boost multi index for a fixed sized multi-indexed polymorphic container

Question

Still digging into C++/boost so any comments/feedback are welcome.

I was playing with boost::unordered_maps and created a polymorphic example using shapes, about the time I had my head wrapped around that (mostly) I stumbled across the mru example from boost multi_index. http://www.boost.org/doc/libs/1_46_1/libs/multi_index/example/serialization.cpp

At that point I thought. Hmm, a fixed sized multi-indexed polymorphic container that will discard values based on LRU, that sounds to crazy to not implement.

    #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;
    }

After working through a lot of stuff I am still left with the following questions.

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

2. 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.

3. 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.

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

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

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&>> = {}, }, }, }, }, }, }, }, }, node = 0x60a010, buckets = 0x7fffffffdd88}

Answer 1

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

See 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.

First of all, I think your current implementation is wrong: your hashed index is based on Shape_ptr equality, which is not what you're after --you want equality based on Shape::ShapeKey. In order to get this, simply redefine the index as

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

For this to work you'll have to implement hashing for ShapeKey, left as an exercise :-) Now implementing find is as simple as

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 can't see why your syntax is not working. It should.

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

Indices in Boost.MultiIndex are modelled after std::set and std::unordered_set rather than std::map and std::unordered_map (for fundamental reasons we need not discuss here.) But consider that a map<T,Q> is pretty much a set<mutable_pair<T,Q>>, where mutable_pairis a pair structure whose second member is mutable. You can draw on this equivalence to build map-like structures with Boost.MultiIndex.

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

What do you mean by "printing"?