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

From: David Abrahams (david.abrahams_at_[hidden])
Date: 2002-01-20 11:10:41

----- Original Message -----
From: "Alan Bellingham" <alan_at_[hidden]>

> My personal strategy for this sort of thing would be to have a flag that
> is set when items are inserted. When a potential access is requested,
> the underlying std::vector<> is then sorted, and the flag cleared.
>
> This would cause all insertions to turn into std::vector<>::push_back
> plus a flag set, and indexing and iterator generation to turn into a
> flag check (with sort if flag still set) followed by their normal
> operation.
>
> The guarantees about iterator stability would change slightly - all
> insertions would invalidate, which would be a little worse than
> std::vector<> which can keep them valid when reallocation doesn't occur.
>
> <cough>
>
> Exception safety would be an interesting problem, though - a supposedly
> non-mutating operation such as getting a const_iterator could cause a
> sort, and the sort couldn't be guarateed not to throw.

Not to mention that all of your iterators, pointers, and references would be
scrambled.

> Internally
> sorting into a new vector and swapping would get around that, but
> potentially use a lot of space in the process.

Issues like this one are exactly why some of us need more control. It seems
like on-demand sorting could be disastrous, and not every operation needs to
be automated. For this case I would want to be able to use push_back() +
sort() + inplace_merge().

Regards,
Dave