multisystem's blog

Order of incrementing set::iterator
By multisystem, 10 years ago, In English

Assuming the following snippet of code

set<int>::iterator it = st.begin();
it++;

What's the order of it++. Does it take O(log n)?

Tags c++, stl
  • Vote: I like it
  • +12
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Yes.

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +29 Vote: I do not like it

It's O(1) amortized, as it just traverses binary tree going up and down, and O(log n) in a worst case for one ++ operation, as std::set uses red-black tree which has logarithmic height.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Very helpful. Thanks

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Code from the post is

    set<int>::iterator it = st.begin();
it++;

    Beginning of the set is the leftmost element, and it's parent will be the next, so this code will always run in O(1). Am I right?

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

      No, you're wrong.

      First, the leftmost element isn't always a leaf, so the increment won't always work in O(1).

      Second, I'm not sure that set::begin() must work in O(1) according to the C++ standard. So, I'd always rely only on the upper bound.

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Oh, I see now, thanks

        → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← Rev. 3   Vote: I like it +3 Vote: I do not like it

        It seems that if begin() is not a leaf then depth of its subtree is constant because black height of left subtree is 0, so black height of right subtree is 0 too. And it's either empty or one red vertex.

        Note, that I suppose that it's red-black tree and it's not guaranteed.

        cppreference and cpkuspkus com say that std::set::begin() is constant but I'm not sure if it is reliable source

        → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +18 Vote: I do not like it

        In C++11 23.2.1 "General container requirements", in Table 96 you have

        Expression    Complexity
------------------------
a.begin()     constant
        → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    In other words, iterating over the whole set takes O(n) worst case (inorder traversal). Executing a single it++ (looking for successor) takes O(lg n) worst case.

    → Reply