Re: [boost] Re: Proposal: Sorted Vector Container

From: Carl Daniel (cpdaniel_at_[hidden])
Date: 2002-01-08 13:19:20

From: "David Abrahams" <david.abrahams_at_[hidden]>
> From: "Carl Daniel" <cpdaniel_at_[hidden]>
>
> > Dave - what were the issues with the version you & John Potter worked on
> > several months ago?
>
> We have three known designs:
>
> simple - direct containment, no stability, fast/small iterators
>
> indirect - held by some kind of pointer, pointer/reference stability, small
> iterators w/fast traversal
>
> "Mike+Corwin" - direct containment with changelog, iterator stability,
> larger slower iterators
>

The simple, direct version is the only one I've ever wanted.  In my simple version, the underlying sequence was required
to be sorted as a pre-condition to construction of the sequence_map<>.  Since my use entailed storing always-sorted
vectors on disk, I didn't want the implementation of sequence_set<> to ever sort the container.

The indirect associated container is interesting, particularly in that it affords the ability to view an underlying
container with several distinct orderings simultaneously.   This approach is likely be more efficient than the direct
approach if the contained objects are expensive to copy, and vice-versa.

The Mike+Corwin version is starting to sound complicated - is it really an advantage over std::map/set/multimap/multiset
in many applications?

Perhaps these three approaches should all be persued - they have distinct application domains, each with their own
strengths and weaknesses.

-cd