Boost logo

Boost :

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


Boost list run by bdawes at, gregod at, cpdaniel at, john at