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?

masoud · Answer 1 · 2013-04-18T07:02:48.940

2

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.

edited Apr 18 '13 at 07:02

answered Apr 18 '13 at 04:46

masoud

55,379
16
141
208

Oh goodness, the code I posted was simplified too much to show the whole problem. Let me try again and make sure there's a real problem here and not just my inability to make a proper test case! Thanks. – John Zwinck Apr 18 '13 at 04:51
OK, I've updated the code in the question to better reflect the problem. Can you have another look please? – John Zwinck Apr 18 '13 at 04:52
@JohnZwinck: I just updated my answer based on your new edit, to make it relevant. – masoud Apr 18 '13 at 05:06

score 2 · Answer 2 · answered Apr 18 '13 at 05:55

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.

answered Apr 18 '13 at 05:55

Elroy

167
1
8

I can use this as a workaround; I'd still like to know why the code in my question doesn't "just work." – John Zwinck Apr 18 '13 at 07:30

score 2 · Accepted Answer · edited May 23 '17 at 10:25

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:

Move the operator< inside Inner and make it a friend function.
Define operator< inside Inner like M M. suggested.
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;
}

C++ STL fails to find comparator for nested class

4 Answers4