Robot Dreams
Robot Dreams
Thursday, February 23. 2006
Set, Query, Result
First off, a general update. It's been a slow start to the blog, sorry about that. But I'm still recovering from a total drive failure of the machine I do most of my development work from. So it's been a hard slog to reinstall everything, especially that initial Windows install with at least 15 reboots (I was counting them and that's when I gave up). On to the subject at hand...
One of the data structures in C++ I make use of most are the associative standard containers. I use them because of the bounded algorithmic guarantees they provide. But one of the most nagging problems with them is that it is hard to do any meaningful searching once one has arranged to keep the sorted elements. Sure it's easy to find equivalent elements with for example std::set::equal_range. But if how you are sorting is anything but the element itself as a value it's rather painful to come up with the usual convoluted special value elements to do the searching for you. For example having:
struct A
{
int type;
std::string label;
std::string description;
};
struct S
{
bool operator()(
boost::shared_ptr<A> const & a,
boost::shared_ptr<A> const & b ) const
{
return a->type < b->type;
}
};
std::multiset<boost::shared_ptr<A>,S> db;
And wanting to find out how many A's of type #2 there are. So even though the set is arrange in the most optimal way for getting that answer one is thwarted in using the property of the set only because std::multiset::count, and others, don't take anything but the an element.
With the use of some of the Boost libraries one can get around such a limitation. The idea is to replace the elements stored in the set with something more flexible, but still maintain the basic properties and advantages of directly storing the elements. With some freedom in what the elements can be one can tailor the comparison function object to handle any search one might think of, including freestanding call point functions (lambdas).
The reformulation is to use the Boost Variant and Boost Any libraries. The former as the values we store, and the latter as the values we search with. First we change the set itself to store the variant:
typedef boost::variant<boost::shared_ptr<A>,
boost::any> V;
std::multiset<V,S> db;
With that change we can store either the original element pointer, or anything else we want through boost::any instances. Not that we ever will store a boost::any in the set, but having it as a possible value allows us to pass anything into the various set methods that take elements. But this complicates the sorting function we are using a bit as we now need to make sure we do the right thing based on the stored type. Luckily the Boost Variant library already provides a handy utility to minimize the code:
struct S
{
bool operator()( V const & a, V const & b ) const
{
boost::apply_visitor(*this,a,b);
}
bool operator()(
boost::shared_ptr<A> const & a,
boost::shared_ptr<A> const & b ) const
{
return a->type < b->type;
}
};
Now, the fun part. We want to be able to count the number of elements that have the type member as #2. And we can now pass that into the method:
std::cout << "#2 count = " << db.count(boost::any(2));
But to make that work we need to teach our container to interpret that kind of value as the search we want to do. To do this we will need to detect when that boost::any special value is being used and translated it to the int. Luckily the "detection" is what the boost::apply_visitor is already doing above. All we need to do is add extra comparisons for those values:
struct S
{
// The same operators as above, plus:
bool operator()( boost::shared_ptr<A> & a, boost::any const & b ) const
{
return a->type < boost::any_cast<int>(b);
}
bool operator()( boost::any const & a, boost::shared_ptr<A> & b ) const
{
return boost::any_cast<int>(a) < b->type;
}
bool operator()( boost::any const & a, boost::any const & b ) const
{
return boost::any_cast<int>(a) < boost::any_cast<int>(b);
}
};
Technically the last method is not needed but it's good to have for completeness. Now when the count algorithm searches for the range of elements to count it will pass in to the comparison function our special boost::any value in the guise of a boost::variant and the correct comparison gets done. This allows for the perhaps more useful iteration of categorically similar elements:
std::pair<iterator,iterator> toOutput = db.equal_range(boost::any(2));
while ( toOutput.first != toOutput.second )
{
std::cout
<< boost::get< boost::shared_ptr<A> >(*toOutput.first)->label
<< "\n";
++toOutput.first;
}
The above can be generalized further to handle just about any kind of search, as long as it's within the ordering of the container. But I leave that as an exercise for the reader 
