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

From: Carl Daniel (cpdaniel_at_[hidden])
Date: 2002-01-08 17:38:07

From: "David Abrahams" <david.abrahams_at_[hidden]>
> From: "corwinjoy" <cjoy_at_[hidden]>
>
> > I think it would be nice to try to come to some agreement on a family
> > of solutions for this.
>>
> > 1. After the container is first sorted, is it the container's job or
> > the user's job to sort it if elements are later added or removed?
>
> I want to at least have an interface available which lets me say, "I know
> what I'm doing; put this /here/, and don't waste any time
> verifying/re-sorting".

Agreed.  In my implementation, I provided the normal std::map/set insert operations, which maintained sorted order.  A
client could do un-sorted inserts by directly accessing the underlying sequence (vector) and (if necessary) re-sorting
to restore the invariant.

One difference (I think) in what I implemented versus the others that have been described is that I did not embed the
sequence container within the associative container.  Instead, my sequence_set<> (or map) would be constructed "on top
of" an existing sequence, thus both interfaces are available to the client.  Caveat programmer :)

> >
> > So I guess the proposals out there are something like this:
> >
> > 1. Simple sorted vector by value.
> > - Fast sort/lookup for small objects.
> > - Not sorted if inserts are made after the initial sort.
>
> There should be an insert interface which inserts in-order.
> There should also be one that inserts "with hint" at the closest in-order
> position to the supplied iterator.
>
> > - Iterator invariants not maintianed after deletes.
>
> No, the iterators are invalidated by deletes. That's markedly different.
>
> > - Not exception safe for objects whose copy operations can throw.
>
> Disagree, again.

Provides the exact exception safety guarantee that the underlying sequence container provides.

-cd