Re: [boost] [MultiIndex] proposal - delayed index initialisationandmaintenance

From: Joaquín Mª López Muñoz (joaquin_at_[hidden])
Date: 2005-12-16 03:17:37

Hello Neil, excuse my late answering.

Neil Hunt ha escrito:

> I am just sort of throwing this out there as a wild idea.

Many top designs stem from some wild idea :)

> Having a trait on any given index such that it is
> only initialised upon first access.
>
> The motivation being - When displaying a table of rows
> of fields, the user may not
> necessarily click on any given column header
> for sorting, and would only rarely click on
> the majority of column headers. Therefore it
> is not required to maintain any given
> column index unless the user has requested
> sorting by that index.

Lazy indices, right? Leaving implementation complexities aside (this
doesn't look trivial to write efficiently) I wonder whether the motivation
is consistent: if you only need one index at a time, why using a
multi-index container? You can always have a vector and sort it
as needed depending on the column clicked by the user.
An in-between case is when you have several fixed indices (say, those
given the most usage) plus many more that are seldom selected. Even
in this case, lazy indices are just half-way to an optimal solution: even
if you save computing time, there's still a lot of wasted space: nodes
must allocate space for all index headers, regardless of whether the
indices use them right away or lazily.
Thinking out loud, the "some fixed, some dynamic indices" situation
can be handled in a number of ways:
1. Allowing ordered indices to change their (key extractor, comparer)
pair and re-sorting appropriately. This can make an index kind of
multi-column.
2. Using a random access index for supporting the dynamic columns.
The index can be sorted according to the current column. You can
already try this approach, there's a preview of random access
indices in the vault.
3. Dynamic multi-index containers. Sometime in 2006 I plan to
begin studying how to design such a beast, still uncertain about
its feasibility and value.

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