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

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

Jeremy Maitin-Shepard ha escrito:

> Joaquín Mª López Muñoz wrote:
>
>  >
>  > 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.
>
> What are the current semantics of your insert?  In order to be
> consistent with std::map, the behavior has to be to overwrite (delete)
> an existing element with the same key.  The number of elements deleted
> by an insert or modify or update operation under the semantics I suggest
> is at most the number of unique indices.  These are the semantics I
> would expect anyway, although I suppose it is a matter of opinion.

The semantics of std::map (or any other STL associative container) are
not overwriting on insertion: instead, if an equivalent element is found, no
insertion occurs. This is what my library does, too. Maybe you're confusing
here map::operator[] with map::insert.

>
>
>  > 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.
>
> Okay, now that I reconsider, this seems most consistent with standard
> containers, since it follows the idiom of "exception thrown means
> nothing happened."
>
>  > 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
>
> I still think it is better to delete the older elements rather than the
> new one, consistent with my proposed semantics for insert (and
> consistent with standard container insert).

same comment about insertion semantics as above.

>
>
>  >     b2. If there's an exception (by some comparison predicate),
> delete the
>  > modified
>  >         element and rethrow.
>
> Okay, this seems reasonable, and would be consistent with insert.

So, to sum it up, if we both agree that insertion will not overwrite (as
it is the semantics of STL assoc. containers), then is this approach
for modify OK with you?

I've included the new memfun modify following your indications and those
of Fernando, and it works right. It'll go in next release, which I hope it'll be
submitted for preformal review.

[...]

>
> There are various advantages to separating key extraction from key
> comparison:
>
> 1) It allows the use of more generic key extraction and key comparison
> functors.  Specifically, for an ordered index, the key comparison
> function in many cases would be std::less<KeyType>, and can default to
> that.  For "unordered" (hash-table-like) indices, it is necessary, at
> least internally, to separate key comparison and key extraction because
> the hash function must also operate on the "key" value; otherwise, the
> hash function must also be very specialized, when in many cases a
> default library-provided hash function can be used (and thus not specified).

A small utility class named less_by is used for precisely this purpose. You can
see it in action in the example accompanying the library. As for hashing, an
analogous device can be written (when hashes get included).

>
>
> 2) It is necessary in order to support certain convenient interfaces;
> specifically, I think it is very convenient to allow the syntax:
> table[key], find(key), and equal_range(key).  In order for the front-end
> to deteremine which index corresponds to the key type, it must "know"
> about keys.

find(key) and related search memfuns are already supported in the way
you suggest! Look for "special lookup operations" in the documentation.
Matter of fact, the operations provided are even more powerful in that
they allow for alternative arguments and comparison predicates.

[...]

>
>
> Couldn't a `composite index' be supported by a key which is a tuple of
> some number of references?

I guess you're taking inspiration here from your own library's design. This
implementation of composite indices simply doesn't fit here. You can consider
things are "the other way around" with respect to indices and dependent keys:
every index is composite. Those that happen to depend on a single member
of the element can be conveniently built by resorting to less_by. I'm
not sure I'm being clear enough. If not, please tell me so.

On a side note, taking composite indices as indices over a tuple of
members does not cover the full spectrum of what an index can do. Imagine an
index whose associated comparison predicate depend on the result of an
external function, say

int f(const element& e);

f() won't accept a tuple of members of element, but the actual element. To make
it fit one would be forced to construct a new element on the fly out of the
provided parts.

[...]

> I rechecked the status of the proposal, and it appears that the LWG has
> decided to clarify that both set iterator and const_iterator are
> constant.

[...]

>
> Thus it appears your decision to have only constant iterators is correct.

Great! On this we agree :)

>
>
> It occurs to me that a mechanism for the user to specify that reordering
> may be required in only certain indices as a result of a modify
> operation.  This syntax could be used:
>
> table.modify(it, functor); // all indices are updated
> table.modify<0, 1, 3>(it, functor); // indices 0, 1, and 3 are updated
> table.modify<tag1>(it, functor); // indices with tag1 are updated
> table.modify<tag1, tag2>(it, functor); // indices with either tag1 or
>                                         // tag2 are updated
>
> (The tagging mechanism I am using in my policy-based table allows for
> more than one tag to be "attached" to a single index and for more than
> one index to have the same tag.)

I don't think specifying which indices are changed fits well here. It
requires extreme knowledge from the programmer, and trusting her
(by not updating other indices) can leave the container in a bad state.
On the other hand, I am extremely interested in the technique you're
using for tagging indices. Could you please enlighten me on that?

[...]

>
>  > 1. Leave update() as it is as a well-defined updating mechanism when
>  > copy cost is not a concern, and for entry-level users.
>
> If my suggested semantics for erasing elements when a "collision" exists
> are used, is there any advantage to update over modify with a simple
> assignment functor.  With boost.lambda, such a call to modify could be
> as simple as:
>
> value_type newValue = ...;
> table.modify(it, _1 = newValue);

There's a difference. With update(), if a collision happens the changed
element is kept with its original value. With modify(), it is erased.
BTW I like the names "update" and "modify" in that they suggest the
way the different memfuns work: Somehow, "modify" seems more
intrusive, which precisely modify() is. What do you think about it?

>
>
>  > 2. Provide a modify (should be call it internal_update?) facility that
>
> Personally I prefer the name modify.

On a second thought, me too.

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