[multi_index] How to iterate by user selected index
Hello, I'm looking for an easy way to iterate over a set by a user selected index. A little example: [code] struct Person { std::string name; std::string city; }; struct city{}; struct name{}; typedef multi_index_container< Person, indexed_by< ordered_unique< tag<name>, member<Person, std::string, &Person::name> >, ordered_non_unique< tag<city>, member<Person, std::string, &Person::city> >
person_set;
typedef Person::index<name>::type Person_by_name; typedef Person::index<city>::type Person_by_city; person_set persons; for(Person_by_name::iterator it = persons.get<name>().begin(); .....) {...} [/code] This for loop is hard-coded to iterate over the set sorted by name. How can I dynamically change the iterator used in this loop to let the user decide the sort criteria? Greetings, René
On 10/3/06, René Haber <rene.haber@freenet.de> wrote:
I'm looking for an easy way to iterate over a set by a user selected index.
(example) How can I dynamically change the iterator used in this loop to let the user
decide the sort criteria?
The loop is resolved at compile time. You will have to use a higher level approach to dynamically choose between the two hard-code loops. Maybe a simple switch is enough in this case. Best regards Matias
René Haber ha escrito:
Hello,
I'm looking for an easy way to iterate over a set by a user selected index. A little example: [code] struct Person { std::string name; std::string city; };
struct city{}; struct name{};
typedef multi_index_container< Person, indexed_by< ordered_unique< tag<name>, member<Person, std::string, &Person::name> >, ordered_non_unique< tag<city>, member<Person, std::string, &Person::city> >
person_set;
typedef Person::index<name>::type Person_by_name; typedef Person::index<city>::type Person_by_city;
person_set persons;
for(Person_by_name::iterator it = persons.get<name>().begin(); .....) {...} [/code]
This for loop is hard-coded to iterate over the set sorted by name. How can I dynamically change the iterator used in this loop to let the user decide the sort criteria?
Hello René, As Matías states on his reply, maybe a simple switch could be enough for your needs. Otherwise, you'll have to devise some kind of dynamic framework that lets you add run-time polymorphism to the multi-index container (which is basically a compile-time construct.) This is simple in principle, but the implementation can be a little cumbersome for those unfamiliar with MPL and so-called type erasure techniques. I've written a small example for your convenience that lets you iterate over any index selected at run time, let me go through the ideas step by step: The first place where dynamic polymorphism must be added is the iterator itself: as the iterator type of index #N is *not* the same as that of index #M, you cannot possibly have a loop that handles both types of iterators uniformly. There is an Adobe open source library called ASL that provides a nice utility called adobe::any_iterator: http://opensource.adobe.com/classadobe_1_1any__iterator.html adobe::any_iterator basically accepts any conforming iterator type object at construction time and wraps it with a polymorphic interface so that code using adobe::any_iterator's can through the provided extra indirection layer actually use iterators of different types --precisely what we want. adobe::any_iterator is conceptually very similar to boost::function, which can effectively hide under the same interface callable objects of entirely different types. So, we use adobe::any_iterator to define: template<typename MultiIndexContainer> struct multi_index_any_iterator { typedef typename adobe::any_iterator< const typename MultiIndexContainer::value_type, std::bidirectional_iterator_tag
type; };
template<typename MultiIndexContainer> struct multi_index_any_iterator_pair { typedef typename multi_index_any_iterator< MultiIndexContainer>::type iterator; typedef std::pair<iterator,iterator> type; }; Now, it is easy to construct a function which, given a compile-time constant N, provides a range function for the index #N of a container using our newly defined multi_index_any_iterator_pair: typedef typename multi_index_any_iterator_pair< MultiIndexContainer>::type iterator_pair; template<int N> static iterator_pair nth_range(const MultiIndexContainer& m) { typedef typename multi_index_any_iterator< MultiIndexContainer>::type iterator; return iterator_pair( iterator(m.template get<N>().begin()), iterator(m.template get<N>().end())); } nth_range is not yet what we want, since the index number must be provided at compile time. We need another polymorphism layer here so that the index number be accepted at run time. One way to do this is to have an array of function pointers like this: typedef iterator_pair (*range_function)(const MultiIndexContainer&); // index_number is s compile-time constant calculated from // MultiIndexContainer typedef range_function range_function_array[index_number]; and somehow have it filled with &nth_range<0>,..., &nth_range<index_number-1>. Using this array, we can dispatch to the appropriate index at run time: range_function_array f; ... iterator_pair range(const MultiIndexContainer& m,int n) { return f[n](m); } All of ths is wrapped up inside a class called any_range_dispatcher (see the attached code): template<typename MultiIndexContainer> class any_range_dispatcher { public: typedef typename multi_index_any_iterator_pair< MultiIndexContainer>::type iterator_pair; iterator_pair operator()(const MultiIndexContainer& m,int n)const; ... }; The part of filling the function array is done at any_range_dispatcher construction time using the MPL utility for_each, see the code for details. Once any_range_dispatcher is set up, or final range function looks like: template<typename MultiIndexContainer> typename multi_index_any_iterator_pair<MultiIndexContainer>::type range(const MultiIndexContainer& m,int n) { static any_range_dispatcher<MultiIndexContainer> d; return d(m,n); } and we can do things like the following: typedef multi_index_container< person, indexed_by< ordered_unique< tag<name>,member<person,std::string,&person::name> >, ordered_non_unique< tag<city>, member<person,std::string,&person::city> > >
person_set;
int main() { person_set ps; ps.insert(person("Leonardo","Vinci")); ps.insert(person("Aristotle","Stagira")); ps.insert(person("Leibniz","Leipzig")); ps.insert(person("Cervantes","Alcala")); std::cout<<"0=name, 1=city: "; int n; std::cin>>n; multi_index_any_iterator_pair<person_set>::type p=range(ps,n); while(p.first!=p.second){ std::cout<<p.first->name<<" of "<<p.first->city<<std::endl; ++p.first; } } When the user enters 0, the output is Aristotle of Stagira Cervantes of Alcala Leibniz of Leipzig Leonardo of Vinci When 1 is entered, the output is Cervantes of Alcala Leibniz of Leipzig Aristotle of Stagira Leonardo of Vinci The attached example works for GCC 3.2, I hope you won't have problems trying it in any modern compiler. You've got to download ASL (for adobe::any_iterator) to compile it. I don't know if this scaffolding is too much for your needs, in case you like it and want to go deeper into metaprogramming and techniques for adding runtime polymorphism, you'll find plenty of material in Abrahams and Gurtovoy "C++ Template Metaprogramming": http://boost-consulting.com/mplbook/ HTH, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
participants (3)
-
Joaquín Mª López Muñoz
-
Matias Capeletto
-
René Haber