jeudi 8 novembre 2012

Using Boost any_iterator to hide multi_index

Not so long ago i was faced with an issue with a library i created at work... it took ages to compile.

The fault was on Boost.MultiIndex whitch was using too much metatemplate programming techniques for my working computer. We use a continuous integration system, but i like to test everything on my developpement machine.

So i wondered how difficult it could be to hide it from the header. using a simple pimpl idiom couldn't work because i needed to expose some sort of iteration mecanism to the user. I searched over boost and found the any_range class and digged into the arcanes of Boost code to get it's any_iterator implementation.

any_iterator is a detail implementation of Boost any_range whitch is part of the Boost.Range library. It uses a stacked memory optimisation compared to others iterator abstractions who allocate memory on heap for the stored wrapped iterator. However, there is still a big performance hit when using any_iterator as it is using virtual methods behind the hood to abstract the wrapped iterator. There is currently another pending implementation of any_iterator in Boost with the inclusion of Boost.TypeErasure library. For the moment this library is not included in Boost releases (ie: currently Boost 1.52), but you can find it on Boost svn trunk.

Header exemple :
#include <string>
// note that there is no include to multi_index here! 
#include <boost/scoped_ptr.hpp>
#include <boost/range/concepts.hpp>
#include <boost/range/detail/any_iterator.hpp>

class hidden_container; //forward declare the hidden container

class exemple {
public:
  boost::scoped_ptr<hidden_container> impl; //hidden container behind pointer

  // declare a type erased iterator that can iterate over any container of std::string
  // this could be a std::vector<std::string>::const_iterator or a std::list<std::string>::const_iterator
  typedef boost::range_detail::any_iterator<
         const std::string,
         boost::forward_traversal_tag,
         const std::string&,
         std::ptrdiff_t
         > const_iterator;

  //ctor
  exemple();
  // abstracted iterators
  const_iterator begin() const;
  const_iterator end() const;

};

Implementation exemple :
#include "exemple.h"
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/composite_key.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/ordered_index.hpp>

namespace tag {
   struct sequenced {};
   struct ordered {};
}

class hidden_container : public boost::multi_index::multi_index_container<
   std::string,
   boost::multi_index::indexed_by<
      boost::multi_index::sequenced<
         boost::multi_index::tag<tag::sequenced>
      >,
      boost::multi_index::ordered_unique<
         boost::multi_index::tag<tag::ordered>,
         boost::multi_index::identity<std::string>
      >
   >
>
{};

exemple::exemple():
impl(new hidden_container())
{
}

exemple::const_iterator exemple::begin() const
{
   return const_iterator(impl->get<tag::sequenced>().begin());
}

exemple::const_iterator exemple::end() const
{
   return const_iterator(impl->get<tag::sequenced>().end());
}