1214. Insufficient/inconsistent key immutability requirements for associative containers

Section: 23.2.7 [associative.reqmts] Status: C++14 Submitter: Daniel Krügler Opened: 2009-09-20 Last modified: 2016-01-28

Priority: Not Prioritized

View other active issues in [associative.reqmts].

View all other issues in [associative.reqmts].

View all issues with C++14 status.

Discussion:

Scott Meyers' mentions on a recent posting on c.s.c++ some arguments that point to an incomplete resolution of 103 and to an inconsistency of requirements on keys in ordered and unordered associative containers:

1) 103 introduced the term immutable without defining it in a unique manner in 23.2.7 [associative.reqmts]/5:

[..] Keys in an associative container are immutable.

According to conventional dictionaries immutable is an unconditional way of saying that something cannot be changed. So without any further explicit allowance a user always runs into undefined behavior if (s)he attempts to modify such a key. IMO this was not the intend of the committee to resolve 103 in that way because the comments suggest an interpretation that should give any user the freedom to modify the key in an explicit way provided it would not affect the sort order in that container.

2) Another observation was that surprisingly no similar 'safety guards' exists against unintentional key changes for the unordered associative containers, specifically there is no such requirement as in 23.2.7 [associative.reqmts]/6 that "both iterator and const_iterator are constant iterators". But the need for such protection against unintentional changes as well as the constraints in which manner any explicit changes may be performed are both missing and necessary, because such changes could potentially change the equivalence of keys that is measured by the hasher and key_equal.

I suggest to fix the unconditional wording involved with "immutable keys" by at least adding a hint for the reader that users may perform such changes in an explicit manner and to perform similar wording changes as 103 did for the ordered associative containers also for the unordered containers.

[ 2010-03-27 Daniel provides wording. ]

This update attempts to provide normative wording that harmonizes the key and function object constraints of associative and unordered containers.

[ 2010 Batavia: ]

We're uncomfortable with the first agenda item, and we can live with the second agenda item being applied before or after Madrid.

[ 2011 Bloomington ]

Further discussion persuades us this issue is Ready (and so moved). We may need a further issue clarifying the notion of key value vs. key object, as object identity appears to be important to this wording.

Proposed resolution:

  1. Change 23.2.7 [associative.reqmts]/2 as indicated: [This ensures that associative containers make better clear what this "arbitrary" type is, as the unordered containers do in 23.2.8 [unord.req]/3]

    2 Each associative container is parameterized on Key and an ordering relation Compare that induces a strict weak ordering (25.4) on elements of Key. In addition, map and multimap associate an arbitrary mapped typetype T with the Key. The object of type Compare is called the comparison object of a container.

  2. Change 23.2.7 [associative.reqmts]/5 as indicated: [This removes the too strong requirement that keys must not be changed at all and brings this line in sync with 23.2.8 [unord.req]/7. We take care about the real constraints by the remaining suggested changes. The rationale provided by LWG 103 didn't really argue why that addition is necessary, and I believe the remaining additions make it clear that any user changes have strong restrictions]:

    5 For set and multiset the value type is the same as the key type. For map and multimap it is equal to pair<const Key, T>. Keys in an associative container are immutable.

  3. Change 23.2.8 [unord.req]/3+4 as indicated: [The current sentence of p.4 has doesn't say something really new and this whole subclause misses to define the concepts of the container-specific hasher object and predicate object. We introduce the term key equality predicate which is already used in the requirements table. This change does not really correct part of this issue, but is recommended to better clarify the nomenclature and the difference between the function objects and the function object types, which is important, because both can potentially be stateful.]

    3 Each unordered associative container is parameterized by Key, by a function object type Hash that meets the Hash requirements (20.2.4) and acts as a hash function for argument values of type Key, and by a binary predicate Pred that induces an equivalence relation on values of type Key. Additionally, unordered_map and unordered_multimap associate an arbitrary mapped type T with the Key.

    4 The container's object of type Hash - denoted by hash - is called the hash function of the container. The container's object of type Pred - denoted by pred - is called the key equality predicate of the container.A hash function is a function object that takes a single argument of type Key and returns a value of type std::size_t.

  4. Change 23.2.8 [unord.req]/5 as indicated: [This adds a similar safe-guard as the last sentence of 23.2.7 [associative.reqmts]/3]

    5 Two values k1 and k2 of type Key are considered equivalent if the container's key equality predicatekey_equal function object returns true when passed those values. If k1 and k2 are equivalent, the container's hash function shall return the same value for both. [Note: thus, when an unordered associative container is instantiated with a non-default Pred parameter it usually needs a non-default Hash parameter as well. — end note] For any two keys k1 and k2 in the same container, calling pred(k1, k2) shall always return the same value. For any key k in a container, calling hash(k) shall always return the same value.

  5. After 23.2.8 [unord.req]/7 add the following new paragraph: [This ensures the same level of compile-time protection that we already require for associative containers. It is necessary for similar reasons, because any change in the stored key which would change it's equality relation to others or would change it's hash value such that it would no longer fall in the same bucket, would break the container invariants]

    7 For unordered_set and unordered_multiset the value type is the same as the key type. For unordered_map and unordered_multimap it is std::pair<const Key, T>.

    For unordered containers where the value type is the same as the key type, both iterator and const_iterator are constant iterators. It is unspecified whether or not iterator and const_iterator are the same type. [Note: iterator and const_iterator have identical semantics in this case, and iterator is convertible to const_iterator. Users can avoid violating the One Definition Rule by always using const_iterator in their function parameter lists. — end note]