Multiple keys in same index for same value in multi_index

[Aaron Moss <moss.aaron@…>]

I have a collection of data objects analogous to this one:

struct foo {
  bar b;
  std::set<baz> s;
  quux q;
};

which I want to be able to efficiently search either by b, or any element of s (q is extra information). The natural way to do that would be some sort of multi_index-like container, where I have a hash-map of bar to foo (with one key per value), and another hash-map of baz to foo (with multiple keys mapping to the same foo).

I may be mistaken, but I don't believe the second map can be set up (efficiently, in its obvious implementation) in the current multi_index. However, if it is allowable to have different sizes for different views of the same collection / different numbers of keys of the same index mapping to the same value, it would perhaps be a useful capability.

Without looking at the Boost sources, this would probably involve generalizing key extractors to support multiple keys from the same value, with syntax looking something like the following:

typedef multi_index_container<
  foo,
  indexed_by<
    hashed_unique<
      member<foo, bar, &foo::b>
    >,
    hashed_unique<
      member_collection<foo, std::set<baz>::iterator, &foo::s.begin, &foo::s.end>
    >
  >
> my_map;

[Joaquín M López Muñoz]

Hi Aaron,

The idea you propose is in direct contradiction with many basic assumptions about the kind of data structures Boost.MultiIndex is designed to generate: for one, all indices have the same size(), meaning that a particular element appears once and exactly once in each index. Breaking these basic assumption subvert the whole internal infrastucture of the library, and it is not easy to see how this could be done in a conceptually sound manner. In other words, I don't plan to augment Boost.MultiIndex the way you propose.

You can approximate your scenario with some manual work: instead of storing plain foos use some kind of proxy like

struct foo_proxy
{
  boost::shared_ptr<foo> p;
  boost::function<const baz&(const foo&)> key;
};

where p points to the actual element and key is a key extractor settable at run time. Then, for each element x insert as many proxys as elements has its s member, setting for each the appropriate key extractor returning the i-th element of x.s. A collateral effect is that indices other than the used for s will contain duplicates as well.