Re: [Boost-users] multi_index library, dynamic number of indices

From: JOAQUIN LOPEZ MU?Z (joaquin_at_[hidden])
Date: 2006-09-13 17:59:55

Adán Cosgaya ha escrito:
> Hi, I am using multi_index to keep a set of d-dimensional
> points, where each point is a vector inside the multi_index
> container. e.g (3,5,8,9,5) is a 5-dimensional point (but
> this can vary and be 3-d, 7-d, etc..). I need to have the
> set sorted by each of the dimensions.
> 
> I can do it statically if I know in advance how many
> dimensions I have, but I don't know how to make dynamic to
> any number of dimensions. 
> 
> I currently have:
> 
>  template<int N>
>  struct nth_coordinate
>  {
>    typedef int result_type;
> 
>    int operator()(const vector<int>& x)const
>    {
>      return x[N]; 
>    }
>  };
> 
>  typedef multi_index_container<
>    vector<int>,
>    indexed_by<
>      sequenced<>,
>      ordered_non_unique<nth_coordinate<0> >,
>      ordered_non_unique<nth_coordinate<1> >, 
>      ordered_non_unique<nth_coordinate<2> >,
>      ordered_non_unique<nth_coordinate<3> >,
>      ordered_non_unique<nth_coordinate<4> >
>    >
>  > multi_index_Points;
> 
> is it possible do it without explicitly saying how many
> indices do I need?

Well, the short answer is no, you can't: multi_index_container
is a compile-time construct, you cannot delay the specification
to run time. That said, you can sort of have a kind of
rudimentary dynamicity if you know the maximum number of
coordinates and don't mind wasting memory and cpu cycles
for those cases where the number of coordinates is less:
rewrite nth_coordinate so as to not incur out of bounds
accesses:

 template<int N>
 struct nth_coordinate
 {
   typedef int result_type;

   int operator()(const vector<int>& x)const
   {
     if(x.size()>N)return x[N];
     else          return 0; 
   }
 };

and add as many indices to multi_index_Points as the
maximum number of coordinates you know you're going
to handle.
 
> Also, I am trying to create a function which receives as a
> parameter the dimension I want to work with, but it seems that
> I need to explicitly say the number of the index in nth_index
> (it obviously needs a constant). For example: 
> 
> int median (int d){
>  ...
>     typedef multi_index_Points::nth_index< d >::type 
multi_index_Points_it;    ===> I would like to pass "d" as a parameter 
>    ...
> }
> 
> is there any workaround for this issues? 

Well, you're experiencing a typical clash between compile-time
(or static) and run-time (or dynamic) polymorphisn. In the
particular case of your median function, what you propose cannot
work as is because multi_index_Points_it would be of a *different*
type for each d!
There are some techniques to bridge the static and dynamic
worlds, all of them involving some sort of "type erasure", i.e.
absorbing several different types into one polymorphic proxy
type. The following is a possible realization of a dynamic
median facility:

class compile_time_median_table
{
private:
  template<int D>
  static int compile_time_median()
  {
    typedef typename multi_index_Points::
      nth_index<D>::type multi_index_Points_it;
    ...
  }

  std::map<int,int (*)()> m;

public:
  compile_time_median_table()
  {
    m[0]=compile_time_median<0>;
    ...
    m[6]=compile_time_median<6>;
  }

  int operator()(int d)
  {
    return m[d]();
  }
};

int median(int d)
{
  static compile_time_median_table t;
  return t(d);
}

Here, we perform the type erasure by storing a pointer
to every different instantiation of compile_time_median<D>
and using those within a proxy function int median(int)
which provides the illusion of runtime polymorphism.
Maybe this sort of approach does suit your needs.

Best regards,

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