Iterator performance on associative containers

J

Johs

I have implemented a red-black tree based on the description in Introduction
to Algorithms Cormen section 13. But I would like to make all iterator
operations to take O(1) time in worst case. Is this even possible and if so
does anyone know of any articles websites dealing with this optimzation?
 
?

=?ISO-8859-1?Q?Erik_Wikstr=F6m?=

I have implemented a red-black tree based on the description in Introduction
to Algorithms Cormen section 13. But I would like to make all iterator
operations to take O(1) time in worst case. Is this even possible and if so
does anyone know of any articles websites dealing with this optimzation?

This is not a C++ question so if you have more like this one try some
other group, perhaps comp.programming.

While I'm not 100% sure I don't think that you can make all iterator
operation work in O(1) (but you have not defined which operations you
want on an iterator). The field of data-structures and algorithms is
quite well charted so what you read in the books is usually "state of
the art" (and usually figured out a number of years ago).
 
J

James Kanze

On 2007-06-03 22:12, Johs wrote:
This is not a C++ question so if you have more like this one try some
other group, perhaps comp.programming.
While I'm not 100% sure I don't think that you can make all iterator
operation work in O(1) (but you have not defined which operations you
want on an iterator).

Sure you can, at the cost of an additional pointer or two per
node, and some extra time at each insertion. Just keep all the
nodes in a double linked list.
 
J

Juha Nieminen

Johs said:
I have implemented a red-black tree based on the description in Introduction
to Algorithms Cormen section 13. But I would like to make all iterator
operations to take O(1) time in worst case. Is this even possible and if so
does anyone know of any articles websites dealing with this optimzation?

I suppose you could have two additional pointers in the tree nodes:
One pointer for the previous node and another for the next node (in the
traversal order). You'll have to figure out how to update these pointers
when nodes are added and removed from the tree, but I'm confident that
it can be done in log n time.

OTOH one could ask if you really need this. While one single iterator
increment or decrement may require O(log n) steps, the total number of
steps for a full traversal is still O(n) (not even amortized O(n), but
pure O(n)). So you should ask yourself if random single increments /
decrements are so frequent in your program that it justifies the
additional memory needed for the pointers and the overhead of keeping
them updated when the tree changes.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top