From: Allan Odgaard (ML_at_[hidden])
Date: 2004-03-18 16:04:49
On 18. Mar 2004, at 11:50, David B. Held wrote:
>> I guess I'm not fully understanding the use case.
> [...] I had an application where data was being inserted continuously
> (not at a high rate, but high enough that I didn't want O(N) insert).
> The data had to be sorted, and you needed to be able to jump to any
> arbitrary point in the data and start iterating, without doing an O(N)
I had a similar problem myself, but I found that the slower (lg N)
lookup time (even though iteration from that point was linear) did not
make up for the faster insertion, because, most of the time I used the
lookup methods -- and in your listview example, I would think the same
is the case in 99% of the applications I can envision. Similar with the
client/server example, since the 3,000 clients only fetch data from the
database as I understood it.
My problem was that insertions could come in bursts, and could e.g. all
go to the start of the container -- my solution was to create a cache
or insertion queue (in lack of a better name), to which items were
initially added, and lookup would take this queue into consideration.
The queue was of fixed size and flushed (in O(n) time) when it was
full. Basically giving me the same theoretical time complexities as
only using a vector, but in practice making insertion of m items
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk