On 18 Jun, 12:22, desktop <f...@sss.comwrote:

In the C++ standard table 69 erase(k) is said to take log(size()) +

count(k).

If there are 4 keys satisfying k we have that count(k) = 4 so why is the

complexity not count(k)*log(size()), since we have to erase count(k)

elements?

Where I assume size() is equal to the number of elements in the tree.

complexity of find must be logarithmic, that is log(size())

IMHO, what standard says there is that the complexity of erasing all

elements with the same key, once you know where the first one

is, must not be greater than count(k) (that is complexity

must be linear).

so for the complete operation (find the first one and erase all with

the same key) complexity must not exceed log(size()) + count(k)

not log(size()) * count(k).

regards

DS