0

In my other question, How to use a static method as a callback in c++, people solved my practical problem, then suggested I take a different approach in general to follow best practice. I would like a better understanding of why.

This example uses a comparator, but I would really like to understand if there is a general rule for functional programming (for example perhaps also aggregator functions related to a class etc.)

Example use case for a comparator function:

#include <set>

int main() {
    std::set<MyClass, decltype(SOMETHING_HERE)> s(SOMETHING_HERE);
    return 0;
}

Below are solutions I am aware of, from most to least recommended (I believe) - the opposite order to what I would currently choose.

1.

Recommended way (I believe) with a functor:

struct MyComparator {
    bool operator() (MyClass a, MyClass b) const {
        return a > b; // Reversed
    }
};

std::set<MyClass, MyComparator)> s;

I don't like: verbose; not lexically tied to MyClass; I don't understand why s has no constructor argument. I am confused about the lack of argument because set seems to mix up/combine deciding the comparison algorithm at compile time / with the typesystem (as in this example), and at runtime / with a pointer. If it was just one way or the other I would be fine with "that's just how it is".

2.

A method that seems nicer to me:

auto const my_comparator = [](int a, int b) {
    return a > b;
};

std::set<int, decltype(my_comparator)> s(my_comparator);

It's terser. Intention is clear: it is a function, not a class that could be potentially added to. Passing the object, not just the type, makes sense to me (couldn't there be 2 different implementations).

3.

The method that makes most sense to me (based on other languages):

class MyClass {
public:
    
    // More code here
    
    static auto compare_reverse(MyClass a, MyClass b) {
        return a > b;
    }
};

std::set<int, decltype(&MyClass::compare_reverse)> s(&MyClass::compare_reverse);

It is clearly related (and lexically tied to) MyClass. Seems efficient (though I have been told it's not) and terse.

Any explanation why the recommended order is better, performance, bugs/maintainability, philosophical, very appreciated.

user83455
  • 17
  • 3
  • For the problem of ordering for `std::set` or `std::map` (or default ordering for `std::sort` and other functions), why not create a `bool MyClass::operator<(MyClass const&)` function? – Some programmer dude Dec 04 '21 at 14:41
  • @Someprogrammerdude there already is one. It has many orderings. Thank you for highlighting that aspect. – user83455 Dec 04 '21 at 14:46
  • 1
    `decltype(MyComparator())` is simply `MyComparator`. You are making it more verbose than it needs to be. As to "lexically tied" - you can make `MyComparator` a nested class in `MyClass`, and refer to it as `MyClass::MyComparator`. And if for some reason you feel better passing a constructor argument, you can pass `MyComparator{}` (though I must admit I don't understand how one can complain about "too verbose" and "not verbose enough" in the span of one sentence). – Igor Tandetnik Dec 04 '21 at 14:48
  • 2
    Wait. So `std::set s;` is too verbose, while `std::set s(my_comparator);` is terser? By what measure of verbosity? Clearly not by number of characters. What goal function are you trying to optimize? – Igor Tandetnik Dec 04 '21 at 14:56
  • @user83455: "*It's terser.*" No, it isn't. #2 clearly requires more text at the variable definition site than #1. It also creates a global variable. – Nicol Bolas Dec 04 '21 at 14:56
  • @IgorTandetnik My concern with missing the constructor argument is not one of terseness. It is the separate issue that I just don't understand why it is needed sometimes and not others. My understanding (maybe incorrect) is decltype is type system related / compile time, but the pointer is runtime. I would expect one or other method of determining the implementation in a given programming language, but not both. My concern is if `set` can vary at runtime, how can it work without information at runtime? (maybe c++ is just way cooler than I thought). – user83455 Dec 04 '21 at 15:06
  • @NicolBolas That's fair, but I don't understand why one form needs an argument and the other doesn't and I would like to know that. For example if I could combine the closure definition with the argument-free form (or perhaps omit the decltype) that would be ideal. I don't see the distinction between a const global function variable and a class. Coming from a lispy background they seem roughly equivalent. I guess the type system can do cooler stuff with the class? – user83455 Dec 04 '21 at 15:09
  • 1
    `std::set` default-constructs `Comp` if an instance of `Comp` is not passed to the constructor. That's all there is to it. While uncommon, a comparator may be stateful and may have constructors with parameters - then an instance would have to be constructed explicitly and passed to the `set`. Imagine e.g. a set of pointers into some external data structure, where you compare pointers by looking up actual values they point to, and comparing those. The comparator may take a reference to that external data structure in its constructor. – Igor Tandetnik Dec 04 '21 at 15:09
  • "`my_comparator` is a function, not a class" . That's technically incorrect. `my_comparator` is an object of some class type (that cannot be named other than via `decltype(my_comparator)`). A lambda expression is a shorthand for writing a class with `operator()`. Starting with C++20 you could even omit the constructor argument, as in `std::set s;`, since captureless lambdas have been made default-constructible. – Igor Tandetnik Dec 04 '21 at 15:16
  • Using a plain C function pointer as a comparator is likely to preclude inlining, which may hurt performance. – Igor Tandetnik Dec 04 '21 at 15:21

1 Answers1

1

Firstly, note that if you just want a > comparator, there are std::greater<> and std::greater<MyClass> (the former is usually superior).

Reviewing the options you listed:

(1)

struct MyComparator
{
    bool operator()(MyClass a, MyClass b) const
    {
        return a > b;
    }
};
std::set<MyClass, MyComparator)> s;

As you said, this is the recommended way.

not lexically tied to MyClass

As suggested in the comments, you can put it inside MyClass.

don't understand why s has no constructor argument

If you don't pass the comparator to the constructor, the comparator is default-constructed (if it's default-constructible, otherwise you get a compilation error).

You can pass MyComparator{} manually, but there is no point.

(2)

auto my_comparator = [](int a, int b)
{
    return a > b;
};
std::set<int, decltype(my_comparator)> s(my_comparator);

It's exactly equivalent to (1), except you're forced to pass my_comparator to the constructor. C++20 fixed this by making lambdas default-constructible (if they have no captures), making the argument unnecessary.

(3)

class MyClass
{
  public:
    static auto compare_reverse(MyClass a, MyClass b)
    {
        return a > b;
    }
};
std::set<int, decltype(&MyClass::compare_reverse)> s(&MyClass::compare_reverse);

This gives you an extra feature: you can choose the comparator at runtime, by passing different functions to the constructor.

This ability comes with an overhead: the set stores a pointer to the function (normally 4 or 8 bytes), and has to look at the pointer when making comparisons.

(3.5)

You can wrap your function in std::integral_constant. The result is equivalent to (1).

bool foo(int x, int y) {return x > y;}

std::set<int, std::integral_constant<decltype(&foo), foo>> s;
// Or:
using MyComparator = std::integral_constant<decltype(&foo), foo>;
std::set<int, MyComparator> s;

This is good if you're dealing with an existing type, that provides the comparator as a function, and you don't want the overhead of (3).

All of those (except (3)) are equivalent.

If std::greater<> is applicable, you should use it.

Otherwise I'd recommend (1) as the least confusing option.

HolyBlackCat
  • 78,603
  • 9
  • 131
  • 207