Movatterモバイル変換

This page is a snapshot from the LWG issues list, see theLibrary Active Issues List for more information and the meaning ofC++14 status.

2304. Complexity ofcount in unordered associative containers

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

Priority:0

View otheractive issues in [unord.req].

View all otherissues in [unord.req].

View all issues withC++14 status.

Discussion:

Table 103 in 23.2.8[unord.req] states that the complexity ofb.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 tok.	Average case 𝒪(1b.count(k)), worst case 𝒪(b.size()).
   …