Hi Dave ----- Mensaje original ----- De: "David B. Held" <dheld@codelogicconsulting.com> Fecha: Lunes, Marzo 29, 2004 9:57 pm Asunto: [boost] Re: IndexedSet Review

"Joaquín Mª López Muñoz" <joaquin@tid.es> wrote in message news:406802F9.4990B35C@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