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.
> I think the most fundamental concept here is Composite Container.
> Let's rip off SGI for a minute:
> 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
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.
> * 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.
Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk