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/