Re: [boost] Re: Interest in multiindex_set?(again)

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

Beman Dawes ha escrito:

[...]

> I'm more interested in the class name than the namespace name. One problem
> at a time. If you weren't worrying about the namespace name, would you then
> like indexed_set as the class name? What are some other alternatives?

If we forget about the namespace name, then I have no objections against
indexed_set (though std::sets are indexed by nature, but this is probably not
a common perception between users).
I thought long and hard about name candidates and come up with none except
multiindex_set.
If no one says anything against it, I'll change it to indexed_set. The problem
remains
of how to name its associated namespace.

[...]

>
> Yes, I think so. It is a bit of a judgement call, but since the library is
> a very general purpose tool, and assuming the library only adds a few names
> to the namespace it lives in, I'd rather see it in namespace boost. Others
> may disagree; a lot of people like tall and deep namespace hierarchies even
> when the components are very general purpose.

OK, next installment will have the container promoted to boost::indexed_set.
There are some auxiliary classes which I don't know exactly where to put, I'll
think it over.

> I don't see any acceptable (non-invasive) way to implement marking only one
> class. But the unique/non_unique two template approach seems perfectly
> acceptable. You could even argue that it forces the user to consciously
> make  the critical unique/non_unique decision for each index, so may reduce
> user error.

I agree with you. The all-predicates-are-marked approach is even better in the
light
of future change (I plan to add hash indices sometime by the end of 2003).

[...]

>
> I understand the rationale for that, but am still concerned. There are many
> applications where the cost of a copy to apply a minor update is
> prohibitive. The user is then forced to add a layer of indirection, or use
> a home-made container. Ugh. This is one of the few cases I run into where a
> safe design is so inefficient compared to a traditional unsafe design that
> in real production code I might be forced to use the unsafe design. That
> makes me uncomfortable.

I don't think it is a question of how smartly update() is coded, but an
actual conceptual impossibility. If we are to provide strong exception-safety,
then no fail or throw is permitted after the element has changed its value.
So, there are three scenarios:

1. Updating can possibly fail (because of collision with some other element) or

reorder the updated element: no other soluction but to incur a copy of the
element, as the actual updating has to take place *after* the reordering is
done.
2. Updating won't fail (because the progammer knows it) but can result in
reordering. Here a no-throw update is possible that doesn't require an
additional copy.
3. Updating does not alter the order of the updated element (because the
programmer knows it). One can just change the value in-place and forget
about it.

1 is taken care of by current multiindex_set::update. 3 can be solved with
appropriate const_casting: this is dangerous as any cast is, but then again
the programmer *knows* what she's doing. Furthermore, this is exactly
the same situation as in std::set. We are left with 2: please note that
it is extremely error-prone to trust the programmer in her implicit knowing
that no collision will happen (checking 3, on the other hand, is much
easier, as probably what the programmer is changing are auxiliary members
that no comparison predicate depend on). Now, if the no-collision
guarantee is assumed, the updating can be performed without throwing.

To sum it up, as it stands now mutiindex_set allows for updating in
scenarios 1 and 3. Scenario 2 (programmer knows the updated element
won't clash with some other element) can be realized (Fernando suggested
a nice way to do it), but my opinion is that this facility would be extremely
dangerous to handle. I'd rather leave things as they are now, but I'm
open to suggestions, maybe I'm missing something obvious that will solve
the whole problem in a fell swoop.

Open issues:

* Name will change to indexed_set if no one complains. What name to
use for the associated namespace?
* Is it advisable to provide an no-copy update facility relying on the
assumption that updating won't clash with other elements in the set?

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