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

### 1214. Insufficient/inconsistent key immutability requirements for associative containers

Section: 22.2.6 [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 22.2.6 [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 22.2.6 [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 22.2.6 [associative.reqmts]/2 as indicated: [This ensures that associative containers make better clear what this "arbitrary" type is, as the unordered containers do in 22.2.7 [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 type type `T` with the `Key`. The object of type `Compare` is called the comparison object of a container.

2. Change 22.2.6 [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 22.2.7 [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 22.2.7 [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 22.2.7 [unord.req]/5 as indicated: [This adds a similar safe-guard as the last sentence of 22.2.6 [associative.reqmts]/3]

   > 5 Two values `k1` and `k2` of type `Key` are considered equivalent if the container's key equality predicate `key_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 22.2.7 [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]