Issue 2227: Stateful comparison objects in associative containers

2227. Stateful comparison objects in associative containers

Section: 23.2.7 [associative.reqmts] Status: Open Submitter: Juan Soulie Opened: 2012-12-19 Last modified: 2019-04-23

Priority: 3

View other active issues in [associative.reqmts].

View all other issues in [associative.reqmts].

View all issues with Open status.

Discussion:

Table 102 in 23.2.7 [associative.reqmts]/8 states on expression a.key_comp() that it "returns the comparison object out of which a was constructed". At the same time, 23.2.2 [container.requirements.general]/8 states (starting in the third line) that "...Any Compare, Pred, or Hash objects belonging to a and b shall be swappable and shall be exchanged by unqualified calls to non-member swap...". This is problematic for any compliant implementation, since once swapped the container cannot return the comparison object out of which it was constructed unless incurring in storing an otherwise needless object.

The simple solution is to correct that statement in Table 102, but I believe this is part of a larger problem of underspecified behavior: The new standard has made an effort in regards to allocators and now fully specifies what happens to stateful allocator objects. It has even specified what happens to stateful hasher and key_equal members of unordered containers (they propagate), but it says nothing about stateful comparison objects of (ordered) associative containers, except for the statement in 23.2.2 [container.requirements.general]/8 referred above and only related to swap.

For example, it is unclear to me what is specified to happen on an assignment: should the comparison object be copied/moved along with the elements, or should the left-hand side object keep its own? Maybe this has been intentionally left unspecified with the purpose of compatibility with C++98, which I understand it specified that comparison objects were kept for the entire life of the container (like allocators) — an unfortunate choice. But anyway, the segment of 23.2.2 [container.requirements.general] quoted above seems to break any possible backwards compatibility with C++98 in this regard.

Therefore, taking into consideration consistency with how this is dealed with for unordered associative containers, I propose that Table 102 is modified as follows:

The row for expression a.key_comp() is changed so that its "assertion/note pre-/post-condition" reads "Returns a's comparison object."

A new row is added at the appropriate location (which I believe would be after "X(il)" row), with:

Table 102 — Associative container requirements (in addition to container)
Expression Return type Assertion/note pre-/post-condition Complexity

X(b) X a(b) X Copy constructor. In addition to
the requirements of Table 96, copies
the comparison object. Linear in b.size()

a = b X& Copy assignment operator. In addition to
the requirements of Table 96, copies the
comparison object. Linear in a.size() and b.size()

Table 102 — Associative container requirements (in addition to container)
Expression	Return type	Assertion/note pre-/post-condition	Complexity
`X(b) X a(b)`	`X`	Copy constructor. In addition to the requirements of Table 96, copies the comparison object.	Linear in `b.size()`
`a = b`	`X&`	Copy assignment operator. In addition to the requirements of Table 96, copies the comparison object.	Linear in `a.size()` and `b.size()`

[2013-03-15 Issues Teleconference]

Moved to Review.

[2013-04-18, Bristol]

STL: can't believe we don't specify this already. this is totally necessary

Alisdair: how does it do this? copy construction? assignment?

Also need it for move.

STL: we already specify this for constructing from a comparator, not during copy construction though.

Jonathan: don't like wording, should say "key_compare is CopyConstructible. Uses b.key_comp() as a comparison object."

STL: we get it right for unordered!

Jonathan: can't wordsmith this now, but I think implementations do the right thing.

Alisdair: not sure what right thing is for moves. Also we say nothing about propagating allocators to functors.

Moved to Open.

[2015-02 Cologne]

TK: There's no need for fine-grained propagate/not-propagate control. If you don't want to propagate the predicate, you can simply construct or insert from an iterator range.

VV: libstdc++ already implements the resolution of this issue.

GR: There are a couple of other problems. We don't specify move constructor and move assignment for maps. Those are just general.

TK: General container requirements already describe the semantics for {copy,move}-{construction,assignment}, so it doesn't seem that there's room for choice in std::map assignments. unordered_map is different, though.

[Note: Check what general container requirements say about container equality.]

DK will draft wording. The decision is to unambiguously make all {copy,move}-{construction,assignment} operations endow the LHS with the exact state of the RHS, including all predicates and hash function states.

Conclusion: Update wording, revisit later.

[2015-05-06 Lenexa: Waiting for updated wording]

