Boost logo

Boost :

From: Rainer Deyke (root_at_[hidden])
Date: 2002-01-20 11:45:48

----- Original Message -----
From: "Alan Bellingham" <alan_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Sunday, January 20, 2002 8:47 AM
Subject: Re: [boost] More ramblings on a sorted vector container

> My personal strategy for this sort of thing would be to have a flag
> is set when items are inserted. When a potential access is
> the underlying std::vector<> is then sorted, and the flag cleared.

An item can be inserted into the correct position (using
'std::lower_bound') in O(n) time. A full sort ('std::sort') takes O(n
log n) time. Consequently your method is only faster when inserting
'm' items, where 'm > k log n' where 'k' is some platform specific

In my experience 'm' is usually 1, so I prefer a system where sort
order is always maintained.

Rainer Deyke (root_at_[hidden])
Shareware computer games           - 
"In ihren Reihen zu stehen heisst unter Feinden zu kaempfen" - Abigor

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