struct index1{};

struct index2{};

template<typename Key1,typename Key2, typename Data>

struct bimultimap

{

  typedef boost::tuple<Key1,Key2,Data> value_type;

  typedef boost::multi_index_container<

    value_type,

    indexed_by<

      ordered_non_unique<

        tag<index1>,member<value_type,Key1,&value_type::first> >,

      ordered_non_unique<

        tag<index2>,member<value_type,Key2,&value_type::second> >

    >

  > bimimap;

};

template<typename Key1, typename Key2, typename Data>

class concurrent_bimultimap

{

private:

    typename bimultimap<Key1, Key2, Data>::bimimap    the_bimultimap;

    mutable boost::mutex     the_mutex;

    boost::condition_variable     the_condition_variable;

public:

typedef typename bimultimap<Key1,Key2,Data>::bimimap bimimapType;

typedef typename bimultimap<Key1,Key2,Data>::bimimap::iterator bimimapIterator;

typedef typename bimultimap<Key1,Key2,Data>::bimimap::index<index2>::type::iterator bimimapIterator2;

void insert(Key1 const& key1, Key2 const& key2, Data const& data)

{

boost::mutex::scoped_lock lock(the_mutex);

the_bimultimap.insert( bimultimap<Key1,Key2,Data>::bimimap::value_type(key1,key2,data) );

lock.unlock();

// Note: because we unlock above and notify below, we can starve the "pop" thread for short durations in burst situations. That's ok so far.

the_condition_variable.notify_one();

}

bool findKey1(Key1& key1, Data& data)

{

boost::mutex::scoped_lock lock(the_mutex);

bimimapIterator itFindIt = the_bimultimap.find(key1);

if (itFindIt != the_bimultimap.end()) {

data = itFindIt->third;

return true;

}

else return false;

}

bool findKey2(Key2& key2, Data& data)

{

boost::mutex::scoped_lock lock(the_mutex);

bimimapIterator2 itFindIt = the_bimultimap.get<index2>().find(key2);

if (itFindIt != the_bimultimap.get<index2>().end()) {

data = itFindIt->third;

return true;

}

else return false;

}

..... there's more but this gives the essence of the problem .... 

};