Title
Wording of unordered container's clear() method complexity
Status
c++17
Section
[unord.req]
Submitter
Yegor Derevenets

Created on 2015-10-11.00:00:00 last changed 81 months ago

Messages

Date: 2016-03-07.06:00:57

Proposed resolution:

This wording is relative to N4527.

  1. Change [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().
Date: 2016-03-07.06:00:57

[ 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.

Date: 2015-10-11.00:00:00

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 [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.

History
Date User Action Args
2017-07-30 20:15:43adminsetstatus: wp -> c++17
2016-06-28 12:47:21adminsetstatus: ready -> wp
2016-03-07 06:00:57adminsetmessages: + msg8016
2016-03-07 06:00:57adminsetstatus: new -> ready
2015-10-29 19:12:23adminsetmessages: + msg7590
2015-10-11 00:00:00admincreate