What is the time complexity for a clear function is std::map according to big O?

Question

What is the time complexity for a clear function is std::map?
Would I be right in saying that it is O(1)?

Answer 1

The Standard says in [associative.reqmts]/8 Table 102:

a.clear() <=> a.erase(a.begin(), a.end()) linear in a.size()

So it is actually mandated to be O(N).

---

EDIT: summing up the various bits.

To remove a node, a map does two operation:

1. Call the allocator destroy method to destroy the element
2. Call the allocator deallocate method to deallocate the memory occupied by the node

The former can be elided in code (checking for is_trivially_destructible), and actually it is generally done in vector for example. The latter is unfortunately trickier, and no trait exists, so we must rely on the optimizer.

Unfortunately, even if by inlining the optimizer could completely remove the destroy and deallocate nodes, I am afraid it would not be able to realize that the tree traversal is now useless and optimize that away too. Therefore you would end up in a Θ(N) traversal of the tree and nothing done at each step...

Answer 2

The cplusplus reference site claims it has linear complexity in the container's size as the destructor of each element must be called.