I was reading this and from what I can get is that unordered_map practically works linear in number of elements number of buckets.

So, let's say, I have code, which

1. adds arbitrary number of elements to std::unordered_map

2. then clear() the std::unordered_map

3. repeat this multiple times.

If I had lot of elements at any point of the total execution (in step 1), the clear time will carry-on in future also, making code slow.

But, is this same issue also with std::map?

Thanks

CodePudding user response：

When will std::map::clear() going to be faster that std::unordered_map::clear()?

Both have linear asymptotic complexity. You can time your code using both to see if either is measurably faster.

Note that if the destructor of the element is non-trivial, then clear of all containers has linear complexity. If the destructor is trivial, then the only standard containers that have less than linear complexity of clear are std::vector and std::basic_string.

Regarding the case of:

• grow container large
• clear
• insert few
• clear

The cost of latter clear being high that applies to std::unordered_map is not a problem that reproduces with std::map.