Re: [boost] Re: IndexedSet Review

From: JOAQUIN LOPEZ MU?Z (joaquin_at_[hidden])
Date: 2004-03-29 16:40:11

Hi Dave, 2nd part of your post.

----- Mensaje original -----
De: "David B. Held" <dheld_at_[hidden]>
Fecha: Lunes, Marzo 29, 2004 9:57 pm
Asunto: [boost] Re: IndexedSet Review
[...] 
> > As for the Composite Sorted Associative Container concept, we
> > have the same problem. Technically, the requirements imposed
> > to current or future index types by indexed_set are much weaker
> > than being some sort of associative container. I cannot even state
> > global complexity bounds (please check the reference, page
> > "Index reference", section "Complexity signature").
> 
> Ok, so if the concept is not a refinement of Associative Container,
> then create a new concept!
> 
> > I agree with you a concept section would be highly desirable, but
> > here I definitely need some help. What you request is not trivial.
> 
> Then let's take a first stab at it.  What you have is similar to an
> Associative Container, but is fundamentally different.  The way in
> which it is different is that there is more than one way to access
> the data.  And, as you say, it is like multiple containers in one. 
> So
> I think the most fundamental concept here is Composite Container.
> [...]

Agreed. 

> Let's rip off SGI for a minute:
> 
>    Description
> 
>    A Composite Container is a variable-sized Container that
>    supports retrieval of elements (values) based on one or more
>    keys. It supports insertion and removal of elements, but differs
>    from an Associative Container in that the complexity of the
>    operations depends on the type of key indices used.

Not agreed. A Composite Container is more primitive than
that. Keys properly belong to the indices (some indices
are even not key-based.)

I would try first to forge the Index concept. Then
a Composite Container is more or less trivially
defined as a "composition" (wants definition) of
indices. We could call an Associative Composite Container
to a Composite Container whose indices model
Associative Index (wants def). A bimap is a model
Assoc Comp Container, as well as some instantiations
of indexed_set.

The part of index retrieval (the get<> stuff)
I don't see any hope of being conceptualized, as
bimap, for instance, could perfectly lack such
interface in favor of something simpler for
the data structure at hand.

Probably, a Composite Container is *not* any kind
of Container (its indices are, though): imagine an
indexed_set that does not inherit the functionality
of its first index.

[...]
 
> Now, here we have a tricky issue.  By default, IndexedSet *is*
> default constructible, but we can't say that Composite Container
> should be, because IndexedSet might *not* be default c'tible if
> one of the key types are not.  The STL solved this by simply
> implicitly requiring key comparators to be default c'tible, but
> perhaps this requirement is not justified.  Anyway, let's continue:

Oh, I hadn't thought of this before. Really std::sets
implicitly require that their key objetcs are Default
Constructible. Seems a defect to me.

[snipped rest of stuff]

Well, all these sections really belong (IMHO)
to the Index concept.
> 
> Models
> 
>    * indexed_set (of course)
>    * bimap (if anyone makes it ;)
> 
> That's a start anyway, and if you fill in as much of that as you can,
> I think others will be able to help you fill in the rest.  It also 
> mighthelp if you define other concepts first, like Ordered Unique 
> Index,etc.  I know it's a lot of work, but I think it's worthwhile 
> (especiallyfor people wanting to extend the library, i.e.: by 
> defining custom
> index types).

Well, I'll try to come up with something, but it'll
take long. If this is a requirement for acceptance,
it certainly will affect to the availability time.

> 
> > [...]
> > My Latin (I speak Spanish) heritage makes me favor "indices"
> > to "indexes" (and "minuscule" to "miniscule", etc.) The Google
> > metric could be biased by the fact that "indexes" is not only the
> > plural of "index" but also the 3rd singular formal of the Present
> > tense of the verb "index".
> 
> Good call!  That was some sloppy reasoning on my part. ;)

To be honest, there's bias on the other side to:
"indices" is a valid French and Spanish word.

Cheers,

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