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)?
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)?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 155 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 145 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 132 |
| 10 | cry | 130 |
Yes.
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.
Very helpful. Thanks
Code from the post is
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?
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
upper bound.
set::begin()must work in O(1) according to the C++ standard. So, I'd always rely only on theOh, I see now, thanks
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
In C++11 23.2.1 "General container requirements", in Table 96 you have
In other words, iterating over the whole set takes
O(n)worst case (inorder traversal). Executing a singleit++(looking for successor) takesO(lg n)worst case.