103. set::iterator is required to be modifiable, but this allows modification of keys

Section: 23.2.7 [associative.reqmts] Status: CD1 Submitter: AFNOR Opened: 1998-10-07 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 CD1 status.

Discussion:

Set::iterator is described as implementation-defined with a reference to the container requirement; the container requirement says that const_iterator is an iterator pointing to const T and iterator an iterator pointing to T.

23.1.2 paragraph 2 implies that the keys should not be modified to break the ordering of elements. But that is not clearly specified. Especially considering that the current standard requires that iterator for associative containers be different from const_iterator. Set, for example, has the following:

typedef implementation defined iterator;
       // See _lib.container.requirements_

23.2 [container.requirements] actually requires that iterator type pointing to T (table 65). Disallowing user modification of keys by changing the standard to require an iterator for associative container to be the same as const_iterator would be overkill since that will unnecessarily significantly restrict the usage of associative container. A class to be used as elements of set, for example, can no longer be modified easily without either redesigning the class (using mutable on fields that have nothing to do with ordering), or using const_cast, which defeats requiring iterator to be const_iterator. The proposed solution goes in line with trusting user knows what he is doing.

Other Options Evaluated:

Option A.   In 23.2.7 [associative.reqmts], paragraph 2, after first sentence, and before "In addition,...", add one line:

Modification of keys shall not change their strict weak ordering.

Option B. Add three new sentences to 23.2.7 [associative.reqmts]:

At the end of paragraph 5: "Keys in an associative container are immutable." At the end of paragraph 6: "For associative 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."

Option C. To 23.2.7 [associative.reqmts], paragraph 3, which currently reads:

The phrase ``equivalence of keys'' means the equivalence relation imposed by the comparison and not the operator== on keys. That is, two keys k1 and k2 in the same container are considered to be equivalent if for the comparison object comp, comp(k1, k2) == false && comp(k2, k1) == false.

  add the following:

For any two keys k1 and k2 in the same container, comp(k1, k2) shall return the same value whenever it is evaluated. [Note: If k2 is removed from the container and later reinserted, comp(k1, k2) must still return a consistent value but this value may be different than it was the first time k1 and k2 were in the same container. This is intended to allow usage like a string key that contains a filename, where comp compares file contents; if k2 is removed, the file is changed, and the same k2 (filename) is reinserted, comp(k1, k2) must again return a consistent value but this value may be different than it was the previous time k2 was in the container.]

Proposed resolution:

Add the following to 23.2.7 [associative.reqmts] at the indicated location:

At the end of paragraph 3: "For any two keys k1 and k2 in the same container, calling comp(k1, k2) shall always return the same value."

At the end of paragraph 5: "Keys in an associative container are immutable."

At the end of paragraph 6: "For associative 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."

Rationale:

Several arguments were advanced for and against allowing set elements to be mutable as long as the ordering was not effected. The argument which swayed the LWG was one of safety; if elements were mutable, there would be no compile-time way to detect of a simple user oversight which caused ordering to be modified. There was a report that this had actually happened in practice, and had been painful to diagnose. If users need to modify elements, it is possible to use mutable members or const_cast.

Simply requiring that keys be immutable is not sufficient, because the comparison object may indirectly (via pointers) operate on values outside of the keys.

The types iterator and const_iterator are permitted to be different types to allow for potential future work in which some member functions might be overloaded between the two types. No such member functions exist now, and the LWG believes that user functionality will not be impaired by permitting the two types to be the same. A function that operates on both iterator types can be defined for const_iterator alone, and can rely on the automatic conversion from iterator to const_iterator.

[Tokyo: The LWG crafted the proposed resolution and rationale.]