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.
in insert() is there a way to get a hashed_unique iterator from the sequence iterator so I can call erase directly?
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.
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;
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}
