2550. Wording of unordered container's clear() method complexity

Section: 23.2.8 [unord.req] Status: C++17 Submitter: Yegor Derevenets Opened: 2015-10-11 Last modified: 2017-07-30

Priority: 2

View other active issues in [unord.req].

View all other issues in [unord.req].

View all issues with C++17 status.

Discussion:

I believe, the wording of the complexity specification for the standard unordered containers' clear() method should be changed from "Linear" to "Linear in a.size()". As of N4527, the change should be done in the Complexity column of row "a.clear()..." in "Table 102 — Unordered associative container requirements" in section Unordered associative containers 23.2.8 [unord.req].

From the current formulation it is not very clear, whether the complexity is linear in the number of buckets, in the number of elements, or both. cppreference is also not very specific: it mentions the size of the container without being explicit about what exactly the size is.

The issue is inspired by a performance bug in libstdc++. The issue is related to LWG 1175.

[2016-03 Jacksonville]

GR: erase(begin. end) has to touch every element. clear() has the option of working with buckets instead. will be faster in some cases, slower in some. clear() has to be at least linear in size as it has to run destructors.
MC: wording needs to say what it's linear in, either elements or buckets.
HH: my vote is the proposed resolution is correct.
Move to Ready.

Proposed resolution:

This wording is relative to N4527.

1. Change 23.2.8 [unord.req], Table 102 as indicated:

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

   Expression	Return type	Assertion/note pre-/post-condition	Complexity
   …
   a.clear()	void	Erases all elements in the container. Post: a.empty() returns true	Linear in a.size().
   …