Re: [boost] Re: IndexedSet Review

From: JOAQUIN LOPEZ MU?Z (joaquin_at_[hidden])
Date: 2004-03-29 16:07:42

Hi Dave

----- Mensaje original -----
De: "David B. Held" <dheld_at_[hidden]>
Fecha: Lunes, Marzo 29, 2004 9:57 pm
Asunto: [boost] Re: IndexedSet Review

> "Joaquín Mª López Muñoz" <joaquin_at_[hidden]> wrote in message
> news:406802F9.4990B35C_at_tid.es...
> > [...]
> > Ummm... If I followed your approach I would be incurring two
> > extra copies which is precisely what modify() is meant to avoid.
> > For non-destructive updating you can use update(), that's the
> > idea. If I'm not making myself clear please tell me so.
> 
> Yeah, I'm not understanding where the extra copies would come
> from.  As far as I can tell, it's possible to reorder the operations
> in modify() without increasing the cost of execution except by a
> few instructions.  This is my understanding of how modify() works
> now:
> 
> mod(element); // changes the element immediately and in-place
> unlink(element); // takes the node out of the index
> link2(element); // puts it back in at the correct spot

Sort of, yes.

> 
> This is what I'm suggesting:
> 
> i = find(new_element); // look to see if modify() can even succeed
> if (*i == new_element) return;
> mod(element); // now change the node, since modify() will succeed
> unlike(element); // same as before
> link2(element, i); // reinsert, but use i as a hint (which will be 
> correct)

OK, I know now where you're getting at. You are assumming
that a change in the name key won't affect other indices.
In general, this is not true: keys are not orthogonal,
the simplest example is two indices having the same key.
More interesting examples include indices with composite
keys or, in general, any function that depends on the
whole element rather than a single data member.
OK so far? So, you just cannot feed an index with the
new key and expect the other indices to remain unaltered.
You *must* provide the indices with the final modified
object. From this it easily follows that you need two
copies: one from the original element to the modified
one (which you must supply separately from the original)
and other to do the final commit. If you look at the
implementation of modify_ (the internal backbone
of modify) you'll see that each index is given its turn
to rearrange the element, not only the one from which
you called modify.

This is the reason behind the existence of different
update and modify memfuns: there's a tradeoff between
copying penalty and reversible semantics.

Got it? Allow me to snip the rest of the discussion.
If you're not convinced or I haven't explained myself
please tell me so.

[...]

> 
> > [...]
> > > Some of the lines are > 80 columns (e.g.: the copyright notice).
> >
> > Is this strictly required? If so I'll go thru the code and make the
> > changes. If not, I'd rather leave it like that.
> 
> I don't think it's strictly required, but a lot of people complain
> about long lines.

Reluctantly added to my todo list (I'm lazy.)

> 
> > <off topic> It'd be nice if Boost.Config provided a (possibly
> > automatically generated) reference table showing which
> > compilers do have a specific defect macro.</off topic>
> 
> That would be great, but as with many things, complaints are
> usually satisfied by the complainer. ;)
> 

Oh, I'm too young for commitment :)

[...]
> > Well, I stated previously that I'll do what people agree on. I don't
> > know if the final decision should be made by Pavel as the review
> > manager.  IMHO, qualified identifiers will be so long anyway that
> > having an additional ::container:: won't hurt much.
> 
> It won't hurt, but if it won't help, why should it be there?  We 
> can add
> gratuitous namespace levels all day long, but that doesn't mean
> we should.

Others (not talking about me) think differently.

> 
> > [...]
> > The main problem with "Set" slipping into the name of the
> > container is that, for instance, the following
> >
> > indexed_set<int,index_list<sequenced<> > >
> >
> > does not have anything to do with sets (it resembles a std::list of
> > constant ints.) For this reason I like Multicontainer better (or
> > something along this line.)
> 
> Perhaps, but "multicontainer" sounds *too* generic.  I would expect
> something with that name to support any number of back-ends, like
> vector, deque, etc.  Actually, come to think of it, that might not be
> such a bad idea.  However, it wouldn't really fit the implementation
> of the library, because the container is a node-based one, and
> vector wouldn't play as nicely as the others.  But if you could not
> only created computed indices, but also *virtual indices*, then you
> could create an associative vector!  However, this might exceed
> the scope of the library.  By a virtual index, I mean that the vector
> itself would remain sorted, and you would have an index that
> performs a binary search without actually storing any additional
> node information.  That sounds like a big mess, though.

I don't think I'll go down that route. As you point out,
the container delivers for node based structures.

> 
> The reason I think that "Set" is ok is that the STL "Set" is only
> vaguely related to mathematical sets.  The only property of
> essence that is related to mathematical sets is the uniqueness
> property, and even that is violated by the multiset.  The vagarities
> of computational performance necessitate that the STL notion
> of Set be stricter than the mathematical notion for it to be usable.
> In the same way, I think that IndexedSet need not strictly be even
> an STL Set for similar reasons.  It supports the "essential
> properties" of uniqueness and intrinsic ordering, and adds
> additional concepts which cater to computational practicalities.
> It's not *merely* a container, but a special kind of container.  It's
> not truly a generic container, so I think it would benefit from a
> more specific name.  It's primarily associative, and that's the
> essence of the STL Set, which is why I think your container
> ultimately *is* a set, even though a degenerate configuration
> may not be.

Then again, not even the general feel of a std::set
has to be met. Imagine a bunch of sequenced indices
(like a lot of std::list without duplicate storage): this
is not just a degenerate case (it might be useful) and
it is definitely not a set.

I agree "Multi" is probably too generic, and clashes
with, for instace, multi_array. What about
CompositeContainer for the lib (and composite_container
for the class)? it matches the name of the concept it
satisfies, it *is* some sort of container and it's
certainly composite. Admittedly a bimap could be also
a considered a composite container, but
composite_container is *the* composite container,
if you know what I mean.

Please allow me to answer the rest of your post
in a separate message so as to keep its size bounded.

Best,

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