This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of Open status.

### 2227. Stateful comparison objects in associative containers

Section: 24.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 24.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, 24.2.2.1 [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 24.2.2.1 [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 24.2.2.1 [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()`

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

> 1. 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` | r Returns 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 24.6.7.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 24.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:

1. 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).

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

3. 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:

1. Visual Studio 2015 uses copy construction and copy assignment for the two copy operations but uses swap operations for the move operations.

2. GCC's libstdc++ performs copy construction and copy assignment for the two copy operations and for the two move operations, respectively

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

> 1. Change 24.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, […]

> 2. 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` | r Returns the `a`'s comparison object out of which a was constructed. | constant

> 3. Change 24.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.

> 4. Change 24.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`, […]

> 5. 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
>    > `…`

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