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

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

AlisdairM:

>So we get a 'vector that remembers if it has been sorted' rather than a
>'sorted vector'.

More a 'vector that's always sorted when you look at it'.

>> 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.
>
>Which is not a guarantee I feel is reliable, as you have no way of knowing
>then the reallocation occurred (bad cough you have there)

Actually, the standard guarantees that vector reallocation doesn't occur
if size() is less than capacity(), and is why it supplies reserve(). I
think it's a fairly safe bet that when size() exceeds capacity(),
reallocation would 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.
>
>These problems are reduced by remaining always sorted, and using the range
>operations for efficiency, but the specification of those operations becomes
>tricky!

A little tricky, yes. For an 'always sorted vector', the range insert
could become an append + sort(appended) + inplace_merge.

Time for me to study the previous code, I think.