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

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
that
> is set when items are inserted. When a potential access is
requested,
> 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
pseudo-constant.

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           -           http://rainerdeyke.com
"In ihren Reihen zu stehen heisst unter Feinden zu kaempfen" - Abigor