Std :: set anomaly complexity erase?

Question

I am trying to find out the difficulty of erasing multiple elements from std :: set. I use this page as a source.

He claims that the complexity of erasing a single element using an iterator is amortized by O (1), but deleting multiple elements using a range form is log (c.size ()) + std :: distance (first, last) (i.e. - log of a given size + the number of deleted items).

Taken at face value, if the number of elements to be erased (n) is much less than the number of elements in the set (m), this means that the cycle through the elements to be erased and erasing them one time is faster (O (n)) than erasing them in one call (O (log m) taking n <m).

Obviously, if this were true, the internal implementation of the second form would simply do the above cycle.

Is this a mistake on the site? Error in the specifications? Did I miss something?

Thanks, Shahar

Answer 1

It seems that the problem is hidden behind the (somewhat affectionate) word "amortized." The only element removal has complexity O log (c.size ()), but the amortized complexity O (1).

Performing several single erasures in a loop will thus be log log (c.size ()) + the number of erasures, which is the complexity of the shape of the range.

Shahar

Answer 2

Internally, set items are stored in a balanced binary tree. A balanced tree is a tree in which the maximum height difference between any left and right subtree of any node is 1.

Maintaining a balanced structure is important to ensure that finding any item in a tree (in a set) in the worst case O(log(n)) steps.

Removing an item may upset the balance. To restore balance, rotations must be performed. In some cases, one deletion leads to several turns, so the operation takes O(log(n)) steps, but on average it takes O(1) steps.

Thus, when several items scattered across a set must be deleted one after another, the amortized cost is likely to be O(1) for deletion.

Deleting several elements in the range ( first, last , where one element follows the next) will almost certainly destroy the balance, which will make the logarithmic coefficient difficult: log(n) + std::distance(first, last)