14

This question is inspired by Issue with std::reference_wrapper. Let' say, for example, operator< for std::vector. It's defined as a function template as 

template< class T, class Alloc >
bool operator<( const vector<T,Alloc>& lhs,
                const vector<T,Alloc>& rhs );

As a result, implicit conversion of function argument to the type of the corresponding function parameter is denied (basically because of its template nature). This greatly reduces the usefulness and convenience of std::reference_wrapper. For example, you cannot use std::sort on std::vector<std::reference_wrapper<std::vector<int>>>.

On the other hand, all the problems are solved only if operator< is defined as a non-template Koenig operator like

template <...>
class vector ... {
  friend bool operator<(const vector& a, const vector& b) {...}
};

I'm wondering why the standard library has adopted the former approach instead of this?

Community
  • 1
  • 1
Lingxi
  • 14,579
  • 2
  • 37
  • 93
  • @jxh The crucial difference between the two is: one is a template, effectively forbidding implicit conversion, while the other is not, allowing implicit conversion. – Lingxi May 15 '15 at 17:47
  • 4
    Well, at the time that `operator <` was standardized, `reference_wrapper` didn't exist, AFAIK. – T.C. May 15 '15 at 17:52
  • 2
    About the wording: there are no Koenig operators. There are, instead, functions that are found by ADL/Koenig lookup. – edmz May 15 '15 at 17:53
  • @black I just need a convenient word for the `friend bool operator<(...) {...}` thing... – Lingxi May 15 '15 at 17:56
  • The friend function is implicitly inline. – dyp May 15 '15 at 18:00
  • @dyp Is there any problem with that? – Lingxi May 15 '15 at 18:02
  • 1
    It's not a problem, but I think at the time when the SGI STL was invented, it still was relevant to optimizers. -- Also note that this function doesn't need to be a friend (doesn't need privileged access), so maybe it was thought to be a cleaner solution. – dyp May 15 '15 at 18:03
  • 2
    Maybe a better way to allow this btw would be to add wrapper operators to `std::reference_wrapper`, just like its `operator()`. – dyp May 15 '15 at 18:05
  • 1
    Here's a question: suppose you wanted to overload operator< for std::vector. Would it be doable given your suggestion? It seems like it might be impossible. Your function would be an exact, non templated match, so defining your own operator< would result in an ambiguity error. Whereas in the current form, overloading operator< will work perfectly since it takes precedence over a template function. – Nir Friedman May 15 '15 at 18:13
  • @NirFriedman Would `using some_ns::operator<;` be a solution? – Lingxi May 15 '15 at 18:18
  • This is not a solution, because the pre existing operator< would always be around, because it's namespace gets dragged in with the type (vector) during adl lookup. So you will get an ambiguous function call error. I think this is a reasonable explanation, so I'll post it. – Nir Friedman May 15 '15 at 19:29
  • Is this not exactly http://stackoverflow.com/questions/30265207/should-operators-be-declared-as-non-member-non-template-friends – Barry May 15 '15 at 20:59
  • It seems like both questions were asked almost simultaneously. Since this question has received more upvotes and has an answer, the most reasonable thing seems to be to close the other. – Nir Friedman May 15 '15 at 21:08

1 Answers1

1

Consider this code (A.h):

template <class T>
class A {
  public:
  T m_x;

  friend bool operator<(const A & lhs, const A & rhs) {
    return lhs.m_x < rhs.m_x;
  }
};

And main.cpp:

#include "A.h"

namespace buddy {
bool operator<(const A<double> & lhs, const A<double> &rhs) {
    return lhs.m_x > rhs.m_x;
};
}
using namespace buddy;
int main(int argc, char ** argv) {

  A<double> a1;
  A<double> a2;

  a1 < a2;

  return 0;
}

This code does not compile:

main.cpp:14:5: error: ambiguous overload for ‘operator<’ (operand types are ‘A’ and ‘A’) a1 < a2;

The reason of course is that both of the operator<'s are exact matches. On the other hand, if we change the first operator< to (defined outside the class):

template <class T>
bool operator<(const A<T> & lhs, const A<T> & rhs) {
  return lhs.m_x < rhs.m_x;
}

The compiler stops complaining: it's now a competition between an exact match, and a function template, so the exact match is used.

If operator< was defined in the fashion that you're suggesting, there would be no reasonable way for users of std::vector to redefine the behavior of operator<, short of specializing std::vector themselves, which is a lot more work.

In conclusion, the standard writers elected to make it easier to overload operator<, than to provide an operator< that might be more useful in certain situations. I think they made the right choice.

Nir Friedman
  • 17,108
  • 2
  • 44
  • 72
  • 1
    *"there would be no reasonable way for users of std::vector to redefine the behavior of operator<"* You seem to imply that this is a good thing. I don't think I'd agree. For example, the generic algorithms in the Standard Library allow passing a comparator function object, to specify a custom order relation. – dyp May 15 '15 at 20:48
  • There's nothing particularly fundamental about operator< for a vector; it's just defined in some reasonable default way. If the default implementation doesn't make sense for you, and there's another operation that's always what you want, it makes sense to overload operator<. Even if you don't feel this way, I'm sure you can concede there will be a range of opinion. The standard should make things easier where possible, unless there's broad consensus that it's dangerous or will lead to unclear code. – Nir Friedman May 15 '15 at 21:02
  • Alexander Stepanov, one of the inventors of the SGI STL, would surely disagree: `operator<` and `operator==` (and their specific semantics of a strict weak ordering and equality) are required to make a type *regular*. For example, `operator<` is necessary for sorting and fast lookup (binary search). Therefore, I don't think this "loophole" of redefining `operator<` has been introduced intentionally. – dyp May 15 '15 at 21:58
  • My point was that there is nothing fundamental about this particular operator<. Yes, it's necessary for sorting and fast lookup, for which you can, as you pointed out, pass your own comparator. It's defined generically because there is a reasonable generic default, that is both intuitive and has the desired properties. Unordered_map/set do not have operator<, even though one with the desired properties could be trivially defined. The stl authors clearly didn't see < as mandatory for their containers. Once you accept that < is just a reasonable default, allowing overloading makes perfect sense. – Nir Friedman May 15 '15 at 22:32
  • *"Unordered_map/set do not have operator<, even though one with the desired properties could be trivially defined"* I doubt that: One of the desired properties is [`!(a < b) && !(b < a)` is equivalent to `a == b`]. Since the set is *unordered*, I imagine such an `operator<` cannot be implemented efficiently (e.g. two equal map/sets with different bucket counts). – dyp May 15 '15 at 22:44
  • I don't see any relevance of efficiency here. Many classes provide inefficient operators. If you want another example, priority_queue also does not appear to offer <. Anyhow, what you've basically said is that: 1. operator < is very useful. 2. Therefore, allowing you to overload it must be an oversight. I don't see how 1 implies 2. Of course, the user should be careful to provide < with the correct properties, but the exact same reasoning applies to passing comparators to sort, so this does not rule it out. – Nir Friedman May 15 '15 at 23:03
  • Anyhow, I think we passed the constructive part of the talk after the first two posts. You don't like this technique, ergo it's presence is an accident. I think it's ok (but not my first choice in most cases), and think the standard likes to keep options open for its users. Agree to disagree. – Nir Friedman May 15 '15 at 23:07
  • Whether or not I like the loophole is irrelevant to the quality of your answer. Your answer is based on the assumption that the loophole is intentional. And I don't think that's the case, based on the papers/books/talks by Stepanov which I've read. Of course, whether or not it's intentional can only be definitely answered by either the SGI STL creators or the C++ Standard Committee. -- On the topic of `unordered_*` and `priority_queue`: I'll try to find out why they don't support `<` (pq doesn't even support `==`). If you like, I'll post a comment here if I find a definite answer to that. – dyp May 15 '15 at 23:26
  • It is indeed dangerous. Consider the case when you call into a function defined in `std`, which uses expressions like `a < b`. In this case, the lookup ends in `std` if the compiler finds a `operator<` definition there, event if it is not a match and there is a match or a better match should the lookup continues on. This leads to conflicting behaviors of `operator<` used in different contexts and can surprise programmers. See http://coliru.stacked-crooked.com/a/37fb09223edfc377 for an example in action. – Lingxi May 16 '15 at 03:56
  • Luigi, this is only because I defined < in a different namespace than A. I did this for demonstration purposes. If you define them in the same namespace, which is the natural and standard thing to do, this behavior is impossible. I hardly see how this is dangerous. – Nir Friedman May 16 '15 at 04:10
  • @NirFriedman Users of the standard library are not supposed to define in `std` unless explicitly allowed by the standard. – Lingxi May 16 '15 at 05:52
  • Who said anything about defining in std?3) For arguments whose type is a class template specialization, in addition to the class rules, the following types are examined and their associated classes and namespaces are added to the set a) The types of all template arguments provided for type template parameters (skipping non-type template parameters and skipping template template parameters). So for a vector of user defined type, it's not an issue. – Nir Friedman May 16 '15 at 12:24