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

Section: 26.2.7 [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 26.2.7 [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 26.2.7 [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().