Document number: N3048=10-0038
Project: Programming Language C++, Library Working Group
Author: Daniel Krügler, Mike Spertus, Stefanus Du Toit, Walter E. Brown
Date: 2010-03-12

Defining Swappable Requirements

Discussion

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:

The specific issues to be addressed are:

  1. The requirements are inconsistent, because they do not say in an unambigious way what user code has to do to satisfy the requirements.
  2. The dependency on MoveContructible and MoveAssignable for some special cases (the first bullet in above list) is very unfortunate, because the second bullet already provides a recipe that would just impose the requirements on the actual chosen swap overload. If this overload were a user-defined swap function, the requirements are only those of this particular function. This is the key problem described in library issue 594.
  3. The requirement of the third bullet is unnecessary, because the standard now provides a swap overload for arrays as part of the header <utility>. If we think of the array swap of a function that just forwards to the appropriate swap of the array's elements, this would just be the same approach as described in the bullet 2.
  4. Delegating to a single and unambiguous swap overload if the two swap function templates of <utility> are part of the candidate set would automatically remove any specific requirements on lvalue-ness of the arguments. In fact, it would just delegate to the lvalue-ness of the selected swap function. This is the key problem described in library issue 742.
  5. The current Swappable requirements restrict the return type of the swap function to void. This is both unnecessary and atypical compared to most existing requirement sets and can be relaxed.

Design Rationale

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:

  1. HasSwap<T, U> ⇔ "std::declval<T>() is swappable with std::declval<U>()"
  2. Swappable<T> ⇔ "T satisfies the Swappable requirements"

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:

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
  }

}

Updated Rationale and Later Changes

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.

Resolved Issues

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.

