Re: [boost] [multi_index] User-defined indices

From: Joaquín Mª López Muñoz (joaquin_at_[hidden])
Date: 2007-06-12 09:33:41

Andrey Semashev ha escrito:
[...]

> But there may be ways of decoupling indices. For example, you may
> implement these final_* functions so they call each index's protected
> function separately. There would be no need to call base class
> recursively in each index and I don't think it's going to make a
> performance impact. This is essentially what I was writing above.
> In addition this might help to encapsulate exception safety burden
> in these final_* functions instead of distributing it in indices.

I thought about this more decoupled approach when first designing the
lib, but it presents serious problems. Let me elaborate: suppose we
implement final_insert_() like this (pseudocode follows):

node_type* final_insert(v)_
{
  node_type* x=allocate_node();
  for(int i=0;i<N;++i){
    if(!index<i>::insert_(v,x)){
      for(int j=i;j--;)index<j>::erase_(x);
      deallocate_node(x);
      return 0;
    }
  }
  x->value()=v;
  return x;
}

This is suboptimal because when a given index bans an insertion we have to
undo all the previous work by calling erase_() on the preceding indices.
We can try to remedy this by writing the code as follows:

node_type* final_insert(v)_
{
  node_type* x=allocate_node();
  for(int i=0;i<N;++i){
    if(!index<i>::can_insert_(v)){
      deallocate_node(x);
      return 0;
    }
  }
  for(int i=0;i<N;++i){
     index<i>::insert_(v,x)){
  }
  x->value()=v;
  return x;
}

But then another problem pops up: the code in can_insert_() performs some
calculations that must be repeated when doing the insertion proper. It'd be
so much better if we can somehow store this info as some sort of local data
that can later be used by insert_()... and the simplest way to do this is
to let the insert_() functions the responsibility to cascade the call by
themselves:

node_type* final_insert(v)_
{
  node_type* x=allocate_node();
  if(!index<0>::insert_(v,x)){
    deallocate_node(x);
    return 0;
  }
  x->value()=v;
  return x;
}

node_type* insert(v,x)_
{
  link_info lnk;
  if(!calculate_link_info(lnk,v)){ // collision
    return 0;
  }
  if(!super::insert_(v,x)_){  // remaining indices
    return 0;
  }
  link(x,lnk); // do the actual linking;
  return x; // ok
}

I don't know if the explanation is clear enough... Basically, there might be
conceptually cleaner ways to implement the backbone functionality of
a multi_index_container, but I doubt they can compare to the current one
in terms of efficiency. The drawback is that writing an index becomes an
admittedly arduous task.

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