Boost logo

Boost :

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
> 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
>> 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
> then no fail or throw is permitted after the element has changed its
> 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

Boost list run by bdawes at, gregod at, cpdaniel at, john at