Is it mean that if pos somewhere inside then it really takes constant but if position is first or last then it takes log(size) overtime to recalculate new first and last to make

set::begin, set::end being with complexity constant?

set::begin, set::end being with complexity constant?

It means the erase time of that function is constant, and not dependent on the size of the container.

It says nothing about the value of the iterator.

It says nothing about the value of the iterator.

std::set is often implemented as a tree. When a node is removed the tree has to be rebalanced, which can take different amount of time depending on how much has to be done to get the tree balanced again. The way I understand amortized constant is that the average time it takes calling erase will be constant when calling erase many times.

Last edited on

The way I understand amortized constant is that the average time it takes calling erase will be constant when calling erase many times. |

It's right way to understand key word "amortized". I just asked where that amortization takes effect and why it usually

So, it means thay my version implemented rather like red-black tree. But for such trees both insert and delete are O(log n) for keys passed and, i guess, O(1) for known positions. Oh no, i see from

http://en.wikipedia.org/wiki/Red%E2%80%93black_tree:

However, the immediate result of an insertion or removal may violate the properties of a redâ€“black tree. Restoring the redâ€“black properties requires a small number (O(log n) or amortized O(1)) of color changes (which are very quick in practice) and no more than three tree rotations (two for insertion). |

And this is answer to my question

Topic archived. No new replies allowed.