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

From: Jeremy Maitin-Shepard (jbms_at_[hidden])
Date: 2003-07-08 18:01:25

Joaquín Mª López Muñoz wrote:

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

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.

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

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.

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

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

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.

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.

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

In this case, the modify method described above is sufficient, and the 
exception behavior is irrelevant.

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

---
Jeremy Maitin-Shepard