std::map range erase complexity

Question

cppreference.com says that complexity of range erase of std::map is:

log(c.size()) + std::distance(first, last)

while erase for single element by iterator is amortized constant. So if I erase elements in a loop:

for( auto it = first; it != last; it = map.erase( it ) );

that should be linear on std::distance(first, last), and cplusplus.com agrees with that. What does standard say? Is this just typo on cppreference.com?

Answer 1

log(c.size()) + std::distance(first, last)

When (first,last) is the entire range, that is the bigger factor, so this simplifies to std::distance(first, last), which is linear, so this is consistent with your thoughts.

it = map.erase( it ) is amortized constant. It's constant, plus a tiny bit for traversal and balancing. And when you add all those occasional tiny bits together over n iterations, they sum to something in log(c.size()). You still have to add these to the n constant-time erasures themselves, for a total of log(c.size()) + std::distance(first, last).

In either case, what you want to use is map.clear(), which is O(n) with a very small constant. It's far faster than erasing one at a time, since it can skip the balancing.

Answer 2

I only have the draft, but they are consistent with the draft:

a.erase(q1, q2)

Erases all the elements in the range [q1, q2)...

Complexity: log(a.size()) + N where N has the value distance(q1, q2).

n4594 Page 818.