Why can't I overload this comparator that I pass to std::upper_bound

Question

I am fairly new to C++ and thought it was always ok to overload functions, by overloading I mean:

Function overloading in C++ You can have multiple definitions for the same function name in the same scope. The definition of the function must differ from each other by the types and/or the number of arguments in the argument list. You can not overload function declarations that differ only by return type.

However when I write the code bellow it does not compile, and I have the impression that std::upper_bound cannot resolve which comparator it should use, though it would appear easy as there is only one that has a correct signature.

EDIT Those functions are in a utility file (not class) in a namespace.

I did this following this post

I am likely totally wrong here, can you explain

1. why the code does not compile
2. how I could write 2 implementation of lt which different signature that will have the code compiling and runnable

#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>

//I have a utility file where functions are defined in a namespace
namespace util{
  bool lt(double y, const std::pair<double, long>& x) { 
      return x.first < y;
  }
  //If this function is commented the whole will compile and run
  bool lt(const std::pair<double, long>& x, double y) {
      return x.first < y;
  }
}

int main()
{
  std::vector<std::pair<double,long> > v;
  v.push_back(std::make_pair(999., 123));
  v.push_back(std::make_pair(100., 3));
  v.push_back(std::make_pair(15., 13));
  v.push_back(std::make_pair(10., 12));
  v.push_back(std::make_pair(1., 2));
  //use upper_bound
  std::vector<std::pair<double,long> >::iterator it =
      std::upper_bound(v.begin(), v.end(), 25., util::lt);
  std::cout << " it->first => " << it->first << std::endl;
}

Answer 1

Because std::upper_bound is templated on the type of the predicate (the function you are passing), the particular overload to be used has to be known before any of the body of upper_bound is looked at (which is where overload resolution could be carried out, since the arguments are known). There are various ways around this, none of them particularly pretty:

• cast to the exact type:

  std::upper_bound(v.begin, v.end(), 25.0, static_cast<bool (*)(double, const std::pair<double, long>&>(lt))
  

• Wrap the call in a lambda:

  [](auto x, auto y){ return lt(x, y); }
  

• Put the functions inside a class, so that the template is instantiated with the type of the class, then overload resolution happens inside the body of the template:

  struct LT {
      bool operator()(double y, const std::pair<double, long>& x) {
          return x.first < y;
      }
      bool operator()(const std::pair<double, long>& x, double y) {
          return x.first < y;
      }
  };
  // ...
  std::upper_bound(v.begin(), v.end(), 25.0, LT());
  

Note that the second 2 options are almost the same thing!

---

As it is, I would suggest you stop and think about what you are doing. Does it really make sense to provide ordering between two entirely different types? And your first function actually seems to be implement gt (greater than), maybe it was supposed to be return y < x.first;?

I also really consider using endl to be a bad practice (I know not everyone agrees with me).

Answer 2

The place where you call upper_bound is not a call site for lt, so no overload resolution is taking place here, and your overloads are ambiguous.

#include <algorithm>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>

bool lt(const std::pair<double, long>& x, const std::pair<double, long>& y)
{
    return x.first < y.first;
}

int main()
{
    std::vector<std::pair<double, long>> v;
    v.push_back(std::make_pair(999., 123));
    v.push_back(std::make_pair(100., 3));
    v.push_back(std::make_pair(15., 13));
    v.push_back(std::make_pair(10., 12));
    v.push_back(std::make_pair(1., 2));
    // use upper_bound
    std::vector<std::pair<double, long>>::iterator it =
        std::upper_bound(v.begin(), v.end(), std::make_pair(25., 0.), lt);
    std::cout << " it->first => " << it->first << std::endl;
}