Boost logo

Boost :

From: Fernando Cacciola (fernando_cacciola_at_[hidden])
Date: 2003-07-01 10:51:22


Joaquín Mª López Muñoz <joaquin_at_[hidden]> wrote in message
news:3F0129FD.BEB2DD29_at_tid.es...

>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.
>
>

C++ already has the concept of an Associative Container, and this
concept includes that of a 'Key'. In std terms, a 'key' can be
integrated with the value type (ala 'set') or not (ala 'map');
so this particularity shouldn't indicate the need for another term.

I think that following the std associative containers as much
as possible is the way to go.
For example: if possible, having both 'set' and 'map' variants
would be great (that is, with integrated or external keys).
Also, having 'hash' variants would also be great, that is,
with equal_key clustering but no particular ordering.

>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.
>
I see.
I'm pretty sure this can be done, though I'm not sure how exactly :)
Named template parameters mechanisms come to mind.
Perhaps other boosters can suggest something.

>>(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.
>
Wait...
I read your original example as if you were mutating
the element in-place though the iterator,
then calling update().
But you're not, update() takes a _copy_ of the
possibly mutated element, so I figure that
iterators are non-mutable (as should).

OK, I grant this interface is invariant-safe,
but it strikes me as inneficient, not because of
the update per see but because of the element
copy (which has to be done twice)
An alternative would be something like this:

class multiindex {
...
template<class Modifier>
Modifier update ( const_iterator it, Modifier Mod )
{
  // iterator is private, so is access()
  iterator mit = access(it);
  Mod(*it);
  update(*it);
}
...
} ;

Modifier is a user-suplied function object
which signature of the form:

void operator() ( element& e ) ;

One last concern: keys are related hierarchycally?

Fernando Cacciola


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk