From: Alan Bellingham (alan_at_[hidden])
Date: 2002-01-20 13:10:46
>So we get a 'vector that remembers if it has been sorted' rather than a
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
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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk