Блог пользователя multisystem

Order of incrementing set::iterator
Автор multisystem, 10 лет назад, По-английски

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)?

Теги c++, stl
  • Проголосовать: нравится
  • +12
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

Yes.

→ Ответить
»
10 лет назад, # |
← Rev. 2   Проголосовать: нравится +29 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Very helpful. Thanks

    → Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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?

    → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится -10 Проголосовать: не нравится

      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.

      → Ответить
      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Oh, I see now, thanks

        → Ответить
      • »
        »
        »
        »
        10 лет назад, # ^ |
        ← Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

        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

        → Ответить
      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится +18 Проголосовать: не нравится

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

        Expression    Complexity
------------------------
a.begin()     constant
        → Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

    → Ответить