Providing swap() for a C++ template class breaks std::swap()?

Question

I was trying to implement the copy-and-swap idiom in my custom Matrix class, and I ran into some trouble with the implementation of swap() in the way suggested in the linked-to question:

(The compiler I used is the one from MS VS2010 IDE, dialect is good old-fashioned C++03.)

// matrix.h

namespace my_space 
{

template<typename T> class Matrix
{
public:
    /* ... */

    friend void swap(Matrix<T> &first, Matrix<T> &second)
    {
        using std::swap;
        swap(first.width_, second.width_);
        swap(first.height_, second.height_);
        swap(first.data_, second.data_);
    }
};

} // namespace

Now I have trouble reaching regular std::swap() in the code for functions residing in this namespace:

// some_code.cpp:
#include "matrix.h"
#include <algorithm>

using namespace my_space;
using namespace std;

// SomeClass is part of my_space!
void SomeClass::some_function()
{
    int a = 3, b = 7;
    swap(a,b);  // I wan't std::swap!
}

Unfortunately, for some reason, my_space::swap() for Matrix seems to alias all other calls to std::swap(), and I've no idea why since the arguments don't fit and ADL should favor std::swap:

1>f:\src\some_code.cpp(653): error C3767: 'swap': candidate function(s) not accessible
1>          could be the friend function at 'f:\src\matrix.h(63)' : 'swap'  [may be found via argument-dependent lookup]

