2436. Comparators for associative containers should always be CopyConstructible

Section: 23.2.7 [associative.reqmts], 23.2.8 [unord.req] Status: C++17 Submitter: Stephan T. Lavavej Opened: 2014-10-01 Last modified: 2018-06-23

Priority: 2

View other active issues in [associative.reqmts].

View all other issues in [associative.reqmts].

View all issues with C++17 status.

Discussion:

The associative container requirements attempt to permit comparators that are DefaultConstructible but non-CopyConstructible. However, the Standard contradicts itself. 23.4.3.1 [map.overview] depicts map() : map(Compare()) { } which requires both DefaultConstructible and CopyConstructible.

Unlike fine-grained element requirements (which are burdensome for implementers, but valuable for users), such fine-grained comparator requirements are both burdensome for implementers (as the Standard's self-contradiction demonstrates) and worthless for users. We should unconditionally require CopyConstructible comparators. (Note that DefaultConstructible should remain optional; this is not problematic for implementers, and allows users to use lambdas.)

Key equality predicates for unordered associative containers are also affected. However, 16.4.4.5 [hash.requirements]/1 already requires hashers to be CopyConstructible, so 23.2.8 [unord.req]'s redundant wording should be removed.

[2015-02, Cologne]

GR: I prefer to say "Compare" rather than "X::key_compare", since the former is what the user supplies. JY: It makes sense to use "Compare" when we talk about requirements but "key_compare" when we use it.

AM: We're adding requirements here, which is a breaking change, even though nobody will ever have had a non-CopyConstructible comparator. But the simplification is probably worth it.

GR: I don't care about unmovable containers. But I do worry that people might want to move they comparators. MC: How do you reconcile that with the function that says "give me the comparator"? GR: That one returns by value? JY: Yes. [To MC] You make it a requirement of that function. [To GR] And it [the key_comp() function] is missing its requirements. We need to add them everywhere. GR: map already has the right requirements.

JM: I dispute this. If in C++98 a type wasn't copyable, it had some interesting internal state, but in C++98 you wouldn't have been able to pass it into the container since you would have had to make a copy. JY: No, you could have default-constructed it and never moved it, e.g. a mutex. AM: So, it's a design change, but one that we should make. That's probably an LEWG issue. AM: There's a contradiction in the Standard here, and we need to fix it one way or another.

Conclusion: Move to LEWG

[LEWG: 2016-03, Jacksonville]

Adding CopyConstructible requirement OK.

Unanimous yes.

We discussed allowing MoveConstructible. A moved-from set<> might still contain elements, and using them would become undefined if the comparator changed behavior.

Proposed resolution:

This wording is relative to N3936.

  1. Change 23.2.7 [associative.reqmts] Table 102 as indicated (Editorial note: For "expression" X::key_compare "defaults to" is redundant with the class definitions for map/etc.):

    Table 102 — Associative container requirements
    Expression Return type Assertion/note pre-/post-condition Complexity
    …
    X::key_compare Compare defaults to less<key_type>
    Requires: key_compare is CopyConstructible.     		compile time
    …
    X(c)
    X a(c);         		Requires: key_compare is CopyConstructible.
    Effects: Constructs an empty container. Uses a copy of c as a comparison object.     		constant
    …
    X(i,j,c)
    X a(i,j,c);         		Requires: key_compare is CopyConstructible.
    value_type is EmplaceConstructible into X from *i.
    Effects: Constructs […]     		[…]
    …

  2. Change 23.2.8 [unord.req] Table 103 as indicated:

    Table 103 — Unordered associative container requirements (in addition to container)
    Expression Return type Assertion/note pre-/post-condition Complexity
    …
    X::key_equal Pred Requires: Pred is CopyConstructible.
    Pred shall be a binary predicate that takes two arguments of type Key.
    Pred is an equivalence relation.     		compile time
    …
    X(n, hf, eq)
    X a(n, hf, eq);         		X Requires: hasher and key_equal are CopyConstructible.
    Effects: Constructs […]     		[…]
    …
    X(n, hf)
    X a(n, hf);         		X Requires: hasher is CopyConstructible and
    key_equal is DefaultConstructible
    Effects: Constructs […]     		[…]
    …
    X(i, j, n, hf, eq)
    X a(i, j, n, hf, eq);         		X Requires: hasher and key_equal are CopyConstructible.
    value_type is EmplaceConstructible into X from *i.
    Effects: Constructs […]     		[…]
    …
    X(i, j, n, hf)
    X a(i, j, n, hf);         		X Requires: hasher is CopyConstructible and
    key_equal is DefaultConstructible
    value_type is EmplaceConstructible into X from *i.
    Effects: Constructs […]     		[…]
    …