map : iterator increment/decrement code

Discussion in 'C++' started by John, May 15, 2005.

  1. John

    John Guest

    I was wondering why the STL RB Tree implementation is
    used when the iterators of map are incremented/decremented
    to yield successors and predecessors? This takes O(log n)
    time (and a lot of memory thrashing depending on the size
    of the tree) whereas just a simple pointer chase would make it O(1).
    Is there an easy way to code this in C++ (Threaded red
    black tree? ) OR Modify map so that map<>::iterator, ++it/--it
    becomes O(1)?

    Thanks in advance for your comments,
    --j


    [ See http://www.gotw.ca/resources/clcm.htm for info about ]
    [ comp.lang.c++.moderated. First time posters: Do this! ]
    John, May 15, 2005
    #1
    1. Advertising

  2. Re: iterator increment/decrement code

    John wrote:
    > I was wondering why the STL RB Tree implementation is
    > used when the iterators of map are incremented/decremented
    > to yield successors and predecessors?


    I am wondering why are you sure that it is what's happening.

    > This takes O(log n)
    > time (and a lot of memory thrashing depending on the size
    > of the tree) whereas just a simple pointer chase would make it O(1).


    And why are you sure that it's not so?

    > Is there an easy way to code this in C++ (Threaded red
    > black tree? ) OR Modify map so that map<>::iterator, ++it/--it
    > becomes O(1)?


    What makes you think that all this would be necessary? Do you have
    any definite results from running some tests that the performance of
    ++/-- is not acceptable? And even if you do, what makes you think
    that it's not just your particular implementation of the Standard
    library? AFAIK, there is no specific requirement in the Standard
    that 'std::map' or its iterators have any particular implementation.

    V
    Victor Bazarov, May 15, 2005
    #2
    1. Advertising

  3. John

    P.J. Plauger Guest

    Re: iterator increment/decrement code

    "John" <> wrote in message
    news:...

    > I was wondering why the STL RB Tree implementation is
    > used when the iterators of map are incremented/decremented
    > to yield successors and predecessors?


    Because the RB tree is also used to do inserts, erases, and
    finds?

    > This takes O(log n)
    > time (and a lot of memory thrashing depending on the size
    > of the tree) whereas just a simple pointer chase would make it O(1).


    And in practice, *most* increments and decrements (in a large
    tree) are indeed O(1). It's just that every once in a while
    you come to the end of a subtree and have to do O(log N)
    operations to find the successor. So amortized time complexity
    is O(log N).

    > Is there an easy way to code this in C++ (Threaded red
    > black tree? ) OR Modify map so that map<>::iterator, ++it/--it
    > becomes O(1)?


    You probably could, at the expense of making inserts and erases
    even more expensive. They'd have to update two more links
    (predecessor and successor) in addition to the existing three
    (parent, left subtree, and right subtree). I suspect the
    time complexity would still be O(log N), but with a notably
    bigger multiplier.

    And if you care about memory thrashing, you're bound to get
    more of it with five pointers per node instead of three.
    The member functions insert and erase also get bigger, so
    you increase the chance of code thrashing.

    And if you care about implementation bugs (as I do), you're
    bound to get more of them when the code has to maintain two
    only loosely related data structures instead of one to preserve
    tree integrity.

    P.J. Plauger
    Dinkumware, Ltd.
    http://www.dinkumware.com


    P.J. Plauger
    Dinkumware, Ltd.
    http://www.dinkumware.com



    [ See http://www.gotw.ca/resources/clcm.htm for info about ]
    [ comp.lang.c++.moderated. First time posters: Do this! ]
    P.J. Plauger, May 16, 2005
    #3
  4. John

    Kai-Uwe Bux Guest

    John wrote:

    >
    > I was wondering why the STL RB Tree implementation is
    > used when the iterators of map are incremented/decremented
    > to yield successors and predecessors? This takes O(log n)
    > time (and a lot of memory thrashing depending on the size
    > of the tree) whereas just a simple pointer chase would make it O(1).


    Actually it is implementation dependent, but in any case, the
    implementation you are hinting at is amortized constant time. That is not
    that bad a design for an iterator: in most cases you will use them to
    iterate through a rather longish piece of the map.

    > Is there an easy way to code this in C++ (Threaded red
    > black tree? )


    That depends: what do you consider easy? You would have to run your own
    RB-tree implementation.

    > OR Modify map so that map<>::iterator, ++it/--it becomes O(1)?


    That would be possible with containers that are templated on the underlying
    tree structure. I do not know if there is an implementation available that
    supports this.


    Best

    Kai-Uwe Bux

    [ See http://www.gotw.ca/resources/clcm.htm for info about ]
    [ comp.lang.c++.moderated. First time posters: Do this! ]
    Kai-Uwe Bux, May 16, 2005
    #4
  5. Re: iterator increment/decrement code

    P.J. Plauger wrote:
    > "John" <> wrote in message
    > news:...
    >
    > > I was wondering why the STL RB Tree implementation is
    > > used when the iterators of map are incremented/decremented
    > > to yield successors and predecessors?

    >
    > Because the RB tree is also used to do inserts, erases, and
    > finds?
    >
    > > This takes O(log n)
    > > time (and a lot of memory thrashing depending on the size
    > > of the tree) whereas just a simple pointer chase would make it

    O(1).
    >
    > And in practice, *most* increments and decrements (in a large
    > tree) are indeed O(1). It's just that every once in a while
    > you come to the end of a subtree and have to do O(log N)
    > operations to find the successor. So amortized time complexity
    > is O(log N).


    If you iterate from begin() to end() you go along each edge
    exactly twice (once down, once up). And since there are exactly
    size()-1 edges in a tree (plus 1 additional from the non-node
    "root") the increment time complexity is amortized constant
    unless you mean amortized _with respect to_ something else than
    incrementing every incrementable iterator once.

    Vladimir Marko


    [ See http://www.gotw.ca/resources/clcm.htm for info about ]
    [ comp.lang.c++.moderated. First time posters: Do this! ]
    Vladimir Marko, May 17, 2005
    #5
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Hendrix
    Replies:
    1
    Views:
    1,664
    Ivan Vecerina
    Jun 29, 2003
  2. Mark Turney
    Replies:
    11
    Views:
    4,262
    dibeas
    Nov 13, 2006
  3. Ian Pilcher

    Increment, decrement, overflow, and underflow

    Ian Pilcher, Jan 20, 2005, in forum: C Programming
    Replies:
    5
    Views:
    572
    CBFalconer
    Jan 21, 2005
  4. lovecreatesbeauty
    Replies:
    8
    Views:
    1,627
    Old Wolf
    Sep 12, 2005
  5. Angel Tsankov
    Replies:
    8
    Views:
    458
    Ian Collins
    Feb 27, 2006
Loading...

Share This Page