Re: [Boost-users] [multi_index] How to iterate by user selected index

From: Joaquín Mª López Muñoz (joaquin_at_[hidden])
Date: 2006-10-03 12:24:25

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