From: Alan Bellingham (alan_at_[hidden])
Date: 2002-01-20 10:47:05
>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
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.
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 Bellingham
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk