With the removal of concepts, library issues 594 and 742 are no longer automatically solved via the concepts std::HasSwap and std::Swappable. This paper attempts to suggest a solution that has the nearest-possible effect as the concept solution had, but that is valid for non-template code or unconstrained template code as well. The proposal herein attempts to discard some unnecessary constraints and inconsistencies of the current Swappable requirements, as documented by the current wording within Table 37 ([swappable]):
The Swappable requirement is met by satisfying one or more of the following conditions:
- T is Swappable if T satisfies the MoveContructible requirements (Table 33) and the MoveAssignable requirements (Table 35);
- T is Swappable if a namespace scope function named swap exists in the same namespace as the definition of T, such that the expression swap(s, t) is valid and has the semantics described in this table.
- T is Swappable if T is an array type whose element type is Swappable.
The specific issues to be addressed are:
The approach used in this paper adapts the two concepts
auto concept HasSwap<typename T, typename U> {
void swap(T, U);
}
auto concept Swappable<typename T> : HasSwap<T&, T&> { }
to a wording form compatible with non-concept C++. Therefore this proposal defines some normative phrases as part of Table 37 — Swappable requirements [swappable] roughly as follows:
The first form uses expressions, matching the current style used in the library specification of requirements that need a finer granularity than named requirements like MoveConstructible, EqualityComparable, or Swappable would allow for. We also suggest a third form as a replacement for the degenerate situation
"std::declval<T>() is swappable" ⇔ "std::declval<T>() is swappable with std::declval<T>()"
because this special case occurs frequently in the library specification. [Note that this relation is not the same as Swappable<T>, because the former also supports the swapping of two rvalues]. One reviewer did not like this wording form of this shortcut, because it would shift the inherent binary relation of swappable to a unary relation. As a reply to this criticism two points are noteworthy:
"std::declval<T>() is self-swappable"
We did not suggest this wording form because most reviewers were fine with the "is swappable" form.
The equivalences shown above only roughly apply, because we cannot exactly simulate the special lookup rules for concept maps in a concept-free language. As an approximation to that lookup behavior, a lookup context is defined in an ADL-friendly way which allows for arrays, for all types that do not define their own swap function, and for all ADL-unaware types (the fundamental types) to find the two std::swap function templates from the header <utility>. Wording is carefully crafted to avoid requiring library implementors to include header <utility>, so that they are free to take advantage of their own internal header organization — only user code is required to include <utility> to realize the same thing. The following example demonstrates the well-known idiom for user code to realize a proper swappable context:
#include <utility>
namespace User {
// Requires: T shall satisfy the Swappable requirements.
template<class T>
void my_swap(T& t1, T& t2) {
using std::swap;
swap(t1, t2); // OK: Uses swappable conditions for lvalues of type T
}
}
At the March 2010 C++ meeting in Pittsburgh, a draft version of this paper was reviewed and enhanced in several ways.
Most importantly, it was realized that the Swappable requirement (even when updated as described above) is more constrained than appropriate for most of its uses. In particular, many standard algorithms require the type of an expression obtained by dereferencing an iterator to satisfy Swappable. When expressed as a requirement on the type of such an expression, it is not possible (or at least not simple) to allow for cases where dereferencing such an iterator yields an rvalue (in addition to the case where the dereferencing yields an lvalue).
Such iterators, which yield rvalues when dereferenced, are common in existing practice when the object returned needs to be a proxy of some kind (thus giving rise to the term proxy iterator). A simple example of such iterators in the standard library are those of vector<bool>.
To address this issue, the proposed wording was updated to introduce a new ValueSwappable requirement. Rather than stating a requirement on the types of these dereferenced iterator expressions, this requirement is instead intended to apply to the iterator type, and thus to place a restriction on the dereferencing expressions themselves. This allows simple wording that applies equally to applicable iterators whether they yield lvalues or rvalues.
Nearly all existing uses of the Swappable requirement can be replaced with a use of ValueSwappable instead. Where Swappable was previously listed as a requirement on a type not matching a dereferenced iterator expression, the phrase lvalues of type T shall be swappable is used instead, which most closely matches the intent of these cases.
In addition to the ValueSwappable requirement, the proposed resolution was updated to introduce a symmetry requirement on the swappable with construction. This ensures that swappable values behave as expected in certain scenarios.
Finally, some small improvements were made to fix editorial issues in the previous draft.
If the proposed resolution is accepted, the following library issues will be resolved:
| Number | Description |
|---|---|
| 594 | Disadvantages of defining Swappable in terms of CopyConstructible and Assignable |
| 742 | Enabling swap for proxy iterators |
In addition, we believe that accepting this proposal will allow easier resolution of library issue 774.
20.2.1 describes requirements on types and expressions used to instantiate templates defined in the C++ standard library. 20.2.2 describes the requirements on swappable types and swappable expressions. 20.2.3 describes the requirements on hash functions. 20.2.4 describes the requirements on storage allocators.
Table 37 — Swappable requirements [swappable]ExpressionReturn typePost-conditionswap(s, t)voidt has the value originally held by s and s has the value originally held by t
The Swappable requirement is met by satisfying one or more of the following conditions:
T is Swappable if T satisfies the MoveContructible requirements (Table 33) and the MoveAssignable requirements (Table 35);T is Swappable if a namespace scope function named swap exists in the same namespace as the definition of T, such that the expression swap(s, t) is valid and has the semantics described in this table.T is Swappable if T is an array type whose element type is Swappable.
20.2.2 Swappable requirements [swappable.requirements]
This subclause provides definitions for swappable types and expressions. In these definitions, let t denote an expression of a type T, and let u denote an expression of a type U.
An object designated t is swappable with an object designated u if and only if:
The context in which swap(t, u) and swap(u, t) are evaluated shall ensure that a binary non-member function named "swap" is selected via overload resolution ([over.match]) on a candidate set that includes:
[Note: If T and U are both fundamental types or arrays thereof, and the declarations from the header <utility> are in scope, the overall lookup set described above is equivalent to that of the qualified name lookup applied to the expression std::swap(t, u) or std::swap(u, t) as appropriate. — end note]
[Note: It is unspecified whether a library component that has a swappable requirement includes the header <utility> to ensure an appropriate evaluation context. — end note]
An rvalue or lvalue t is swappable if and only if t is swappable with any rvalue or lvalue of type T respectively.
A type X satisfying one of the iterator requirements of Clause 24 is ValueSwappable if *x is swappable for any dereferenceable object x of type X.
[Example: User code can ensure the evaluation of swap calls is performed in an appropriate context under the various conditions as follows:
#include <utility>
// Requires: std::forward<T>(t) shall be swappable with std::forward<U>(u).
template<class T, class U>
void value_swap(T&& t, U&& u) {
using std::swap;
swap(std::forward<T>(t), std::forward<U>(u)); // OK: Uses "swappable with" conditions for rvalues and lvalues
}
// Requires: lvalues of T shall be swappable.
template<class T>
void lv_swap(T& t1, T& t2) {
using std::swap;
swap(t1, t2); // OK: Uses swappable conditions for lvalues of type T
}
namespace N {
struct A { int m; };
struct Proxy { A* a; };
Proxy proxy(A& a) { return Proxy{&a}; }
void swap(A& x, Proxy p) {
std::swap(x.m, p.a->m); // OK: Uses context equivalent to swappable conditions for fundamental types
}
void swap(Proxy p, A& x) { swap(x, p); } // Satisfy symmetry constraint
}
int main() {
int i = 1, j = 2;
lv_swap(i, j);
assert(i == 2 && j == 1);
N::A a1 = {5}, a2 = {-5};
value_swap(a1, proxy(a2));
assert(a1.m == -5 && a2.m == 5);
}
— end example]
4 The X::pointer, X::const_pointer,
X::void_pointer, and X::const_void_pointer types
shall satisfy
the requirements of EqualityComparable,
DefaultConstructible, CopyConstructible,
CopyAssignable,
Swappable, and
Destructible (20.2.1), and lvalues of these types shall be
swappable (20.2.2).
template<class T> void swap(T& a, T& b);
template <class T, size_t N> void swap(T (&a)[N], T (&b)[N]);
..
template<ValueType T, size_t N>
void swap(T (&a)[N], T (&b)[N]);
template <class T, size_t N> void swap(T (&a)[N], T (&b)[N]);
3 Requires: T is Swappable (37). a[i] shall be swappable with (20.2.2) b[i] for all 0 <= i < N.
4 Effects: swap_ranges(a, a + N, b)
void swap(pair& p);
16 Effects: Swaps first with p.first and second with p.second.
17 Requires: first_type and second_type shall be Swappable. first shall be swappable with (20.2.2) p.first and second shall be swappable with p.second.
void swap(tuple& rhs);
1 Requires: Each type in Types shall be Swappable. Each element in *this shall be swappable with (20.2.2) the corresponding element in rhs.
2 Effects: Calls swap for each element in *this and its corresponding element in rhs.
3 Throws: Nothing unless one of the element-wise swap calls throws an exception.
2 If the deleter D maintains state, it is intended that
this state stay with the associated pointer as ownership is
transferred from unique_ptr to unique_ptr. The
deleter state need never be copied, only moved or swapped as pointer
ownership is moved around. That is, the deleter need only
be values obtained from get_deleter() must be
swappable (20.2.2), and D needs only satisfy the requirements
of MoveConstructible, and
MoveAssignable, and Swappable, and need
not be satisfy the requirements of CopyConstructible (unless
copied into the unique_ptr) nor CopyAssignable.
void swap(unique_ptr& u);
8 Requires: The deleter Dget_deleter() shall be Swappable swappable (20.2.2) and shall not throw an exception under swap.
9 Effects: The stored pointers of this and u are exchanged. The stored deleters are swap'd (unqualified).
10 Throws: nothing.
template<class ForwardIterator1, class ForwardIterator2>
ForwardIterator2 swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2);
1 Effects: For each non-negative integer n < (last1 - first1) performs: swap(*(first1 + n), *(first2 + n)).
2 Requires: The two ranges [first1,last1) and [first2,first2 + (last1 - first1)) shall not overlap. The type of *first1 *(first1 + n) shall be swappable with (20.2.2)the same as the type of *first2 *(first2 + n) and that type shall satisfy the Swappable requirements (Table 37).
..
template<class ForwardIterator1, class ForwardIterator2>
void iter_swap(ForwardIterator1 a, ForwardIterator2 b);
5 Effects: swap(*a, *b).
6 Requires: a and b shall be dereferenceable. The type of *a shall be the same as the type of swappable with (20.2.2) *b and that type shall satisfy the Swappable requirements (Table 37).
template<class BidirectionalIterator>
void reverse(BidirectionalIterator first, BidirectionalIterator last);
...
2 Requires: The type of *first shall be swappable (20.2.2) satisfy the Swappable requirements (Table 37).
template<class ForwardIterator>
ForwardIterator rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last);
...
4 Requires: [first,middle) and [middle,last) shall be valid ranges. The type of *first shall satisfy the Swappable requirements (Table 37), ForwardIterator shall satisfy the requirements of ValueSwappable (20.2.2). The type of *first shall satisfy the MoveConstructible requirements (Table 33), and the MoveAssignable requirements (Table 35).
template<class RandomAccessIterator>
void random_shuffle(RandomAccessIterator first,
RandomAccessIterator last);
template<class RandomAccessIterator, class RandomNumberGenerator>>
void random_shuffle(RandomAccessIterator first,
RandomAccessIterator last,
RandomNumberGenerator&& rand);
template<class RandomAccessIterator, class UniformRandomNumberGenerator>>
void random_shuffle(RandomAccessIterator first,
RandomAccessIterator last,
UniformRandomNumberGenerator& g);
...
2 Requires: The type of *first shall satisfy the Swappable requirements (Table 37) RandomAccessIterator shall satisfy the requirements of ValueSwappable (20.2.2). [..]
template<class ForwardIterator, class Predicate>
ForwardIterator
partition(ForwardIterator first,
ForwardIterator last, Predicate pred);
...
6 Requires: The type of *first shall satisfy the Swappable requirements (Table 37). ForwardIterator shall satisfy the requirements of ValueSwappable (20.2.2).
template<class BidirectionalIterator, class Predicate>
BidirectionalIterator
stable_partition(BidirectionalIterator first,
BidirectionalIterator last, Predicate pred);
...
10 Requires: The type of *first shall satisfy the Swappable requirements (Table 37), BidirectionalIterator shall satisfy the requirements of ValueSwappable (20.2.2). The type of *first shall satisfy the MoveConstructible requirements (Table 33), and the the MoveAssignable requirements (Table 35).
template<class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void sort(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
...
template<class RandomAccessIterator>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
...
template<class RandomAccessIterator>
void partial_sort(RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void partial_sort(RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last,
Compare comp);
...
template<class InputIterator, class RandomAccessIterator>
RandomAccessIterator
partial_sort_copy(InputIterator first, InputIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last);
template<class InputIterator, class RandomAccessIterator, class Compare>
RandomAccessIterator
partial_sort_copy(InputIterator first, InputIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last,
Compare comp);
...
template<class RandomAccessIterator>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
RandomAccessIterator last, Compare comp);
...
template<class BidirectionalIterator>
void inplace_merge(BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last);
template<class BidirectionalIterator, class Compare>
void inplace_merge(BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last,
Compare comp);
...
template<class RandomAccessIterator>
void pop_heap(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void pop_heap(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
...
template<class RandomAccessIterator>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
...
template<class BidirectionalIterator>
bool next_permutation(BidirectionalIterator first,
BidirectionalIterator last);
template<class BidirectionalIterator, class Compare>
bool next_permutation(BidirectionalIterator first,
BidirectionalIterator last, Compare comp);
...
template<class BidirectionalIterator>
bool prev_permutation(BidirectionalIterator first,
BidirectionalIterator last);
template<class BidirectionalIterator, class Compare>
bool prev_permutation(BidirectionalIterator first,
BidirectionalIterator last, Compare comp);
...
The authors would like to express their special thanks to Alberto Ganesh Barbati, Peter Dimov, Howard Hinnant, Jens Maurer, and Mike Miller for providing several wording improvements and reviewing of several drafts of this paper. Thanks also to Niels Dekker and Alisdair Meredith for reviewing this paper. Finally, we acknowledge the Fermi National Accelerator Laboratory's Computing Division for sponsoring the fourth author's participation in the C++ standardization effort.
The second, third, and fourth authors of this paper wish to extend special thanks to Daniel Krügler for providing the initial proposed wording that formed the basis of the proposal presented at the Pittsburgh meeting.