Wednesday, November 24, 2010

Boost multi-index container quirks

I recently had the need to use a container that supports both fast search access and sequential (insert-order) access. The boost::multi_index_container was just that. It is an amazing piece of code. To use the container itself, however, is a bit quirky. First, let's see how we can use it.

Suppose your requirement is to define a map (for fast search) with an int KEY and some satellite data struct DATA, and you still want to access the whole list of (KEY, DATA) pairs in the same order as you inserted them. The way to define a multi_index_container for this is as follows:

#include "boost/multi_index_container.hpp"
#include "boost/multi_index/indexed_by.hpp"
#include "boost/multi_index/seqeunced_index.hpp"
#include "boost/multi_index/ordered_index.hpp"
#include "boost/multi_index/identity.hpp"
#include "boost/multi_index/member.hpp"

typedef std::pair<int,DATA> DataPair;

typedef boost::multi_index_container<datapair,
boost::multi_index::indexed_by <
boost::multi_index::sequenced<>,
boost::multi_index::ordered_unique <
boost::multi_index::member<DataPair,>
>
>
> DataContainer;

enum IndexType {
     kIndexSequential, // = zero (the first index is the sequenced index)
     kIndexSearchable // = one (the second index is the ordered index on the first member of the pair)
};

typedef DataContainer::nth_index<kIndexSequential> SequentialAccessIndex;
typedef DataContainer::nth_index<kIndexSearchable> SearchableAccessIndex;


// To declare a container
DataContainer myContainer;

....

// to insert content
myContainer.push_back(std::make_pair(12, someDATAInstance));
myContainer.push_back(std::make_pair(13, someOtherDATAInstance));
....


// to search for the content
SearchableAccessIndex& srchIdx = myContainer.get<kIndexSearchable>();
SearchableAccessIndex::iterator idx = srchIndex.find(12);
if (idx != srchIdx.end()) {
// ... use it..
}

// to sequentially access (e.g. iterate over the content, or add it to a list)
std::list sequentialDataList;
SequentialAccessIndex& seqIdx = myContainer.get<kIndexSequential>();
std::transform (seqIdx.begin(), seqIdx.end(), std::back_inserter(sequentialDataList),
std::tr1::bind(&DataPair::second, std::tr1::placeholders::_1));


So where are the quirks? Some hint in the last operation we did.. the sequentialDataList had to be declared as a list of const Data. This is the key issue. The multi_index_container does NOT allow changing the data in-place (that's not entirely true).

The container is not (and probably cannot be) programmed to be smart enough to know that only a part of the data is to be modified in-situ, while the indexes will remain intact. So, how does it allow updates? There are two distinct ways:

i) Using replace( ) which is an exception-safe way to do it. It takes the iterator to the element to be replaced, and a new object (which implicitly means your object needs to be copy-constructible).
// replace
SearchableAccessIndex& srchIdx = myContainer.get();
SearchableAccessIndex::iterator idx = srchIndex.find(12);
if (idx != srchIdx.end()) {
DataPair pair = *idx; // copy constructed
pair.second = someNewDATAInstance;
srchIdx.replace (idx, pair);
}

ii) The second, more sophisticated, way is to use modify which takes as its second parameter, a functor. This functor is passed a reference to the object being modified, and is responsible for modifying it as required. So,

// using modify()

struct ModificationFunctor {
ModificationFunctor(const DATA& someDataRef):m_Data(someDataRef)
{
}
void operator()(DataPair& dataPair)
{
dataPair.DATA = m_Data;
}

private:
const DATA& m_Data;
};


...
// actual modify
SearchableAccessIndex& srchIdx = myContainer.get();
SearchableAccessIndex::iterator idx = srchIndex.find(12);
if (idx != srchIdx.end()) {
srchIdx.modify(idx, ModificationFunctor(someNewDataInstance));
}

But if you are the old school, novice programmer that I am, you'd like direct access to the struct DATA, which after all is the only thing you wish to modify. Why can't you just let me have it? Why not?? :(

The answer is to use a const_cast. This is not necessarily the best way to do things, but it works, provided that the DATA you inserted into the pair is never really a constant. The way to do that is as follows:

SearchableAccessIndex& srchIdx = myContainer.get<kIndexSearchable>();
SearchableAccessIndex::iterator idx = srchIndex.find(12);
DATA& data = *(const_cast<DATA*>(&(idx.second)));

and then modify data as usual

data.whatever = whatever;





2 comments:

Xabi said...

There is a third solution to your problem:

Instead of using std::pair you can create your own struct like this:

struct DataPair
{
int key_;
mutable DATA data_;
};

Then the typedef would be:
typedef boost::multi_index::multi_index_container, boost::multi_index::ordered_unique > > DataContainer;

Notice that you have to include the mutable modifier before any member that you plan to modify. And you have to make sure you don't modify values that are indexed without using the replace() or modify() functions, of course.

So the rule is, if the value is not const and not indexed prefix it with mutable :)

Protean said...

That is nicer. Thanks.

Followers

Blog Archive

About me

A soul possessed forever...