Re: [Boost-users] [MultiIndex] is it possible to create multi-key key-extractors?

Subject: Re: [Boost-users] [MultiIndex] is it possible to create multi-key key-extractors?
From: joaquin_at_[hidden]
Date: 2010-08-09 07:51:49

Steven Watanabe escribió:
> AMDG
>
> Mostafa wrote:
>   
>> That's pretty much what I figured from the documentation, I was just 
>> hoping for some kind of workaround that I might have missed.
>>
>> Well, here goes a feature request ... (A rough outline.)
>>
>> I propose adding a key-extractorS concept to the multi-index library. 
>> Something along the lines of the existing key-extractor concept, 
>> modified such that
>>
>> key_extractorS::result_type is a Boost.Range of keys
>>     
>
> Sorry, but I don't think that this can be implemented
> in a way that is consistent with the rest of the library.
> You'd be better off using an auxillary map of pointers.
> No implementation that I can think of is going to be
> more efficient than that, anyway.
>   

Adding to Steven's answer, you'll need to somehow maintain additional data
structures to do what you want. As each element has one and only one key
per (key-based) index, you need an extra level of indirection that maps
all the aliases into a single value that can act as the key. A possible 
way to
do this is by using a "multi-key bag" (for want of a better name) that you
can feed with lists of keys to obtain a representative token of the list in
return (a N-to-1 bimap, really). Something like this:

  template<typename Key>
  class multi_key_bag
  {
  public:
    typedef Key         key_type;
    typedef std::size_t token_type;

    static const token_type not_found=static_cast<token_type>(-1);

    multi_key_bag():next_token(0){}

    template<typename ForwardIterator>
    token_type insert(ForwardIterator first,ForwardIterator last)
    {
      if(first==last)return not_found;

      token_type token=find(*first);
      if(token!=not_found)return token;

      token=++next_token;
      while(first!=last)cont.insert(value_type(*first++,token));
      return token;
    };

    token_type find(const key_type& k)const
    {
      container::iterator it=cont.find(k);
      if(it!=cont.end())return it->token;
      else              return not_found;
    }

    void erase(const key_type& k)
    {
      token_type token=find(k);
      if(token==not_found)return;

      cont.template get<1>().erase(token);
    }

  private:
    struct value_type
    {
      value_type(const key_type& k,token_type t):key(k),token(t){}
      key_type   key;
      token_type token;
    };
    typedef multi_index_container<
      value_type,
      indexed_by<
        hashed_unique<member<value_type,key_type,&value_type::key> >,
        hashed_non_unique<member<value_type,token_type,&value_type::token> >
      >
    > container;
    container  cont;
    token_type next_token;
  };

The semantics of multi_key_bag is simple: you insert N keys and obtain a
token in return to be used as the representative key; each of the N keys
can be used in isolation to retrieve that same token; erasing a key 
automatically
erases the other associated key as well.

Now, a suitable key extractor would have to be provided with a reference
to a multi-key bag so as to do its job:

  struct FlowerMultiKeyExtractor
  {
    typedef multi_key_bag<std::string> MultiKeyBag;
    typedef MultiKeyBag::token_type    result_type;

    FlowerMultiKeyExtractor(MultiKeyBag& bag):pbag(&bag){}

    result_type operator()(const Flower& f)const
    {
      if(f.aliases.empty())return MultiKeyBag::not_found;
      return pbag->find(*(f.aliases.begin()));
    }

  private:
    MultiKeyBag* pbag;
  };

And that's it: the ugly part is that you need to manually maintain a
multi-key bag in sync with your main container. I've attached a complete 
demo
program. Beware: the mechanism by which the tokens are generated is rather
frail (an incrementing counter) since it'll provide duplicate tokens if 
you do a lot
of insertions (i.e., when the counter wraps around). A more robust
implementation is left as an exercise to you.

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo


#include <boost/multi_index_container.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/member.hpp>

using namespace boost::multi_index;

template<typename Key>
class multi_key_bag
{
public:
  typedef Key         key_type;
  typedef std::size_t token_type;

  static const token_type not_found=static_cast<token_type>(-1);

  multi_key_bag():next_token(0){}

  template<typename ForwardIterator>
  token_type insert(ForwardIterator first,ForwardIterator last)
  {
    if(first==last)return not_found;

    token_type token=find(*first);
    if(token!=not_found)return token;

    token=++next_token;
    while(first!=last)cont.insert(value_type(*first++,token));
    return token;
  };

  token_type find(const key_type& k)const
  {
    container::iterator it=cont.find(k);
    if(it!=cont.end())return it->token;
    else              return not_found;
  }

  void erase(const key_type& k)
  {
    token_type token=find(k);
    if(token==not_found)return;

    cont.template get<1>().erase(token);
  }

private:
  struct value_type
  {
    value_type(const key_type& k,token_type t):key(k),token(t){}
    key_type   key;
    token_type token;
  };
  typedef multi_index_container<
    value_type,
    indexed_by<
      hashed_unique<member<value_type,key_type,&value_type::key> >,
      hashed_non_unique<member<value_type,token_type,&value_type::token> >
    >
  > container;
  container  cont;
  token_type next_token;
};

#include <boost/assign/list_of.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <list>
#include <string>
#include <cassert>

using namespace boost::assign;

struct Flower
{
   std::list<std::string> aliases;
};

struct FlowerMultiKeyExtractor
{
  typedef multi_key_bag<std::string> MultiKeyBag;
  typedef MultiKeyBag::token_type    result_type;

  FlowerMultiKeyExtractor(MultiKeyBag& bag):pbag(&bag){}

  result_type operator()(const Flower& f)const
  {
    if(f.aliases.empty())return MultiKeyBag::not_found;
    return pbag->find(*(f.aliases.begin()));
  }

private:
  MultiKeyBag* pbag;
};

typedef boost::multi_index_container<
  Flower,
  indexed_by<
    ordered_unique<FlowerMultiKeyExtractor>
  >
> FlowerMngr;

int main()
{
  FlowerMultiKeyExtractor::MultiKeyBag bag;
  FlowerMultiKeyExtractor              ext((bag));
  FlowerMngr mgr(
    FlowerMngr::ctor_args_list(boost::make_tuple(ext)));

  Flower f0;
  f0.aliases=list_of("rose")("alba")("gallica");
  bag.insert(f0.aliases.begin(),f0.aliases.end());
  mgr.insert(f0);

  Flower f1;
  f1.aliases=list_of("narcissus")("daffodil")("jonquil");
  bag.insert(f1.aliases.begin(),f1.aliases.end());
  mgr.insert(f1);

  assert(*(mgr.find(bag.find("rose"))->aliases.begin())=="rose");
  assert(*(mgr.find(bag.find("alba"))->aliases.begin())=="rose");
  assert(*(mgr.find(bag.find("jonquil"))->aliases.begin())=="narcissus");
  assert(bag.find("daisy")==FlowerMultiKeyExtractor::MultiKeyBag::not_found);

  mgr.erase(bag.find("jonquil"));
  bag.erase("jonquil");
  assert(bag.find("narcissus")==FlowerMultiKeyExtractor::MultiKeyBag::not_found);
}