Talk:cpp/container/unordered multimap/count
From cppreference.com
[edit] Complexity
Any reasonable implementation will have complexity:
Linear in number of matches, worst case linear in the size of the container.
- Yes, the standard requirement is O(1) complexity (Table 103 — Unordered associative container requirements), but the two implementations I just looked at execute one hash lookup followed by as many equality comparisons as there are elements with the given key. I added a non-normative note. --Cubbi (talk) 06:54, 31 December 2013 (PST)
