C++ non-member functions for nested template classes

Question

I have been writing several class templates that contain nested iterator classes, for which an equality comparison is required. As I believe is fairly typical, the comparison is performed with a non-member (and non-friend) operator== function. In doing so, my compiler (I'm using Mingw32 GCC 4.4 with flags -O3 -g -Wall) fails to find the function and I have run out of possible reasons.

In the rather large block of code below there are three classes: a Base class, a Composed class that holds a Base object, and a Nested class identical to the Composed class except that it is nested within an Outer class. Non-member operator== functions are supplied for each. These classes are in templated and untemplated forms (in their own respective namespaces), with the latter equivalent to the former specialised for unsigned integers.

In main, two identical objects for each class are compared. For the untemplated case there is no problem, but for the templated case the compiler fails to find operator==. What's going on?

#include <iostream>

namespace templated {

template<typename T>
class Base {
  T t_;
public:
  explicit Base(const T& t) : t_(t) {}

  bool
  equal(const Base& x) const {
    return x.t_==t_;
  }
};

template<typename T>
bool
operator==(const Base<T> &x, const Base<T> &y) {
  return x.equal(y);
}

template<typename T>
class Composed {
  typedef Base<T> Base_;
  Base_ base_;
public:
  explicit Composed(const T& t) : base_(t) {}
  bool equal(const Composed& x) const {return x.base_==base_;}
};

template<typename T>
bool
operator==(const Composed<T> &x, const Composed<T> &y) {
  return x.equal(y);
}

template<typename T>
class Outer {
public:
  class Nested {
    typedef Base<T> Base_;
    Base_ base_;
  public:
    explicit Nested(const T& t) : base_(t) {}
    bool equal(const Nested& x) const {return x.base_==base_;}
  };
};

template<typename T>
bool
operator==(const typename Outer<T>::Nested &x,
    const typename Outer<T>::Nested &y) {
  return x.equal(y);
}

} // namespace templated

namespace untemplated {

class Base {
  unsigned int t_;
public:
  explicit Base(const unsigned int& t) : t_(t) {}

  bool
  equal(const Base& x) const {
    return x.t_==t_;
  }
};

bool
operator==(const Base &x, const Base &y) {
  return x.equal(y);
}

class Composed {
  typedef Base Base_;
  Base_ base_;
public:
  explicit Composed(const unsigned int& t) : base_(t) {}
  bool equal(const Composed& x) const {return x.base_==base_;}
};

bool
operator==(const Composed &x, const Composed &y) {
  return x.equal(y);
}

class Outer {
public:
  class Nested {
    typedef Base Base_;
    Base_ base_;
  public:
    explicit Nested(const unsigned int& t) : base_(t) {}
    bool equal(const Nested& x) const {return x.base_==base_;}
  };
};

bool
operator==(const Outer::Nested &x,
    const Outer::Nested &y) {
  return x.equal(y);
}

} // namespace untemplated

int main() {
  using std::cout;
  unsigned int testVal=3;
  { // No templates first
    typedef untemplated::Base Base_t;
    Base_t a(testVal);
    Base_t b(testVal);

    cout << "a=b=" << testVal << "\n";
    cout << "a==b ? " << (a==b ? "TRUE" : "FALSE") << "\n";

    typedef untemplated::Composed Composed_t;
    Composed_t c(testVal);
    Composed_t d(testVal);

    cout << "c=d=" << testVal << "\n";
    cout << "c==d ? " << (c==d ? "TRUE" : "FALSE") << "\n";

    typedef untemplated::Outer::Nested Nested_t;
    Nested_t e(testVal);
    Nested_t f(testVal);

    cout << "e=f=" << testVal << "\n";
    cout << "e==f ? " << (e==f ? "TRUE" : "FALSE") << "\n";
  }
  { // Now with templates
    typedef templated::Base<unsigned int> Base_t;
    Base_t a(testVal);
    Base_t b(testVal);

    cout << "a=b=" << testVal << "\n";
    cout << "a==b ? " << (a==b ? "TRUE" : "FALSE") << "\n";

    typedef templated::Composed<unsigned int> Composed_t;
    Composed_t c(testVal);
    Composed_t d(testVal);

    cout << "c=d=" << testVal << "\n";
    cout << "d==c ? " << (c==d ? "TRUE" : "FALSE") << "\n";

    typedef templated::Outer<unsigned int>::Nested Nested_t;
    Nested_t e(testVal);
    Nested_t f(testVal);

    cout << "e=f=" << testVal << "\n";
    cout << "e==f ? " << (e==f ? "TRUE" : "FALSE") << "\n";
    // Above line causes compiler error:
    // error: no match for 'operator==' in 'e == f'
  }

  cout << std::endl;
  return 0;
}

Answer 1

If you haven't overloaded operator&, then just compare memory addresses. There's no need to do this.

Answer 2

The issue is fairly common with nested class with templates.

template <class T>
struct Outer { struct Inner {}; };

template <class T>
void increment(typename Outer<T>::Inner&) {}

The increment function cannot be found. I think the look up is too difficult for the compiler to solve.

You can alleviate the problem though,

namespace detail
{
  template <class T> struct InnerImpl {};

  template <class T> void increment(InnerImpl& ) {}
}

template <class T>
struct Outer
{
  typedef detail::InnerImpl<T> Inner;
};

int main(int argc, char* argv[])
{
  Outer<int>::Inner inner;
  increment(inner);         // works
}

Funny, isn't it ?

As a rule of thumb, typename in the arguments (not for the result type) of a free method is a red herring and seems to prevent automatic argument deduction.

Answer 3

After accepting an answer, I thought about how best to fix my code with the minimum effort. Armed with a clearer idea of the problem I took new inspiration from the C++ FAQ and merged the non-member operator== into the class definition as a friend function. This isn't as much of a hack as it sounds, since the reason for supplying an equal() member function was to avoid the need of a friend, but for templates a friend function has the benefit of allowing the function definition to be held within the class body, thus avoiding the lookup issues.

template<typename T>
class Outer {
public:
  class Nested {
    typedef Base<T> Base_;
    Base_ base_;
    friend bool operator==(Nested const &x, Nested const &y) {
      return x.base_==y.base_;
    }
  public:
    explicit Nested(const T& t) : base_(t) {}
  };
};