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

From: Jeremy Maitin-Shepard (jbms_at_[hidden])
Date: 2003-07-09 19:15:43

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.

 > 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).

 >     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.

 > 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.

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).

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.

Note that having key extractors does not prohibit using a comarison 
functor that is integrated with key extraction, since the formal key 
extractor can be specified as an identity functor, thus the key_type is 
the value_type.

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

 > 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).

http://std.dkuug.dk/jtc1/sc22/wg21/docs/lwg-defects.html#103

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.  The text describing the defect (not the resolution) is 
somewhat inconsistent with the actual resolution, and it appears that 
the defect report initially proposed as the resolution requiring a 
non-constant set iterator, but the LWG later changed the resolution to 
the one upon which they decided.

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

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 realize that if a functor is modified to invalidate an additional 
index, but the code that uses the functor is not changed.  However, I do 
not see any way to beter "associating' the specification of which 
indices are invalidated with the functor.

 > 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);

 > 2. Provide a modify (should be call it internal_update?) facility that

Personally I prefer the name modify.

---
Jeremy Maitin-Shepard