Re: map and set classes implemented with a tree having dynamic order statistics

From:

Maxim Yegorushkin <maxim.yegorushkin@gmail.com>

Newsgroups:

comp.lang.c++

Date:

Wed, 8 Oct 2008 07:20:50 -0700 (PDT)

Message-ID:

<f172de1d-07ed-4e78-a5c5-92999d3c50b5@w39g2000prb.googlegroups.com>

On Oct 8, 2:16 pm, DJ Dharme <donjuandharmap...@gmail.com> wrote:

On Oct 8, 5:17 pm, Maxim Yegorushkin <maxim.yegorush...@gmail.com>
wrote:

On Oct 8, 10:20 am, DJ Dharme <donjuandharmap...@gmail.com> wrote:

Does anybody know about a solid implementation of a map o=

r a set

with dynamic order statistics which allows the user to access a node
by its Index in log(N) time. I have a problem of sorting a huge data
set and showing it row by row. I have to quickly jump to a new
starting point on demand. If I use the std set class it takes so many
iterations to jump to a new location since we have to increment the
iterators until we get the correct row no.

Can you not use a sorted vector? Accessing elements by key is
O(lg(N)), by index is O(1) and there is no memory overhead compared to
std::set/map.

Thanks for the reply, yes I have tested this with vectors but failed
since I have to dynamically change (add, update, remove) the records.
The record count can grow up to few millions. And when the vector
starts to re-allocate memory the program hangs for some time.

[]

In this case you can use std::deque<> to avoid paying for reallocating
and moving many elements.

Also I have to sort the records on each update. So if I
use a vector large amount of items will be moved back and forth due to
insertions and removals.

To insert an element in a sorted vector or deque you do lower_bound
followed by insert. No need to sort again the whole container.

--
Max