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

From: Joaquín Mª López Muñoz (joaquin_at_[hidden])
Date: 2003-07-09 02:19:58

Jeremy Maitin-Shepard ha escrito:

[...]

>
> How about indexed_table?  This container is *not* a set, since there can
> be duplicates, but it *does* resemble a relational database table.
>
> Then it can be defined in namespace boost::table, and additionally
> promoted to namespace boost.

Seems good to me, it'd be great to know others' opinion.

[...]

>
> Actually, using partial specialization, you can avoid re-specifying the
> default/unique.  multiple would possibly be a better name than
> non_unique.  Additionally, I would recommend allowing a specification of
> the default "uniqueness" of the indices.

Seems good too :) I think I got an idea of how to implement this, I'll put
myself to work on it.

>
>
>  > (I plan to add hash indices sometime by the end of 2003).
>
> A policy-based approach seems the best way to support different types of
> indices.  Currently, I am working on a policy-based equivalent to this
> class which will support an "ordered" (binary search tree-based) index
> and an "unordered" (hash-table-based) index, as well as any user-defined
> index policies (which would allow a different hash table or tree
> implementation).  This should be completed within a week or two.
>

Do you intend to submit that to Boost? If so, then there's some collision
between the two libraries, maybe we can cooperate somehow. If not, maybe
you can lend some ideas to (re-baptised) indexed_table. Please drop me a
mail if you feel like discussing this.

>
>  > 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.
>
> It seems the best behavior in the case of a collision is to delete the
> old element with which there is a collision.  This would be consistent
> with the semantics of insert.

This is a no-no policy. Collision can happen with more than one element.
Following this approach could result in an single update sweeping off
half the elements of the container :) I don't think users of the library want
this.
I think current update() has some value as it is now. I keep discussing
the alternate memfun modify you propose below.

>
>
> Instead of an update method, a modify method that takes an iterator and
> a one-argument (a reference to value_type) functor which it executes on
> the value to which the iterator points.  Combined with boost.lambda and
> boost.bind, this system can be very convenient.

This is similar to what Fernando Cacciola proposed some days ago.

>
>
> In the case that the modification functor (or copy constructor, in the
> case of the existing update method) throws an exception, the semantics
> could be one of the following:
>
> 1. The container is left in an undefined state, and the exception is
> propogated to the caller.
>
> 2. The exception is caught, reordering is attempted; if an exception is
> thrown while reordering, by one of the comparison, etc. functors, the
> container is left in an undefined state and the exception is propogated
> to the caller; if reordering succeeds, the original exception thrown the
> by modification functor is rethrown to the caller.  Thus, in either case
> an exception is propogated to the caller, and by the type of the
> exception whether the container is in an undefined state.
>
> 3. Same as (2), except that in the case that the reordering filas,
> before the exception thrown by a comparison function is propogated to
> the caller, the would-be-modified element is erased from the container,
> leaving it in a well-defined state.  The exception thrown by the
> comparison function is still propogated to the user.
>
> (3) seems like the most desirable solution, thus that is the behavior I
> would recommend.

I think the analysis is not precise enough. In the modify approach you're
proposing, modifying (by way of the user-provided functor) takes place *before
anything*. If this functor throws, we got nothing else to do but let the exception

propagate. It is the responsibility of the user to guarantee that the modyfing
functor does not leave things in a bad state.
An acceptable (IMHO) approach for modify would be as follows:

a. Call the user-provided modifying functor. If it throws, let the exception
propagate.
b. Attempt reordering.
    b1. If there's a collision, delete the modified element (this can be done in
        a no-throw way) and return false
    b2. If there's an exception (by some comparison predicate), delete the
modified
        element and rethrow.

What dou you think about it?

[...]

>
>  > 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.
>
> A non-const iterator should be provided. (I believe this is what has
> been proposed for std::set)  Requiring that const_cast is used to obtain
> a non-const value from an iterator seems like too strong a warning.  In
> the case where the key for an index (assuming you separate key
> extraction from key comparison as has been recommended) is a particular
> member of the value, it is often rather obvious whether a particular
> operation will or will not modify the key.

I'm strongly against key extraction: it complicates the instantiation of the
container, has no apparent (to me) usefulness and bans the use of composite
indices. Single-member indices are well served by the less_by utility.
Maybe someone can say something in favor of key extraction: otherwise,
it won't get in.

As for the non-const iterator, I don't really know what the status of this
proposal for std::set is (can someone provide some pointer to info?)
My feeling is that if modify is finally provided, its computational cost in
case 3 is acceptable (it adds 2N comparisons where N is the number of
indices). So I wouldn't pursue the non-const iterator approach  (and as
always you can resort to const_casting).

So my proposal by now with respect to the updating stuff is as follows:

1. Leave update() as it is as a well-defined updating mechanism when
copy cost is not a concern, and for entry-level users.
2. Provide a modify (should be call it internal_update?) facility that
does not have the copy penalty but can result in the to-be-modified
element being erased when collisions or exceptions happen.
3. As ever, users can const_cast elements away and play at their own
risk, just as in std::set.

Comments?

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