(The error repeats 10 times for every line where I'm trying to use std::swap)

Does my_space::swap() always overrule std::swap() in my_space, even if the arguments don't fit? It's not as if std::swap() is not visible, and it worked OK before my_space::swap() was created.

Answer 1

The approach taken by STL containers uses a member function and then overload the static function. For example:

template<class T, class Alloc=std::allocator<T> >
class vector
{
   T *data;
   size_t n;
   size_t max_n;
public:
   void swap(vector<T, Alloc> &other)
   {
      swap(this->data, other.data);
      swap(this->n, other.n);
      swap(this->max_n, other.max_n);
   }
};

template<class T, class A>
void swap(vector<T, A> &lhs, vector<T, A> &rhs)
{
   lhs.swap(rhs);
}

In the suggested Matrix class, simply take the same approach...

namespace my_space
{
template<typename T>
class Matrix
{
   unsigned width_;
   unsigned height_;
   std::vector<T> data_;
public:
   void swap(Matrix<T> &other)
   {
      std::swap(this->width_, other.width_);
      std::swap(this->height_, other.height_);
      std::swap(this->data_, other.data_);  // calls this->data_.swap(other.data_);
   }
};
}

namespace std
{
   template<typename T>
   void swap(my_space::Matrix<T> &lhs, my_space::Matrix<T> &rhs)
   {
      lhs.swap(rhs);
   }
}

Answer 2

Include the following line in Matrix:

template<typename U> friend void swap(Matrix<U> &first, Matrix<U> &second);

and define the swap outside of the class. The reason you are getting the error function template has already been defined, is because each instantiation of Matrix<unsigned short> and Matrix<char> will contain the same defintion of your swap function since you defined the friend function inside of the Matrix template.

Answer 3

The following builds cleanly for me with VC++ 2010 SP1:

Matrix.h:

#pragma once

#include <algorithm>
#include <vector>

namespace my_space
{
    template<typename T>
    class Matrix
    {
    public:
        Matrix(unsigned const w, unsigned const h)
          : width_(w), height_(h), data_(w * h)
        { }

    private:
        unsigned width_;
        unsigned height_;
        std::vector<T> data_;

        friend void swap(Matrix& lhs, Matrix& rhs)
        {
            using std::swap;
            swap(lhs.width_,  rhs.width_);
            swap(lhs.height_, rhs.height_);
            swap(lhs.data_,   rhs.data_);
        }
    };
}

.cpp:

#include "Matrix.h"

int main()
{
    using namespace my_space;
    using std::swap;

    int a(0), b(1);
    swap(a, b);

    Matrix<int> c(2, 3), d(4, 5);
    swap(c, d);

    Matrix<short> e(6, 7), f(8, 9);
    swap(e, f);
}

Since you didn't post an SSCCE (hint, hint), it's very difficult to see exactly where you're going wrong, but you can use this as a starting point to narrow down your issue.

Answer 4

If the code is really like what you posted, that is an issue with the compiler. The code compiles fine in clang++, as it should.

Friend declarations are strange in that they declare a function that has namespace scope, but the declaration is only available though ADL, and even then, only if at least one of the arguments is of the type of the class that has the friend declaration. Unless there is a namespace level declaration, the function is not available in the namespace scope.

---

Test 1 (function not available at namespace level with out an explicit declaration):

namespace A {
   struct B {
      friend void f();  // [1]
   };
   // void f();         // [2]
}
void A::f() {}          // [3]

In [1] we add a friend declaration, that declares void A::f() as a friend of A::B. Without the additional declaration in [2] at namespace level, the definition in [3] will fail to compile, since being outside of the A namespace that definition is not also a self-declaration.

---

The implication here is that, because the function is not available for lookup at namespace level, but only through ADL on Matrix<T> (for some particular instantiating type T), the compiler cannot possibly find that as a match to a swap of two int values.

In his answer, Jesse Good states that each instantiation of Matrix and Matrix will contain the same defintion of your swap function since you defined the friend function inside of the Matrix template which is completely absurd.

A friend function that is defined inside the class will declare and define a namespace level function, and again, the declaration will only be available inside the class and accessible through ADL. When this is done inside a template it will define a non-templated free function at namespace level for each instantiation of the template that uses the function. That is, it will generate different definitions. Note that inside the class template scope, the name of the template identifies the specialization that is being instantiated, that is, inside Matrix<T>, the identifier Matrix does not name the template, but one instantiation of the template.

Test 2

---

namespace X {
   template <typename T>
   struct A {
      friend void function( A ) {}
   };
   template <typename T>
   void funcTion( A<T> ) {}
}
int main() {
   using namespace X;
   A<int> ai;    function(ai); funcTion(ai);
   A<double> ad; function(ad); funcTion(ad);
}

$ make test.cpp
$ nm test | grep func | c++filt
0000000100000e90 T void X::funcTion<double>(A<double>)
0000000100000e80 T void X::funcTion<int>(A<int>)
0000000100000e70 T X::function(A<double>)
0000000100000e60 T X::function(A<int>)

The output of nm is the list of symbols, and c++filt will translate the mangled names into the equivalent in C++ syntax. The output of the program clearly shows that X::funcTion is a template that has been instantiated for two types, while X::function are two overloaded non-templated functions. Again: two non-templated functions.

---

Claiming that it would generate the same function makes little sense, consider that it had a function call, say std::cout << lhs, the code must pick the correct overload of operator<< for the current instantiation of the function. There is no single operator<< that can take say a int and an unsigned long or std::vector<double> (Nothing inhibits you from instantiating the template with any type.

The answer by ildjarn proposes an alternative, but provides no explanation of the behavior. The alternative works because a using-directive is completely different from a using-declaration. In particular, the former (using namespace X;) modifies lookup so that the identifiers in namespace X are available at namespace level in one of the enclosing namespaces of the current piece of code (if you build a tree of namespaces, the declarations would be available where the branch containing X meets the branch containing the code where the using-directive is used).

On the other hand, a using-declaration (using std::swap;) provides a declaration of the function std::swap in the context where the using-declaration is present. This is why you must use using-declarations and not using-directives to implement your swap functions:

Test 3

---

namespace Y { struct Z {}; void swap( Z&,Z& ); }
namespace X {
   struct A { int a; Y::Z b; };
   void swap( A& lhs, A& rhs ) {
      //using namespace std;       // [1]
      using std::swap;             // [2]
      swap( lhs.a, rhs.a );        // [3]
      swap( lhs.b, rhs.b );        // [4]
   }
}

If we had used a using-directive [1], the symbols from the ::std namespace would be available for lookups performed inside the function ::X::swap(X::A&,X::A&) as if they had been declared in :: (which is the common ancestor of ::std and ::X). Now the swap in [3] will not find any swap function through ADL, so it will start searching for swap functions in the enclosing namespace. The first enclosing namespace is X, and it does contain a swap function, so lookup will stop and overload resolution will kick in, but X::swap is not a valid overload for swap(int&,int&), so it will fail to compile.

By using a using-declaration we bring std::swap declaration to the scope of X::swap (inside the function!). Again, ADL will not be applied in [3], and lookup will start. In the current scope (inside the function) it will find the declaration of std::swap and will instantiate the template. In [4], ADL does kick in, and it will search for a swap function defined inside the ::Y::Z function and/or in ::Y, and add that to the set of overloads found in the current scope (again, ::std::swap). At this point, ::Z::swap is a better match than std::swap (given a perfect match, a non-templated function is a better match than a templated one) and you get the expected behavior.

---