Issue 2304: Complexity of count in unordered associative containers

Title: Complexity of count in unordered associative containers
Status: c++14
Section: [unord.req]
Submitter: Joaquín M López Muñoz

Created on 2013-09-20.00:00:00 last changed 123 months ago

Messages

Date: 2014-02-13.15:14:54

Proposed resolution:

This wording is relative to N3691.

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()).

…

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()`).
`…`

msg6678 (view)

Date: 2014-02-13.15:14:54

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

msg6677 (view)

Date: 2013-09-20.00:00:00

Table 103 in [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.

History
Date	User	Action	Args
2014-02-28 13:44:27	admin	set	status: wp -> c++14
2014-02-20 13:52:38	admin	set	status: immediate -> wp
2014-02-13 15:14:54	admin	set	messages: + msg6840
2014-02-13 15:14:54	admin	set	status: new -> immediate
2013-10-06 21:37:06	admin	set	messages: + msg6678
2013-09-20 00:00:00	admin	create