Re: [boost] More ramblings on a sorted vector container

From: David Abrahams (david.abrahams_at_[hidden])
Date: 2002-01-20 08:52:51

----- Original Message -----
From: "AlisdairM" <AlisdairM_at_[hidden]>

> Jumping into the earlier discussion on sorted vectors, I am wondering why
> the 'obvious' implementation is not deemed adequate?

Today seems to be your day to ask for rationale... ;-)

> A sorted vector should be (to my mind) exactly that, a vector that remains
> sorted.  Hence, all insert methods should also sort the vector,
guaranteeing
> the sorted condition.  Obviously, the range-insertion methods become key
to
> efficient usage as they will (probably) sort once after inserting all new
> members.  push_back cannot really be supported, and pop_back raises
symmetry
> problems, but otherwise that would seem to be it to me (beyond hammering
out
> exception safety guarantees)

That's useful, but not as useful as it should be. At least, I want some
other options. I /frequently/ find myself needing finer-grained control than
the restrictive interface provided by the standard associative containers.
Just one example is when I am modelling a bijection by storing a set of
points. Sometimes you want to search on the key, sometimes on the value. I
can't think of the other examples off the top of my head, but for me, things
like this come up *all the time*.

> Any other concerns such as iterator stability are valid, but they aren't a
> *sorted vector*, simply a better associative container that may (or may
not)
> be implemented in terms of a vector.  Naming it after a vector is only
going
> to confuse.

I think that's just a shorthand we're using for the sake of the discussion.
I had been calling them "sorted linear associative containers" but that can
get long-winded.

-Dave