Section: 16.4.4.3 [swappable.requirements], 23.2.2 [container.requirements.general] Status: LEWG Submitter: Robert Shearer Opened: 2012-04-13 Last modified: 2020-09-06
Priority: 3
View all other issues in [swappable.requirements].
View all issues with LEWG status.
Discussion:
Sub-clause 16.4.4.3 [swappable.requirements] defines two notions of swappability: a binary version defining when two objects are swappable with one another, and a unary notion defining whether an object is swappable (without qualification), with the latter definition requiring that the object satisfy the former with respect to all values of the same type.
LetT be a container type based on a non-propagating allocator whose instances do not necessarily
compare equal. Then sub-clause 23.2.2 [container.requirements.general] p7 implies that no object t
of type T is swappable (by the unary definition).
Throughout the standard it is the unary definition of "swappable" that is listed as a requirement (with the
exceptions of 22.2.2 [utility.swap] p4, 22.3.2 [pairs.pair] p31, 22.4.4.4 [tuple.swap] p2,
26.7.3 [alg.swap] p2, and 26.7.3 [alg.swap] p6, which use the binary definition). This renders
many of the mutating sequence algorithms of sub-clause 26.7 [alg.modifying.operations], for example,
inapplicable to sequences of standard container types, even where every element of the sequence is swappable
with every other.
Note that this concern extends beyond standard containers to all future allocator-based types.
Resolution proposal:
I see two distinct straightforward solutions:
I favor the latter solution, for reasons detailed in the following issue.
[ 2012-10 Portland: Move to Open ]
The issue is broader than containers with stateful allocotors, although they are the most obvious
example contained within the standard itself. The basic problem is that once you have a stateful
allocator, that does not propagate_on_swap, then whether two objects of this type can be
swapped with well defined behavior is a run-time property (the allocators compare equal) rather
than a simple compile-time property that can be deduced from the type. Strictly speaking, any
type where the nature of swap is a runtime property does not meet the swappable
requirements of C++11, although typical sequences of such types are going to have elements that
are all swappable with any other element in the sequence (using our other term of art
for specifying requirements) as the common case is a container of elements who all share the
same allocator.
The heart of the problem is that the swappable requirments demand that any two objects
of the same type be swappable with each other, so if any two such objects would not
be swappable with each other, then the whole type is never swappable. Many
algorithms in clause 25 are specified in terms of swappable which is essentially an
overspecification as all they actually need is that any element in the sequence is swappable
with any other element in the sequence.
At this point Howard joins the discussion and points out that the intent of introducing the
two swap-related terms was to support vector<bool>::reference types, and we are
reading something into the wording that was never intended. Consuses is that regardless of
the intent, that is what the words today say.
There is some support to see a paper reviewing the whole of clause 25 for this issue, and other select clauses as may be necessary.
There was some consideration to introducing a note into the front of clause 25 to indicate
swappable requirements in the clause should be interpreted to allow such awkward
types, but ultimately no real enthusiasm for introducing a swappable for clause 25
requirement term, especially if it confusingly had the same name as a term used with a
subtly different meaning through the rest of the standard.
There was no enthusiasm for the alternate resolution of requiring containers with unequal
allocators that do not propagate provide a well-defined swap behavior, as it is not
believed to be possible without giving swap linear complexity for such values,
and even then would require adding the constraint that the container element types are
CopyConstructible.
Final conclusion: move to open pending a paper from a party with a strong interest in stateful allocators.
[2016-03 Jacksonville]
Alisdair says that his paper P0178 addresses this.
[2016-06 Oulu]
P0178 reviewed, and sent back to LEWG for confirmation.
Thursday Morning: A joint LWG/LEWG meeting declined to adopt P0178.
[2017-02 in Kona, LEWG responds]
Note in the issue that this is tracked here
[2017-06-02 Issues Telecon]
Leave as LEWG; priority 3
Proposed resolution:
Apply P0178.