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

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

Fernando Cacciola ha escrito:

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

[...]

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

multiindex_set follows the à la set way. The whole element is the
key. For instance:

struct element{int a;int b;int c;};

struct comp_element{
  bool operator()(const element& e1,const element& e2)const
  {
    return e1.a+e1.b+e2.c<e2.a+e2.b+e2.c;
  }
};

typedef multiindex_set<element,comp_element> mx_set;

Here you can see that the comparison predicate reads from all the
members of element, so basically multiindex_set makes no assumption
(it cannot) about which parts of the element are keys or not. This is
useful for constructing "composite" indices, following database terminology.
less_by is used for comparison predicates depending upon one single
member, but this is not the general case.
So, every index has the same implicit key (the whole element), so calling
the indices "keys" seems to me confusing. An index is just a sorting
criterium. I'm not sure I've explained myself clearly enough (if I haven't
please tell me so). Now the question of how to name the indices
remain open, though maybe this discussion has made you lean towards
my preferences. This is by no means a critical aspect, if someone comes
with a more appropriate name I'll happily adopt it.

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

>From the discussion above, I hope it is clear now that
multiindex_set regards the entire element as the key. A map
variant can be built on top of it, but it is not clear to me
whether such a construct is useful enough. Maybe we can delay
this decision after some stable set-only version is stabilized.
Hashing of user-specified indices is a very good option to have.
I'm currently exploring it, but given the little amount of time I
can devote to this I'd prefer to leave this out for the moment.

[...]

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

If someone else jumps into the thread (s)he may shed some light on this.

[...]

>
>
> 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 ) ;

Ummm... I'm afraid this cannot be done. What happens if the updated
element does not fit into the multiindex_set due to collision with some
other element? For instance:

multiindex_set<int> ms;
ms.insert(0);
ms.insert(1);
ms.update(ms.begin(),increment_by_one);

The last call will call increment_by_one() on the first element with
value 0, changing it to 1. When reordering of  the element is tried,
a collision with the second element will ensue. What's worse, one
cannot revert to the original situation, because the element has been
already rewritten.
At least, I hope current update() is no longer a showstopper for you.

>
>
> One last concern: keys are related hierarchycally?

Only for implementation purposes: derivation from one key
(or index) to another is protected. From the user's point of
view, keys/indices are structurally unrelated types obtained via
get() from the source multiindex_set object.

Just to summarize, the following points remain open:

* How to name "indices" in a more appropriate form.
* Is it worthwile to make a map-like variant? It can be done,
but I'm not sure whether such a construct is any useful before
some practical experience. In the meantime, multiindex_set
can be used as is to simulate map-like structures (the example
provided shows how to implement a bidirectional map).
* Is it possible to make get() accesors parameterized by tags?
* Is it possible to provide an update facility with in-place
updating of elements (I strongly doubt it).

I'd greatly appreciate your interest in examining the library, and
realize the difficulty in doing it without any documentation (which
should follow promptly if finally multiindex_set catches boosters'
eyes).
Regards,

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