Re: [boost] Re: Is there any interest in this container?

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

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 
significantly faster.
-- 
    http://www.diku.dk/hjemmesider/studerende/duff/