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

From: Alan Bellingham (alan_at_[hidden])
Date: 2002-01-20 10:47:05

Alisdair Meredith:

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

Because boosters can't leave a simple thing alone? :-)

>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.

This strikes me as being horribly inefficient in the situation that a
whole of items are added in a loop (for instance, std::copy<>). Each
insertion would trigger a sort.

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. Internally
sorting into a new vector and swapping would get around that, but
potentially use a lot of space in the process.

At least C++ allows us to try a lot of different strategies.

Alan
-- 
Alan Bellingham