Boost logo

Boost Users :

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


Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net