Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Showing content from https://cplusplus.github.io/LWG/issue2542 below:

Missing const requirements for associative containers

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.

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.

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

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

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

[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 … a b.key_comp() X::key_compare returns the comparison object
   out of which a b was
   constructed. constant a b.value_comp() X::value_compare returns an object of
   value_compare constructed
   out of the comparison object constant … a b.find(k) iterator;
   const_iterator for constant a b. returns an iterator pointing to
   an element with the key
   equivalent to k, or a b.end() if
   such an element is not found logarithmic … a b.count(k) size_type returns the number of elements
   with key equivalent to k log( a b.size()) + a b.count(k) … a b.lower_bound(k) iterator;
   const_iterator for constant a b. returns an iterator pointing to
   the first element with key not
   less than k, or a b.end() if such
   an element is not found. logarithmic … a b.upper_bound(k) iterator;
   const_iterator for constant a b. returns an iterator pointing to
   the first element with key
   greater than k, or a b.end() if
   such an element is not found. logarithmic … a b.equal_range(k) pair<iterator, iterator>;
   pair<const_iterator, const_iterator> for
   constant a b. equivalent to make_-
pair( a b.lower_bound(k),
a b.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);
   }
   

RetroSearch is an open source project built by @garambo | Open a GitHub Issue

Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo

HTML: 3.2 | Encoding: UTF-8 | Version: 0.7.4