Previous resolution [SUPERSEDED]:

This wording is relative to N3485.

Change Table 102 as indicated:

Table 102 — Associative container requirements (in addition to container)
Expression Return type Assertion/note pre-/post-condition Complexity

…

X(il) Same as X(il.begin(), il.end()). same as X(il.begin(), il.end()).

X(b) X a(b) Copy constructor. In addition to
the requirements of Table 96, copies
the comparison object. Linear in b.size()

a = b X& Copy assignment operator. In addition to
the requirements of Table 96, copies the
comparison object. Linear in a.size() and b.size()

…

a.key_comp() X::key_compare rReturns ~~the~~a's comparison object
~~out of which a was constructed.~~ constant

Table 102 — Associative container requirements (in addition to container)
Expression	Return type	Assertion/note pre-/post-condition	Complexity
`…`
`X(il)`		Same as `X(il.begin(), il.end())`.	same as `X(il.begin(), il.end())`.
`X(b) X a(b)`		Copy constructor. In addition to the requirements of Table 96, copies the comparison object.	Linear in `b.size()`
`a = b`	`X&`	Copy assignment operator. In addition to the requirements of Table 96, copies the comparison object.	Linear in `a.size()` and `b.size()`
`…`
`a.key_comp()`	`X::key_compare`	rReturns ~~the~~`a`'s comparison object ~~out of which a was constructed.~~	constant

[2015-10-19 Daniel comments and provides alternative wording]

The current standard is especially unclear in regard to what effects move operations of unordered/associative containers should have. We have one example that is standardized exactly in this way by looking at 23.6.4.3 [priqueue.cons.alloc] p7:

template <class Alloc> priority_queue(priority_queue&& q, const Alloc& a);
-7- Effects: Initializes c with std::move(q.c) as the first argument and a as the second argument, and initializes comp with std::move(q.comp)

A similarly comparable example are the move-operations of std::unique_ptr in regard to the deleter (when this is no a reference), which also respect move-capabilities of that function object.

We have wording from C++98 for associative containers (but not for unordered containers!) that was never adjusted to C++11 move-semantics in 23.2.7 [associative.reqmts] p12:

When an associative container is constructed by passing a comparison object the container shall not store a pointer or reference to the passed object, even if that object is passed by reference. When an associative container is copied, either through a copy constructor or an assignment operator, the target container shall then use the comparison object from the container being copied, as if that comparison object had been passed to the target container in its constructor.

The second sentence of this wording is problematic for several reasons:

It only talks about copy operations, not about move operations, except that the term "assignment" without leading "copy" is a bit ambigious (albeit it seems clear in the complete context).
It is not really clear how to interpret "as if that comparison object had been passed to the target container in its constructor" for an assignment operation. A possible but not conclusive interpretation could be that this is wording supporting a "copy-via-swap" idiom.
There does not exist similar wording for unordered containers, except that Table 102 provides entries for copy construction and copy assignment of the containers whose wording just talks of "copies" in either case.

Existing implementations differ already:

Visual Studio 2015 uses copy construction and copy assignment for the two copy operations but uses swap operations for the move operations.
GCC's libstdc++ performs copy construction and copy assignment for the two copy operations and for the two move operations, respectively
clang++'s libc++ performs copy/move construction and copy/move assignment for the corresponding four copy/move operations

The alternative wording provided below attempts to clarify that container copy/move operations perform the corresponding copy/move operations on the owned function objects.

In addition the wording also resolves LWG 2215: I believe that the current wording should require that container function objects should meet the CopyConstructible requirements. Adding this general requirement also fixes the underspecified requirements of the accessor functions key_comp() and value_comp().

I don't think that a general requirement for Swappable is needed, only the member swap function currently requires this. Nonetheless the wording below does support stateful functors that are also moveable or move-assignable, therefore the specified semantics in terms of move operations.

I should add the following warning, though: If this proposed wording would be accepted, there is a little chance of code breakage, because the current wording can be read that in general there is no requirement that the container functors are CopyConstructible. The following code example is accepted by gcc + libstd++:

#include <map>
#include <utility>
#include <iostream>

struct Cmp {
  Cmp() = default;
  Cmp(const Cmp&) = delete;
  Cmp(Cmp&&) = delete;
  Cmp& operator=(const Cmp&) = delete;
  Cmp& operator=(Cmp&&) = delete;
  template<class T>
  bool operator()(const T& x, const T& y) const
  {
    return x < y;
  }
};

