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

From: Joaquin M Lopez Munoz (joaquin_at_[hidden])
Date: 2007-06-11 17:00:41

Andrey Semashev <andysem <at> mail.ru> writes:

> 
> Hello JOAQUIN,
> 
> Monday, June 11, 2007, 1:46:53 AM, you wrote:
[...]
> > It is not exactly like that, if I'm understanding your
> > description correctly. Indices do not hold iterators to some
> > base container, which would be the simplest implementation
> > technique, but they're rather much more tightly coupled
> > to each other internally. For instance, a multi_index_container
> > consisting of N indices holds only one node per element --this
> > node is constructed by metaprogrammatically aggregating
> > in one single struct the N headers for each index. The savings
> > achieved by this technique are calculated at
> 
> >   http://boost.org/libs/multi_index/doc/performance.html
> 
> > The inner workings of the indices are also constrained
> > by some internal APIs that must be complied with so that
> > multi_index_containers can assemble and use the indices.
> 
> Ok, this makes things more complicated but still possible. I see that
> the node structure becomes dependant on the index nature and there is
> no longer "ultimate" begin or end of the container which makes it
> difficult to clear or destruct it.
> 
> However, the implementation does not restrict indices from having
> their internal data that helps them to implement their logic. In fact,
> I suspect that random_access and hashed indices use this ability.

Correct, these indices allocate their own supplemental
structures.

> Therefore, if there is:
> 
> - a way to tell the index the complete node type and means to extract
> the container value and index's header form it
> - a way to tell multi_index_container the type of index's header and
> iterators
> - a way to notify the index about modification events (such as insert
> and erase) performed through other indices (at least on per-node
> basis)
> 
> then there is a quite usable basic interface to implement user's
> indices.

The interface is not a passive one like you seem to be describing,
but an active one in which some operations are performed in
an orchestrated manner by all the indices. Allow me to give
a very incomplete description of how indices work internally.
Rouhgly speaking, an index has the following structure:

template<typename Super>
class index_implementation
{
public:
  // public interface
  typedef typename Super::value_type value_type;
  typedef ...                        iterator;
  ...
  iterator begin();
  ...
  iterator find(...)const;
  ...

protected:
  // backbone
  typedef ... node_type;
  ...
  index_implementation(...);
  void copy_(...);
  node_type* insert_(...);
  void erase_(..);
  void swap_(...);
  bool replace_(...);
  ...
};

where Super contains a linear hierarchy of the preceding indices
and index_implementation is supposed to derive from this to
add itself to the chain. The important part is the backbone
protected interface by which all the important "primitive"
operations of the multi_index_container are implemented: for
instance, index_implementation::insert_(...) must do its part
of the insertion operation and then call Super::insert_(...)
so that the remaining indices do the same, etc. The public
member function insert() then resolves to a mere call to this
primitive operation. As you see, the degree of coupling is
very high --this has been done so in order to provide maximal
efficienfy time- and memory-wise.

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