On Sun, 08 Aug 2010 17:29:49 -0700, Steven Watanabe <watanabesj@gmail.com> wrote:

AMDG

Mostafa wrote:

...

For the following struct:

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

I want to create a multiindexed container that indexes Flower objects by type, name, and aliases, where aliases is some iteratable collection of strings. I just don't know if it's possible to create a multi-key key-extractor for aliases. So far I've come up with the following:

I assume that you want to be able to look up the Flower from a string, which should be one of the aliases? You can't do this with multi-index.

Yes.

A single object corresponds to a single key.

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 and providing adaptor classes for creating such a Range from multi_index::value_type member variables, methods ..., (basically a key-extractorS counterpart for the equivalent existing key-extractors, where approriate of course). The motivation for this request is that a multi-index element can be indexed by a collection of values associated with that element. As an example: (rehashing from previous posts) struct Flower { int getType() const; string name; std::list<string> aliases; }; struct Nursery { std::list<Flower *> flowers; }; 1) a multi-index of Flower objects each indexed by an alias from Flower::aliases, 2.1) a multi-index of Nursery objects each indexed by an alias from Nursery::flowers.aliases, 2.2) and and also indexed by Nursery::flowers.getType() Does this make sense? Should this be a new post, and if so should it be posted in the dev's group? Thanks, -Mostafa

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); }