typedef std::map<int, int, Cmp> MyMap;

int main() {
  MyMap m;
  std::cout << (m.find(12) == m.end()) << std::endl;
}

Previous resolution [SUPERSEDED]:

This wording is relative to N4527.

Change 23.2.7 [associative.reqmts] p8 as indicated:

-8- In Table 101, X denotes an associative container class, a denotes a value of type X, b denotes a possibly const value of type X, rv denotes a non-const rvalue of type X, u denotes the name of a variable being declared, […]

Change Table 101 as indicated:

Table 101 — Associative container requirements (in addition to container)
Expression Return type Assertion/note pre-/post-condition Complexity

…

X::key_compare Compare Requires: Compare is CopyConstructible.
defaults to less<key_type> compile time

X(c) X u(c); Requires: key_compare is CopyConstructible.
Effects: Constructs an empty container.
Uses a copy of c as a comparison object. […]

…

X(i,j,c) X u(i,j,c); Requires: ~~key_compare is CopyConstructible.~~
value_type is EmplaceConstructible into X from *i.
Effects: Constructs an empty container and inserts elements
from the range [i, j) into it; uses c as a comparison object. […]

…

X(il) Same as X(il.begin(), il.end()). same as X(il.begin(), il.end()).

X(b) X a(b) (In addition to the requirements of Table 95)
Effects: Copy constructs the comparison object of a from
the comparison object of b. Linear in b.size()

X(rv) X a(rv) (In addition to the requirements of Table 95 and Table 98)
Effects: Move constructs the comparison object of a from
the comparison object of rv. constant

a = b X& (In addition to the requirements of Table 95 and Table 98)
Requires: key_compare is CopyAssignable.
Effects: Copy assigns the comparison object of b
to the comparison object of a. Linear in a.size() and b.size()

a = rv X& (In addition to the requirements of Table 95 and Table 98)
Requires: key_compare is MoveAssignable.
Effects: Move assigns from the comparison object of rv
to the comparison object of a. Linear

…

a.key_comp() X::key_compare rReturns ~~the~~a's comparison object
~~out of which a was constructed.~~ constant

Change 23.2.7 [associative.reqmts] p12 as indicated:

-12- When an associative container is constructed by passing a comparison object the container shall not store a pointer or reference to the passed object, even if that object is passed by reference. When an associative container is copied, either through a copy constructor or an assignment operator, the target container shall then use the comparison object from the container being copied, as if that comparison object had been passed to the target container in its constructor.

Change 23.2.8 [unord.req] p11 as indicated:

-11- In Table 102: X denotes an unordered associative container class, a denotes a value of type X, b denotes a possibly const value of type X, rv denotes a non-const rvalue of type X, […]

Change Table 102 as indicated:

Table 102 — Unordered associative container requirements (in addition to container)
Expression Return type Assertion/note pre-/post-condition Complexity

…

X::hasher Hash Requires: Hash is CopyConstructible.
Hash shall be a unary function object type
such that the expression hf(k) has type std::size_t. compile time

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: […] […]

X(n, hf) X a(n, hf) X Requires: ~~hasher is CopyConstructible and~~
key_equal is DefaultConstructible.
Effects: […] […]

…

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: […] […]

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: […] […]

…

X(b) X a(b) X Copy constructor. In addition
to the requirements of Table 95,
copies the hash function,
predicate, and maximum load
factor. (In addition to the requirements of Table 95)
Effects: Copy constructs the hash function, predicate, and maximum load factor
of a from the corresponding objects of b. Average case linear in
b.size(),
worst case quadratic.

X(rv) X a(rv) X (In addition to the requirements of Table 95 and Table 98)
Effects: Move constructs the hash function, predicate, and maximum load factor
of a from the corresponding objects of rv. constant

a = b X& Copy assignment operator. In
addition to the requirements of
Table 95, copies the hash
function, predicate, and
maximum load factor. (In addition to the requirements of Table 95 and Table 98)
Requires: hasher and key_equal are CopyAssignable.
Effects: Copy assigns the hash function, predicate, and maximum load factor
of b to the corresponding objects of a. Average case linear in
b.size(),
worst case quadratic.

