By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
424,988 Members | 1,049 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 424,988 IT Pros & Developers. It's quick & easy.

erase(k) in the C++ Standard?

P: n/a
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.
Jun 18 '07 #1
Share this Question
Share on Google+
5 Replies


P: n/a
desktop wrote:
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
Jun 18 '07 #2

P: n/a
Zeppe wrote:
desktop wrote:
>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
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.
Jun 18 '07 #3

P: n/a
desktop wrote:
Zeppe wrote:
>desktop wrote:
>>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

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.

--
Dizzy

Jun 18 '07 #4

P: n/a
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

Jun 18 '07 #5

P: n/a
On 2007-06-18 13:36, desktop wrote:
Zeppe wrote:
>desktop wrote:
>>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

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

--
Erik Wikström
Jun 18 '07 #6

This discussion thread is closed

Replies have been disabled for this discussion.