2542. Missing const requirements for associative containers

Section: 23.2.7 [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 23.2.7 [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 23.2.7 [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 23.2.7 [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. 23.2.7 [associative.reqmts] p8.

[2016-03, Jacksonville]

Proposed resolution:

This wording is relative to N4567.

1. 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, 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 23.2.7 [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 ab.	equivalent to make_- pair(ab.lower_bound(k), ab.upper_bound(k)).	logarithmic
   …

3. Add a new entry to Annex C, C.4 [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);
   }