a = rv X& (In addition to the requirements of Table 95 and Table 98)
Requires: hasher and key_equal are MoveAssignable.
Effects: Move assigns the hash function, predicate, and maximum load factor
from rv to the corresponding objects of a. Linear

…

Table 101 — Associative container requirements (in addition to container)
Expression	Return type	Assertion/note pre-/post-condition	Complexity
`…`
`X::key_compare`	`Compare`	Requires: `Compare` is `CopyConstructible`. defaults to `less<key_type>`	compile time
`X(c) X u(c);`		Requires: `key_compare` is `CopyConstructible`. Effects: Constructs an empty container. Uses a copy of `c` as a comparison object.	[…]
`…`
`X(i,j,c) X u(i,j,c);`		Requires: ~~`key_compare` is `CopyConstructible`.~~ `value_type` is `EmplaceConstructible` into `X` from `i`. Effects*: Constructs an empty container and inserts elements from the range `[i, j)` into it; uses `c` as a comparison object.	[…]
`…`
`X(il)`		Same as `X(il.begin(), il.end())`.	same as `X(il.begin(), il.end())`.
`X(b) X a(b)`		(In addition to the requirements of Table 95) Effects: Copy constructs the comparison object of `a` from the comparison object of `b`.	Linear in `b.size()`
`X(rv) X a(rv)`		(In addition to the requirements of Table 95 and Table 98) Effects: Move constructs the comparison object of `a` from the comparison object of `rv`.	constant
`a = b`	`X&`	(In addition to the requirements of Table 95 and Table 98) Requires: `key_compare` is `CopyAssignable`. Effects: Copy assigns the comparison object of `b` to the comparison object of `a`.	Linear in `a.size()` and `b.size()`
`a = rv`	`X&`	(In addition to the requirements of Table 95 and Table 98) Requires: `key_compare` is `MoveAssignable`. Effects: Move assigns from the comparison object of `rv` to the comparison object of `a`.	Linear
`…`
`a.key_comp()`	`X::key_compare`	rReturns ~~the~~`a`'s comparison object ~~out of which a was constructed.~~	constant

Table 102 — Unordered associative container requirements (in addition to container)
Expression	Return type	Assertion/note pre-/post-condition	Complexity
`…`
`X::hasher`	`Hash`	Requires: `Hash` is `CopyConstructible`. `Hash` shall be a unary function object type such that the expression `hf(k)` has type `std::size_t`.	compile time
`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: […]	[…]
`X(n, hf) X a(n, hf)`	`X`	Requires: ~~`hasher` is `CopyConstructible` and~~ `key_equal` is `DefaultConstructible`. Effects: […]	[…]
`…`
`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*: […]	[…]
`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*: […]	[…]
`…`
`X(b) X a(b)`	`X`	Copy constructor. In addition to the requirements of Table 95, copies the hash function, predicate, and maximum load factor. (In addition to the requirements of Table 95) Effects: Copy constructs the hash function, predicate, and maximum load factor of `a` from the corresponding objects of `b`.	Average case linear in `b.size()`, worst case quadratic.
`X(rv) X a(rv)`	`X`	(In addition to the requirements of Table 95 and Table 98) Effects: Move constructs the hash function, predicate, and maximum load factor of `a` from the corresponding objects of `rv`.	constant
`a = b`	`X&`	Copy assignment operator. In addition to the requirements of Table 95, copies the hash function, predicate, and maximum load factor. (In addition to the requirements of Table 95 and Table 98) Requires: `hasher` and `key_equal` are `CopyAssignable`. Effects: Copy assigns the hash function, predicate, and maximum load factor of `b` to the corresponding objects of `a`.	Average case linear in `b.size()`, worst case quadratic.
`a = rv`	`X&`	(In addition to the requirements of Table 95 and Table 98) Requires: `hasher` and `key_equal` are `MoveAssignable`. Effects: Move assigns the hash function, predicate, and maximum load factor from `rv` to the corresponding objects of `a`.	Linear
`…`

[2016-08-07]

Daniel removes the previously proposed wording to work on revised wording.

[2019-04-22, Billy comments]

In addition to the Cpp17CopyConstructible discussion going on there, I think we need to require that calling the comparison function when Compare itself is const needs to produce the same answer as if Compare is non-const.

Proposed resolution: