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

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

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

Fernando wrote:

>This looks fine in general.
>I've needed something like it so I'm intereseted on seeing this on
boost.

>Some issues:

>(1)
>Why 'index' instead of 'key'? Associative containers use the term key
>instead of index,
>since index is typically related with random access instead of look up
>access.

Well, 'index' is borrowed from database technology meaning an internal
sorting on a given key of a record. I haven't used 'key' instead
because,
in general, the whole element serves as a key (the comparison predicate
for a given index need not be based on a particular member of the
element,
but can be any functor with bool operator(const element&,const element&)

signature; less_by is just a convenient facility for the usual case in
which the
comparison depends solely on a single member of the element.
Also, as every index has a std::set-like interface, its key_type typedef
must
be equal to the type of the elements contained, which contributes to the

confusion.
On earlier versions, I used 'view' instead of 'index', but I don't like
that
either. I'm open to suggestions on more convenient terminology.

>(2)  I would explore a friendlier interface. For instance:

>(2.1)  key uniqueness could be specified along with the key itself
>        and not with a separate template parameter.

Do you have an idea of how the interface can be like? I could try this
approach.

>(2.2) keys could be tagged so that 'get' could be parametrized by
>        key tag instead of number.

I'd do it if I only knew how. Basically I'm using the same technique
as get() member functions in boost::tuple, which don't have tags
either. I really don't know how this could be done.

>(3) This is a showstopper for me: The key mutating operations should
>use a higher level interface which protects clustering and ordering
>invariants.
>With the current interface, if I understood correctly, I could forget
to
>call update() which would break such invariants.
>A better setup would be to use something along the lines of
>the 'modifiers' used by the CGAL Library.
[stuff deleted]

Maybe I'm not explaining myself clearly enough, or else I'm not catching

your point. update() does not break the integrity of multiindex_set.
Semantically,

update(it,new_element)

is equivalent to the following:

element original=*it;
erase(it);
if(!insert(new_element).second) insert(original);

with the added guarantees that:
* strong exception-safety (all-or-nothing operation) is provided.
* the process is done optimally (constant time if no internal reordering
is
necessary)
* iterator and reference validity is preserved (an iterator pointing to
the
original element will point to the new one after update() ).

This does satisfy your concerns? If it doesn't I'd appreciate if
you could explain a little further what you have in mind.

Regards,

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