C++ Programming :: Iterator performance on associative containers


	Iterator performance on associative containers 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? On 2007-06-03 22:12, Johs wrote: > 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). -- Erik Wikstrm On Jun 3, 11:33 pm, Erik Wikstrm <Erik-wikst@telia.com> wrote: > On 2007-06-03 22:12, Johs wrote: > > 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). 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. -- James Kanze (Gabi Software) email: james.ka@gmail.com Conseils en informatique oriente objet/ Beratung in objektorientierter Datenverarbeitung 9 place Smard, 78210 St.-Cyr-l'cole, France, +33 (0)1 30 23 00 34 Johs wrote: > 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.