C++11 std::set lambda comparison function
c++, c++11, lambda, std-function, stl
Solution
Yes, a `std::function` introduces nearly unavoidable indirection to your `set`. While the compiler can always, in theory, figure out that all use of your `set`'s `std::function` involves calling it on a lambda that is always the exact same lambda, that is both hard and extremely fragile.
Fragile, because before the compiler can prove to itself that all calls to that `std::function` are actually calls to your lambda, it must prove that no access to your `std::set` ever sets the `std::function` to anything but your lambda. Which means it has to track down all possible routes to reach your `std::set` in all compilation units and prove none of them do it.
This might be possible in some cases, but relatively innocuous changes could break it even if your compiler managed to prove it.
On the other hand, a functor with a stateless `operator()` has easy to prove behavior, and optimizations involving that are everyday things.
So yes, in practice I'd suspect `std::function` could be slower. On the other hand, `std::function` solution is easier to maintain than the `make_set` one, and exchanging programmer time for program performance is pretty fungible.
`make_set` has the serious disadvantage that any such `set`'s type must be inferred from the call to `make_set`. Often a `set` stores persistent state, and not something you create on the stack then let fall out of scope.
If you created a static or global stateless lambda `auto MyComp = [](A const&, A const&)->bool { ... }`, you can use the `std::set<A, decltype(MyComp)>` syntax to create a `set` that can persist, yet is easy for the compiler to optimize (because all instances of `decltype(MyComp)` are stateless functors) and inline. I point this out, because you are sticking the `set` in a `struct`. (Or does your compiler support
struct Foo {
auto mySet = make_set<int>([](int l, int r){ return l<r; });
};
which I would find surprising!)
Finally, if you are worried about performance, consider that `std::unordered_set` is much faster (at the cost of being unable to iterate over the contents in order, and having to write/find a good hash), and that a sorted `std::vector` is better if you have a 2-phase "insert everything" then "query contents repeatedly". Simply stuff it into the `vector` first, then `sort` `unique` `erase`, then use the free `equal_range` algorithm.
Problem
I want to create a `std::set` with a custom comparison function. I could define it as a class with `operator()`, but I wanted to enjoy the ability to define a lambda where it is used, so I decided to define the lambda function in the initialization list of the constructor of the class which has the `std::set` as a member. But I can't get the type of the lambda. Before I proceed, here's an example: ``` class Foo { private: std::set<int, /*???*/> numbers; public: Foo () : numbers ([](int x, int y) { return x < y; }) { } }; ``` I found two solutions after searching: one, using `std::function`. Just have the set comparison function type be `std::function<bool (int, int)>` and pass the lambda exactly like I did. The second solution is to write a make_set function, like `std::make_pair`. SOLUTION 1: ``` class Foo { private: std::set<int, std::function<bool (int, int)> numbers; public: Foo () : numbers ([](int x, int y) { return x < y; }) { } }; ``` SOLUTION 2: ``` template <class Key, class Compare> std::set<Key, Compare> make_set (Compare compare) { return std::set<Key, Compare> (compare); } ``` The question is, do I have a good reason to prefer one solution over the other? I prefer the first one because it makes use of standard features (make_set is not a standard function), but I wonder: does using `std::function` make the code (potentially) slower? I mean, does it lower the chance the compiler inlines the comparison function, or it should be smart enough to behave exactly the same like it would it was a lambda function type and not `std::function` (I know, in this case it can't be a lambda type, but you know, I'm asking in general) ? (I use GCC, but I'd like to know what popular compilers do in general) SUMMARY, AFTER I GOT LOTS OF GREAT ANSWERS: If speed is critical, the best solution is to use an class with `operator()` aka functor. It's easiest for the compiler to optimize and avoid any indirections. For easy maintenance and a better general-purpose solution, using C++11 features, use `std::function`. It's still fast (just a little bit slower than the functor, but it may be negligible) and you can use any function - `std::function`, lambda, any callable object. There's also an option to use a function pointer, but if there's no speed issue I think `std::function` is better (if you use C++11). There's an option to define the lambda function somewhere else, but then you gain nothing from the comparison function being a lambda expression, since you could as well make it a class with `operator()` and the location of definition wouldn't be the set construction anyway. There are more ideas, such as using delegation. If you want a more thorough explanation of all solutions, read the answers :)