C++ STL fails to find comparator for nested class

Question

I expected this code to work, but it fails to compile with GCC. It does compile if you lift the inner class out.

#include <algorithm>

template <typename T>
struct Outer
{
  struct Inner
  {
    int x;
  };
  Inner vec[3];
};

template <typename T>
bool operator <(const typename Outer<T>::Inner& lhs, const typename Outer<T>::Inner& rhs)
{
  return lhs.x < rhs.x;
}

int main()
{
  Outer<int> out;
  Outer<int>::Inner in;
  std::lower_bound(out.vec, out.vec + 3, in);
}

GCC 4.4 has this to say:

...
bits/stl_algo.h:2442: error: no match for ‘operator<’ in ‘* __middle < __val’

GCC 4.7 prints a lot more stuff, including the above, ending with this:

...
bits/stl_algobase.h:957:4: note: couldn't deduce template parameter ‘T’

I'm willing to believe it's not well-formed C++, but why not?

Answer 1

The problem as you mentioned is that the compiler couldn't deduce template parameter T. That is because typename Outer::Inner is a nondeduced context context for T.

When a template parameter is used only in a nondeduced context, it's not taken into consideration for template argument deduction. The details are at section 14.8.2.4 of the C++ Standard (2003).

Why? If you specialize Outer as:

template <>
struct Outer<int>
{
   struct Inner
   {
       double y;
   };
   Inner vec[3];
}; 

There is no way for the compiler to deduce if Outer::Inner should reference this definition or the previous one.

Now, onto solutions. There are a couple of possible resolutions:

1. Move the operator< inside Inner and make it a friend function.
2. Define operator< inside Inner like M M. suggested.
3. Suggested by Johannes Schaub - litb: Derive inner from a CRTP base parameterized by inner. Then make the parameter type the CRTP class and cast the parameter reference to the derived inner class, the type of which is given by the template argument you deduce.

I tried out the CRTP approach since it sounds so cool!:

template <typename Inner>
struct Base
{
};

template <typename T>
struct Outer
{
  struct Inner : Base<Inner>
  {
    T x;
  };
  Inner vec[3];
};

template <typename T>
bool operator< (const Base<T>& lhs, const Base<T>& rhs)
{
  return static_cast<const T&>(lhs).x < static_cast<const T&>(rhs).x;
}

Related answers: 1, 2, 3

Answer 2

Here's another workaround. Why don't you use a custom comparer?

template <typename T>
struct Comparer
{
    bool operator()(const typename Outer<T>::Inner& lhs, const typename Outer<T>::Inner& rhs)
    {
        return lhs.x < rhs.x;
    }
};

int main()
{
    Outer<int> out;
    Outer<int>::Inner in;
    std::lower_bound(out.vec, out.vec + 3, in, Comparer<int>());
}

Hope this works for you.

Answer 3

If you overload a specific operator< for int the problem will vanish:

bool operator<(const typename Outer<int>::Inner& lhs, 
               const typename Outer<int>::Inner& rhs)
{
    return lhs.x < rhs.x;
}

 

The simpler solution is defining operator< inside Inner:

template<typename T>
struct Outer
{

    struct Inner
    {
        int x;

        bool operator<(const Inner& obj) const
        {
            return x < obj.x;
        }

    };
    Inner vec[3];
};

Also, it's just a quick solution. And my answer is not the why compiler can not find operator< in nested situation in template mode.

Answer 4

Mar0ux's answer is pretty good. You can find additional information here:

Stephan T. Lavavej: Core C++, 2 of n

You should watch the whole video series - it contains a lot of useful information but you might start from minute 34 or so to get your question answered. Stephen mentions one basic rule to keep in mind:

:: is a brick wall for template argument deduction, i.e. a template argument T on the left side can't be deduced.