[boost] [In response to Arkadiy] Re: Interest in multiindex_set? (again)

From: Joaquín Mª López Muñoz (joaquin_at_[hidden])
Date: 2003-07-01 04:35:07

(My mail server was down yesterday so your post didn't
get through to me and I cannot answer it properly).

Arkadiy wrote:
>We may use this to provide a better table implementation for the
Relational
>Template Library, we are currently working on.
>
>Right now we are using a sorted vector instead of a set, to implement
our
>relational tables, because set doesn't allow us to search on a prefix
of a
>key.  Like if a table is indexed on a, b, c, we are not able to use
>equal_range on a, b with the set.  Sorted vector allows us to do this,
but
>sorted vector has obvious problems with inserts/deletes.
>
>Do you think your library can provide both search on a key prefix and
fast
>inserts/deletes?
>
>Arkadiy

Search methods are extended to allow for compatible comparison
predicates.
If if understood your request right, having a multiindex_set sorted by
lexicographical order on (a,b,c) allows the user to perform searches
based on lexicographical (a,b), since this order is compatible (weaker)
than
the former.

Insertions are O(M log N) where N is the length of the set and M the
number
of indices it is instantiated with. Deletions are constant time --O(M),
to be precise.

Regards,

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