erase(k) in the C++ Standard?

[desktop]

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.

 

[Zeppe]

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?

As usual: because you perform the search only one time?

Regards,

Zeppe

 

[desktop]

As usual: because you perform the search only one time?

Regards,

Zeppe

Ok so the search takes log(size()) time and then it takes count(k) time
to do the deletion?

Is it correct that size() = number of elements in the container? I don't
think they specify the size() in §23.

 

[Dizzy]

Ok so the search takes log(size()) time and then it takes count(k) time
to do the deletion?

Exactly (imagine the implementation using a tree to search for the key then
traversing all elements equal in the multiset/map which is a liniar
traversal of the number of elements equal for that key).

Is it correct that size() = number of elements in the container? I don't
think they specify the size() in §23.

I think they mean "size()" as in the result returned by container.size() so
yes the number of elements in the container.

 

[dasjotre]

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

 

[=?ISO-8859-1?Q?Erik_Wikstr=F6m?=]

Ok so the search takes log(size()) time and then it takes count(k) time
to do the deletion?

Is it correct that size() = number of elements in the container? I don't
think they specify the size() in §23.

Table 65, §23.1