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

From: Rob Stewart (stewart_at_[hidden])
Date: 2004-04-01 12:26:54

From: =?iso-8859-1?Q?Joaqu=EDn=20M=AA=20L=F3pez=20Mu=F1oz?= <joaquin_at_[hidden]>
> 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.
> > >
> > 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.
> 
> 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

I think it should be stated explicitly.  If nothing else, it will
beat folks like me over the head with the obvious!

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

I remember reading that, but I didn't think of it in terms of,
"See?  You can switch to indexed_set without changing existing
code plus you can start using additional indices."  I do recall
reading that one might choose to use an indexed_set just to get
the added capabilities aside from extra indices.

> 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

You're probably right that the "primary" index is likely to be
the first one specified, when there is a primary index.  However,
there are just as likely to be uses of indexed_set in which none
of the indices is preeminent.

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

In a sense, though, that's an argument against inheriting the
first index's interface.  By promoting one over the others, you
give it special significance which it actually doesn't have
(beyond syntax, of course).

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

Since the performance degradation of single-index indexed_sets
relative to "normal" containers is documented, one has to assume
that the switch from a "normal" container to an indexed_set was
done considering performance to gain something else.  Therefore,
the only remaining issue is whether user code can silently change
behavior when switching to indexed_set.  Your sense is that this
is not a problem, so I withdraw my complaint over making index 0
default.  It wouldn't hurt to remove the default, but it doesn't
concern me anymore.  However, if subsequent broader usage reveals
problems with it, I think you should change it so that users must
make a conscious choice to use index 0.

-- 
Rob Stewart                           stewart_at_[hidden]
Software Engineer                     http://www.sig.com
Susquehanna International Group, LLP  using std::disclaimer;