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

From: AlisdairM (AlisdairM_at_[hidden])
Date: 2002-01-20 12:28:19

-----Original Message-----
From: Alan Bellingham [mailto:alan_at_[hidden]]
Sent: 20 January 2002 15:47
To: boost_at_[hidden]
Subject: Re: [boost] More ramblings on a sorted vector container

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

That is exactly why you should use the vector::insert for this kind of
operation (as per 'Effective STL')  The range-taking members of the vector
can take advantage of the knowledge to apply this sort of optimisation.

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

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

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

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

AlisdairM