[Boost-users] [containers] defining the insertion point of non-unique keys

Subject: [Boost-users] [containers] defining the insertion point of non-unique keys
From: Olaf Krzikalla (olaf.krzikalla_at_[hidden])
Date: 2009-12-17 11:08:40

Hi @boost,

I'm looking for the solution to the following problem:
there is a collection of objects and I want to find a particular object 
by two different keys. The first key is unique, so there is no problem. 
The second key however is non-unique and if I search for an object using 
this key I want to find the element that was inserted last in that 
sequence. Neither boost::multindex nor boost:intrusive seems to have 
solutions right at hand. If using boost::multindex I could try to insert 
  a new element in the non-unique sequence using the lower_bound 
iterator of that sequence as a hint. However it is not documented that 
in that case the element is always inserted before the hint. Same is 
true for
boost:intrusive::multi_set/multi_map. And I'm not able to swap the 
position of two adjacent elements in a multi_set or multi_map, if they 
have equal keys.
To illustrate the problem, here is some code:

struct A
{
   int   a;  // non-unique key
   void* b;  // unique key
   // stuff
};

using namespace boost::multi_index;
typedef multi_index_container<A,
   indexed_by<
     ordered_non_unique<member<A,int,&A::a> >,
     ordered_unique<member<A,void*,&A::b> > > > tCollection;

void foo(tCollection& collection, int key)
{
   typedef tCollection::nth_index<0>::type tItByInt;
   tItByInt i = collection.get<0>().lower_bound(key);

   // use the current lower bound as a hint:
   tItByInt insertPos = collection.get<0>.insert(i, getObject(key));

   // the big question: does the assertion holds?
   assert(collection.get<0>().lower_bound(key) == insertPos);
}

Best regards
Olaf Krzikalla