Re: [boost] Re: Formal Review: Indexed Set

From: Joaquín Mª López Muñoz (joaquin_at_[hidden])
Date: 2004-04-01 11:17:39

Rob Stewart ha escrito:

> From: Matthew Vogt <mvogt_at_[hidden]>

> > I thought that the value of this facility was when you could replace an
> > existing STL container with an indexed_set when you had a need to a second
> > index, without disrupting the code that was already accessing the existing
> > container.
> >
> > In this situation, the existing code, unchanged, uses the default index, while
> > new code can be added which explicitly uses the additional index/indices to
> > gain the advantages of the new characteristics.
>
> You're right.  That does sound valuable, but I didn't walk away
> from reading the documentation with that idea.  I just saw it as
> inconsistent treatment of the first index.  Maybe it was there
> and I'm just blind.

FWIW, this was a concious decision, not an implementation
artifact (removing it would involve substituting a "protected" for
a "public", that's all).
Although not explicitly stated, the idea is certainly that one can
replace an STL container with indexed_set and have most of
the original code working without surprises. Please take a look
at the section "A bidirectional list with fast lookup" in the tutorial,
where it is shown how replacing std::list with
indexed_set<string,index_list<sequenced<>,...> > keeps
preexisting user code usable.

A more philosopical rationale behind this decision is that the first
index is thought of as the "primary" one, and probably the user
will access this index more frequently than the others. For instance

indexed_set<
  int,
  index_list<
    unique<identity<int> >,
    sequenced<>
  >
>

can be regarded as a set with an insertion log, while

indexed_set<
  int,
  index_list<
    sequenced<>,
    unique<identity<int> >
  >
>

will more likely be thought of as a list with fast lookup.
However, both types are tecnhically the same, save the
default get<0>() thing.

> > While it seems to increase the chance of erroneous usage, it strikes me as a
> > useful characteristic.
>
> That is useful, but only if the resulting indexed_set is
> sufficiently semantically similar to the container it replaces.
> indexed_set doesn't provide the subscript operator, so the
> replacement won't be seamless if you use that operator on a map.
> There are other differences which may cause problems.  However, I
> haven't got any experience with these problems or with it working
> well, so I'm speaking entirely theoretically.

>
> If there are important behavioral differences between std::set
> and an indexed_set configured like a set, or between std::map and
> an indexed_set configured like a set (other than the missing
> operator, which will simply fail to compile), or between
> std::list and an indexed_set configured like a list, then silent
> substitution doesn't seem appropriate.  If the differences are
> unimportant semantically or if they only change a constant in the
> complexity guarantees, for example, then silent substitution is
> appropriate.  I'm not qualified to judge this, but I'm sure
> Joaquín is.

The situation wrt drop-in replacement is summarized in the advanced
topics, section "Simulating standard containers with indexed_set".
Briefly put, sets are emulated exactly, multisets with tiny syntactic
differences, and lists with the main drawback that elements are no
longer mutable (save with update() and modify()). Map simulation,
OTOH, is probably not suitable for drop-in replacement.
Also, AFAICS replacement is safe in the sense that the original
code either no longer compiles or works with the original
semantics (complexity changes, though.)

> IIRC, get<0>() works, but is not necessary.  Given that, generic
> code won't have to treat the first index differently than the
> others, so that aspect seems fine, regardless of whether it
> inherits the interface of the first index.

That's exact.

Regards,

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