Talk:cpp/container/unordered multimap/count

[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)