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.
Section: 24.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(i) and to an inconsistency of requirements on keys in ordered and unordered associative containers:
1) 103(i) introduced the term immutable without defining it in a unique manner in 24.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(i) 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 24.2.7 [associative.reqmts]/6 that "both
iterator
andconst_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 thehasher
andkey_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(i) 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:
Change 24.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 24.2.8 [unord.req]/3]
2 Each associative container is parameterized on
Key
and an ordering relationCompare
that induces a strict weak ordering (25.4) on elements ofKey
. In addition,map
andmultimap
associate an arbitrary mapped typetypeT
with theKey
. The object of typeCompare
is called the comparison object of a container.
Change 24.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 24.2.8 [unord.req]/7. We take care about the real constraints by the remaining suggested changes. The rationale provided by LWG 103(i) 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
andmultiset
the value type is the same as the key type. Formap
andmultimap
it is equal topair<const Key, T>
.Keys in an associative container are immutable.
Change 24.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 typeHash
that meets theHash
requirements (20.2.4) and acts as a hash function for argument values of typeKey
, and by a binary predicatePred
that induces an equivalence relation on values of typeKey
. Additionally,unordered_map
andunordered_multimap
associate an arbitrary mapped typeT
with theKey
.4 The container's object of type
Hash
- denoted byhash
- is called the hash function of the container. The container's object of typePred
- denoted bypred
- 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 typestd::size_t
Change 24.2.8 [unord.req]/5 as indicated: [This adds a similar safe-guard as the last sentence of 24.2.7 [associative.reqmts]/3]
5 Two values
k1
andk2
of typeKey
are considered equivalent if the container's key equality predicatereturnskey_equal
function objecttrue
when passed those values. Ifk1
andk2
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-defaultPred
parameter it usually needs a non-defaultHash
parameter as well. — end note] For any two keysk1
andk2
in the same container, callingpred(k1, k2)
shall always return the same value. For any keyk
in a container, callinghash(k)
shall always return the same value.
After 24.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
andunordered_multiset
the value type is the same as the key type. Forunordered_map
andunordered_multimap
it isstd::pair<const Key, T>
.For unordered containers where the value type is the same as the key type, both
iterator
andconst_iterator
are constant iterators. It is unspecified whether or notiterator
andconst_iterator
are the same type. [Note:iterator
andconst_iterator
have identical semantics in this case, anditerator
is convertible toconst_iterator
. Users can avoid violating the One Definition Rule by always usingconst_iterator
in their function parameter lists. — end note]