424,988 Members | 1,049 Online
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
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 isthe complexity not count(k)*log(size()), since we have to erasecount(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 isthe complexity not count(k)*log(size()), since we have to erasecount(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

 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 isthe complexity not count(k)*log(size()), since we have to erasecount(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.