Hi Dave, 2nd part of your post. ----- Mensaje original ----- De: "David B. Held" <dheld@codelogicconsulting.com> 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