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

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

"David Abrahams" <david.abrahams_at_[hidden]>:

>From: "Alan Bellingham" <alan_at_[hidden]>
>
>> 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.

Indeed. However, all such iterators, references and pointers would
already be invalid - the previous insertions had already done that. It's
only the first access after an insertion that could cause the internal
sort - once done, newly generated i's, r's and p's would remain valid
till the next sequence mutating operation.

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

One possible bit of control would be if the sort could be guaranteed not
to throw, at which point an in-place sort could be used. This would be a
template parameter.

Also, I would see no reason not to supply the ability to make an
explicit call to the underlying sorting functionality, so the user can
know that it is not going to throw unexpectedly. 

Hmm, as I understand your suggestion, and applying it here, you'd not
have the flag. Instead, you'd note size() when a sort occurs, and would
compare that to size() to determine whether to sort. You'd then sort the
range from that old size to the new size, and do the inplace_merge().

Neater. A little extra bookkeeping for element deletion would update the
recorded size as well. 

It'd also turn the insertion+sort for a single element back into the
O(n) that Rainer Deyke just mentioned.

(For simplicity, I'm assuming only const i's, r's and p's are allowed,
as I see no way to maintain sortedness on element change without using
proxies.)