Proposed resolution

  1. Change [utility.requirements]/1 as indicated [Note to the editor: The second inserted sentence should be added only if 1245 has been accepted]:

    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.

  2. In subclause [utility.arg.requirements], remove Table 37 — Swappable requirements [swappable]:

    Table 37 — Swappable requirements [swappable]
    Expression Return type Post-condition
    swap(s, t) void t 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.
  3. Following [utility.arg.requirements] add a new subclause: [Comment to the editor: This means that all current links to Table 37 — Swappable requirements [swappable] have to be changed into links to subclause [swappable.requirements]. These changes are not shown in the following directives.]

    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. Change paragraph 4 of [allocator.requirements] as indicated:

    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).

  5. Change [utility.swap] as indicated [Note that there are currently three declarations in the WP. One is misplaced, and the other refers to concepts. We fix this here in addition to augmenting the array swap description]:

    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)

  6. Change [pair.pairs] as indicated:

    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.

  7. Change [tuple.swap] as indicated:

    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.

  8. Change [unique.ptr.single] paragraph 2 as indicated:

    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.

  9. Change the description of swap in [unique.ptr.single.modifiers] as indicated:

    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.

  10. Change [alg.swap] as indicated: [The intention is to remove the unnecessary requirements that both iterator value-types are the same and to extend for possible rvalues, e.g. due to proxies, as well. Additionally we fix an obvious missing requirement for iter_swap that both iterator values need to be dereferencable.]

    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).

  11. Change [alg.reverse]/2 as indicated: [The intention is to to extend for possible rvalues, e.g. due to proxies, as well]

    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).

  12. Change [alg.rotate]/4 as indicated: [The intention is to extend for possible rvalues, e.g. due to proxies, as well]

    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).

  13. Change [alg.random.shuffle]/2 as indicated: [The intention is to extend for possible rvalues, e.g. due to proxies, as well]

    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). [..]

  14. Change [alg.partitions] paragraphs 6 and 10 as indicated: [The intention is to extend for possible rvalues, e.g. due to proxies, as well]

    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).

  15. Change [sort]/2 as indicated: [The intention is to extend for possible rvalues, e.g. due to proxies, as well]

    template<class RandomAccessIterator>
      void sort(RandomAccessIterator first, RandomAccessIterator last);
    template<class RandomAccessIterator, class Compare>
      void sort(RandomAccessIterator first, RandomAccessIterator last,
                Compare comp);
    
    ...
    2 Requires: The type of *first shall satisfy the Swappable requirements (Table 37),RandomAccessIterator 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).

  16. Change [stable.sort]/2 as indicated: [The intention is to extend for possible rvalues, e.g. due to proxies, as well]

    template<class RandomAccessIterator>
      void stable_sort(RandomAccessIterator first, RandomAccessIterator last);
    template<class RandomAccessIterator, class Compare>
      void stable_sort(RandomAccessIterator first, RandomAccessIterator last,
                       Compare comp);
    
    ...
    2 Requires: The type of *first shall satisfy the Swappable requirements (Table 37), RandomAccessIterator 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).

  17. Change [partial.sort]/2 as indicated: [The intention is to extend for possible rvalues, e.g. due to proxies, as well]

    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);
    
    ...
    2 Requires: The type of *first shall satisfy the Swappable requirements (Table 37), RandomAccessIterator 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).

  18. Change [partial.sort.copy]/3 as indicated: [The intention is to extend for possible rvalues, e.g. due to proxies, as well]

    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);
    
    ...
    3 Requires: The type of *result_first shall satisfy the Swappable requirements (Table 37), RandomAccessIterator shall satisfy the requirements of ValueSwappable (20.2.2). The type of *result_first shall satisfy the MoveConstructible requirements (Table 33), and the the MoveAssignable requirements (Table 35).

  19. Change [alg.nth.element]/2 as indicated: [The intention is to extend for possible rvalues, e.g. due to proxies, as well]

    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);
    
    ...
    2 Requires: The type of *first shall satisfy the Swappable requirements (Table 37), RandomAccessIterator 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).

  20. Change [alg.merge]/7 as indicated: [The intention is to extend for possible rvalues, e.g. due to proxies, as well]
    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);
    
    ...
    7 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).

  21. Change [pop.heap]/2 as indicated: [The intention is to extend for possible rvalues, e.g. due to proxies, as well]

    template<class RandomAccessIterator>
      void pop_heap(RandomAccessIterator first, RandomAccessIterator last);
    template<class RandomAccessIterator, class Compare>
      void pop_heap(RandomAccessIterator first, RandomAccessIterator last,
                    Compare comp);
    
    ...
    2 Requires: The range [first,last) shall be a valid heap. The type of *first shall satisfy the Swappable requirements (Table 37), RandomAccessIterator 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).

  22. Change [sort.heap]/2 as indicated: [The intention is to extend for possible rvalues, e.g. due to proxies, as well]

    template<class RandomAccessIterator>
      void sort_heap(RandomAccessIterator first, RandomAccessIterator last);
    
    template<class RandomAccessIterator, class Compare>
      void sort_heap(RandomAccessIterator first, RandomAccessIterator last,
                     Compare comp);
    
    ...
    2 Requires: The range [first,last) shall be a valid heap. The type of *first shall satisfy the Swappable requirements (Table 37), RandomAccessIterator 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).

  23. Change [alg.permutation.generators] paragraphs 2 and 6 as indicated: [The intention is to extend for possible rvalues, e.g. due to proxies, as well]

    template<class BidirectionalIterator>
      bool next_permutation(BidirectionalIterator first,
                            BidirectionalIterator last);
    
    template<class BidirectionalIterator, class Compare>
      bool next_permutation(BidirectionalIterator first,
                            BidirectionalIterator last, Compare comp);
    
    ...
    2 Requires: The type of *first shall satisfy the Swappable requirements (Table 37). BidirectionalIterator shall satisfy the requirements of ValueSwappable (20.2.2).

    template<class BidirectionalIterator>
      bool prev_permutation(BidirectionalIterator first,
                            BidirectionalIterator last);
    
    template<class BidirectionalIterator, class Compare>
      bool prev_permutation(BidirectionalIterator first,
                            BidirectionalIterator last, Compare comp);
    
    ...
    6 Requires: The type of *first shall satisfy the Swappable requirements (Table 37). BidirectionalIterator shall satisfy the requirements of ValueSwappable (20.2.2).

Acknowledgements

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.