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

### 2542. Missing `const` requirements for associative containers

Section: 22.2.6 [associative.reqmts] Status: C++17 Submitter: Daniel Krügler Opened: 2015-09-26 Last modified: 2017-07-30

Priority: 1

View other active issues in [associative.reqmts].

View all other issues in [associative.reqmts].

View all issues with C++17 status.

Discussion:

Table 101 — "Associative container requirements" and its associated legend paragraph 22.2.6 [associative.reqmts] p8 omits to impose constraints related to `const` values, contrary to unordered containers as specified by Table 102 and its associated legend paragraph p11.

Reading these requirements strictly, a feasible associative container could declare several conceptual observer members — for example `key_comp()`, `value_comp()`, or `count()` — as non-`const` functions. In Table 102, "possibly `const`" values are exposed by different symbols, so the situation for unordered containers is clear that these functions may be invoked by `const` container objects.

For the above mentioned member functions this problem is only minor, because the synopses of the actual Standard associative containers do declare these members as `const` functions, but nonetheless a wording fix is recommended to clean up the specification asymmetry between associative containers and unordered containers.

The consequences of the ignorance of `const` becomes much worse when we consider a code example such as the following one from a recent libstdc++ bug report:

>     #include <set>

>     struct compare
>     {
>       bool operator()(int a, int b) // Notice the non-const member declaration!
>       {
>         return a < b;
>       }
>     };

>     int main() {
>       const std::set<int, compare> s;
>       s.find(0);
>     }

The current wording in 22.2.6 [associative.reqmts] can be read to require this code to be well-formed, because there is no requirement that an object `comp` of the ordering relation of type `Compare` might be a `const` value when the function call expression `comp(k1, k2)` is evaluated.

Current implementations differ: While Clangs libc++ and GCCs libstdc++ reject the above example, the Dinkumware library associated with Visual Studio 2015 accepts it.

I believe the current wording unintentionally misses the constraint that even `const` comparison function objects of associative containers need to support the predicate call expression. This becomes more obvious when considering the member `value_compare` of `std::map` which provides (only) a `const operator()` overload which invokes the call expression of data member `comp`.

[2016-02-20, Daniel comments and extends suggested wording]

It has been pointed out to me, that the suggested wording is a potentially breaking change and should therefore be mentioned in Annex C.

First, let me emphasize that this potentially breaking change is solely caused by the wording change in 22.2.6 [associative.reqmts] p8:

> […] and `c` denotes a possibly `const` value of type `X::key_compare`; […]

So, even if that proposal would be rejected, the rest of the suggested changes could (and should) be considered for further evaluation, because the remaining parts do just repair an obvious mismatch between the concrete associative containers (`std::set`, `std::map`, …) and the requirement tables.

Second, I believe that the existing wording was never really clear in regard to require a Standard Library to accept comparison functors with non-`const operator()`. If the committee really intends to require a Library to support comparison functors with non-`const operator()`, this should be clarified by at least an additional note to e.g. 22.2.6 [associative.reqmts] p8.

[2016-03, Jacksonville]

Move to Ready with Daniel's updated wording

Proposed resolution:

This wording is relative to N4567.

1. Change 22.2.6 [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`, `u` denotes the name of a variable being declared, `a_uniq` denotes a value of type `X` when `X` supports unique keys, `a_eq` denotes a value of type `X` when `X` supports multiple keys, `a_tran` denotes a possibly `const` value of type `X` when the qualified-id `X::key_compare::is_transparent` is valid and denotes a type (14.8.2), `i` and `j` satisfy input iterator requirements and refer to elements implicitly convertible to `value_type`, `[i, j)` denotes a valid range, `p` denotes a valid const iterator to `a`, `q` denotes a valid dereferenceable const iterator to `a`, `r` denotes a valid dereferenceable iterator to `a`, `[q1, q2)` denotes a valid range of const iterators in `a`, `il` designates an object of type `initializer_list<value_type>`, `t` denotes a value of type `X::value_type`, `k` denotes a value of type `X::key_type` and `c` denotes a possibly `const` value of type `X::key_compare`; `kl` is a value such that `a` is partitioned (25.4) with respect to `c(r, kl)`, with `r` the key value of `e` and `e` in `a`; `ku` is a value such that `a` is partitioned with respect to `!c(ku, r)`; `ke` is a value such that `a` is partitioned with respect to `c(r, ke)` and `!c(ke, r)`, with `c(r, ke)` implying `!c(ke, r)`. `A` denotes the storage allocator used by `X`, if any, or `std::allocator<X::value_type>` otherwise, and `m` denotes an allocator of a type convertible to `A`.

2. Change 22.2.6 [associative.reqmts], Table 101 — "Associative container requirements" as indicated:

   [Editorial note: This issue doesn't touch the note column entries for the expressions related to `key_comp()` and `value_comp()` (except for the symbolic correction), since these are already handled by LWG issues 2227 and 2215 — end editorial note]

   > Table 101 — Associative container requirements (in addition to container) (continued)
   > Expression | Return type | Assertion/note pre-/post-condition | Complexity
   > --- | --- | --- | ---
   > `…`
   > `ab.key_comp()` | `X::key_compare` | returns the comparison object out of which `ab` was constructed. | constant
   > `ab.value_comp()` | `X::value_compare` | returns an object of `value_compare` constructed out of the comparison object | constant
   > `…`
   > `ab.find(k)` | `iterator`; `const_iterator` for constant `ab`. | returns an iterator pointing to an element with the key equivalent to `k`, or `ab.end()` if such an element is not found | logarithmic
   > `…`
   > `ab.count(k)` | `size_type` | returns the number of elements with key equivalent to `k` | `log(ab.size()) + ab.count(k)`
   > `…`
   > `ab.lower_bound(k)` | `iterator`; `const_iterator` for constant `ab`. | returns an iterator pointing to the first element with key not less than `k`, or `ab.end()` if such an element is not found. | logarithmic
   > `…`
   > `ab.upper_bound(k)` | `iterator`; `const_iterator` for constant `ab`. | returns an iterator pointing to the first element with key greater than `k`, or `ab.end()` if such an element is not found. | logarithmic
   > `…`
   > `ab.equal_range(k)` | `pair<iterator, iterator>`; `pair<const_iterator, const_iterator>` for constant a b. | equivalent to `make_- pair(ab.lower_bound(k), ab.upper_bound(k))`. | logarithmic
   > `…`

3. Add a new entry to Annex C, C.3 [diff.cpp14], as indicated:

   > C.4.4 Clause 23: containers library [diff.cpp14.containers]

   > 23.2.4

   > Change: Requirements change:

   > Rationale: Increase portability, clarification of associative container requirements.

   > Effect on original feature: Valid 2014 code that attempts to use associative containers having a comparison object with non-`const` function call operator may fail to compile:

   > >     #include <set>

   > >     struct compare
   > >     {
   > >       bool operator()(int a, int b)
   > >       {
   > >         return a < b;
   > >       }
   > >     };

   > >     int main() {
   > >       const std::set<int, compare> s;
   > >       s.find(0);
   > >     }