2304. Complexity of count in unordered associative containers

Section: 23.2.8 [unord.req] Status: C++14 Submitter: Joaquín M López Muñoz Opened: 2013-09-20 Last modified: 2017-07-05

Priority: 0

View other active issues in [unord.req].

View all other issues in [unord.req].

View all issues with C++14 status.

Discussion:

Table 103 in 23.2.8 [unord.req] states that the complexity of b.count(k) is average case 𝒪(1) rather than linear with the number of equivalent elements, which seems to be a typo as this requires holding an internal count of elements in each group of equivalent keys, something which hardly looks the intent of the standard and no (known by the submitter) stdlib implementation is currently doing.

[Issaquah 2014-02-11: Move to Immediate]

Proposed resolution:

This wording is relative to N3691.

1. Change Table 103 as indicated:

   Table 103 — Unordered associative container requirements (in addition to container)

   Expression	Return type	Assertion/note pre-/post-condition	Complexity
   …
   b.count(k)	size_type	Returns the number of elements with key equivalent to k.	Average case 𝒪(1b.count(k)), worst case 𝒪(b.size()).
   …