C++11 std::set lambda 比较函数

C++11 std::set lambda comparison function

提问by cfa45ca55111016ee9269f0a52e771

I want to create a std::setwith 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::setas a member. But I can't get the type of the lambda. Before I proceed, here's an example:

我想std::set用自定义比较函数创建一个。我可以将它定义为一个类operator()，但我想享受在使用它的地方定义 lambda 的能力，所以我决定在类的构造函数的初始化列表中定义 lambda 函数，该类的构造函数std::set作为成员。但我无法获得 lambda 的类型。在我继续之前，这里有一个例子：

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.

搜索后我找到了两种解决方案：一种，使用std::function. 只需设置比较函数类型，std::function<bool (int, int)>然后像我一样传递 lambda。第二种解决方案是编写一个 make_set 函数，例如std::make_pair.

SOLUTION 1:

解决方案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:

解决方案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::functionmake 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) ?

问题是，我是否有充分的理由更喜欢一种解决方案而不是另一种？我更喜欢第一个，因为它使用了标准功能（make_set 不是标准功能），但我想知道：使用std::function会使代码（可能）变慢吗？我的意思是，它是否会降低编译器内联比较函数的机会，或者它应该足够聪明以表现得完全相同，就像它是一个 lambda 函数类型而不是std::function（我知道，在这种情况下它不能是一个lambda 类型，但您知道，我一般是在问）？

(I use GCC, but I'd like to know what popular compilers do in general)

（我使用 GCC，但我想知道流行的编译器通常会做什么）

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.

如果速度很重要，最好的解决方案是使用带有operator()aka 函子的类。编译器最容易优化和避免任何间接访问。

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.

为了便于维护和更好的通用解决方案，使用 C++11 特性，使用std::function. 它仍然很快（只是比函子慢一点，但它可能可以忽略不计）并且您可以使用任何函数 - std::function、lambda、任何可调用对象。

There's also an option to use a function pointer, but if there's no speed issue I think std::functionis better (if you use C++11).

还有一个使用函数指针的选项，但如果没有速度问题，我认为std::function更好（如果您使用 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.

有一个选项可以在其他地方定义 lambda 函数，但是您无法从 lambda 表达式的比较函数中获得任何好处，因为您也可以将其设置为一个类，operator()并且定义的位置无论如何都不会是集合构造。

There are more ideas, such as using delegation. If you want a more thorough explanation of all solutions, read the answers :)

还有更多的想法，比如使用委托。如果您想对所有解决方案进行更彻底的解释，请阅读答案:)

采纳答案by Yakk - Adam Nevraumont

Yes, a std::functionintroduces nearly unavoidable indirection to your set. While the compiler can always, in theory, figure out that all use of your set's std::functioninvolves calling it on a lambda that is always the exact same lambda, that is both hard and extremely fragile.

是的， astd::function向您的set. 虽然编译器在理论上总是可以确定所有使用您的set's 都std::function涉及在始终与 lambda 完全相同的 lambda 上调用它，这既困难又极其脆弱。

Fragile, because before the compiler can prove to itself that all calls to that std::functionare actually calls to your lambda, it must prove that no access to your std::setever sets the std::functionto anything but your lambda. Which means it has to track down all possible routes to reach your std::setin all compilation units and prove none of them do it.

脆弱，因为在编译器可以向自己证明所有std::function对它的调用实际上都是对您的 lambda 的调用之前，它必须证明对您的访问std::set从未将 设置为std::function您的 lambda 之外的任何东西。这意味着它必须std::set在所有编译单元中追踪所有可能的路径以到达您的所有编译单元，并证明它们都没有这样做。

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.

另一方面，具有无状态的函子operator()易于证明行为，并且涉及日常事务的优化。

So yes, in practice I'd suspect std::functioncould be slower. On the other hand, std::functionsolution is easier to maintain than the make_setone, and exchanging programmer time for program performance is pretty fungible.

所以是的，实际上我怀疑std::function可能会更慢。另一方面，std::function解决方案比解决方案更容易维护make_set，并且用程序员的时间来换取程序性能是可以互换的。

make_sethas the serious disadvantage that any such set's type must be inferred from the call to make_set. Often a setstores persistent state, and not something you create on the stack then let fall out of scope.

make_set有一个严重的缺点，即set必须从对 的调用中推断出任何此类的类型make_set。通常一个set存储持久状态，而不是你在堆栈上创建的东西，然后让它超出范围。

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 setthat 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 setin a struct. (Or does your compiler support

如果您创建了一个静态或全局无状态 lambda auto MyComp = [](A const&, A const&)->bool { ... }，您可以使用std::set<A, decltype(MyComp)>语法来创建一个set可以持久化的，但编译器很容易优化（因为所有实例decltype(MyComp)都是无状态函子）和内联的。我指出这一点，因为你坚持的set一个struct。（或者你的编译器是否支持

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_setis 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::vectoris better if you have a 2-phase "insert everything" then "query contents repeatedly". Simply stuff it into the vectorfirst, then sortuniqueerase, then use the free equal_rangealgorithm.

最后，如果您担心性能，请考虑它std::unordered_set要快得多（代价是无法按顺序迭代内容，并且必须编写/找到一个好的散列），并且std::vector如果您有一个排序更好两阶段“插入所有内容”然后“重复查询内容”。只需将其塞入第vector一个，然后sortuniqueerase，然后使用自由equal_range算法。

回答by metal

It's unlikely that the compiler will be able to inline a std::function call, whereas any compiler that supports lambdas would almost certainly inline the functor version, including if that functor is a lambda not hidden by a std::function.

编译器不太可能内联 std::function 调用，而任何支持 lambdas 的编译器几乎肯定会内联函子版本，包括如果该函子是未被std::function.

You could use decltypeto get the lambda's comparator type:

您可以使用decltype来获取 lambda 的比较器类型：

#include <set>
#include <iostream>
#include <iterator>
#include <algorithm>

int main()
{
   auto comp = [](int x, int y){ return x < y; };
   auto set  = std::set<int,decltype(comp)>( comp );

   set.insert(1);
   set.insert(10);
   set.insert(1); // Dupe!
   set.insert(2);

   std::copy( set.begin(), set.end(), std::ostream_iterator<int>(std::cout, "\n") );
}

Which prints:

哪个打印：

1
2
10

See it run live on Coliru.

看到它实时运行Coliru。

回答by Jonathan Wakely

A stateless lambda (i.e. one with no captures) can decay to a function pointer, so your type could be:

无状态 lambda（即没有捕获的 lambda）可以衰减为函数指针，因此您的类型可能是：

std::set<int, bool (*)(int, int)> numbers;

Otherwise I'd go for the make_setsolution. If you won't use a one-line creation function because it's non-standard you're not going to get much code written!

否则我会寻求make_set解决方案。如果您不使用单行创建函数，因为它是非标准的，那么您将不会编写太多代码！

回答by ecatmur

If you're determined to have the setas a class member, initializing its comparator at constructor time, then at least one level of indirection is unavoidable. Consider that as far as the compiler knows, you could add another constructor:

如果您决定将set用作类成员，并在构造函数时初始化其比较器，那么至少有一层间接性是不可避免的。考虑到编译器知道，您可以添加另一个构造函数：

 Foo () : numbers ([](int x, int y)
                   {
                       return x < y;
                   })
 {
 }

 Foo (char) : numbers ([](int x, int y)
                   {
                       return x > y;
                   })
 {
 }

Once the you have an object of type Foo, the type of the setdoesn't carry information on which constructor initialized its comparator, so to call the correct lambda requires an indirection to the run-time selected lambda operator().

一旦您拥有 type 的对象Foo， 的类型set就不会携带有关哪个构造函数初始化其比较器的信息，因此要调用正确的 lambda 需要对运行时选定的 lambda 进行间接访问operator()。

Since you're using captureless lambdas, you could use the function pointer type bool (*)(int, int)as your comparator type, as captureless lambdas have the appropriate conversion function. This would of course involve an indirection through the function pointer.

由于您使用的是无捕获 lambda，您可以使用函数指针类型bool (*)(int, int)作为比较器类型，因为无捕获 lambda 具有适当的转换函数。这当然会涉及通过函数指针的间接访问。

回答by user1095108

From my experience playing around with the profiler, the best compromise between performance and beauty is to use a custom delegate implementation, such as:

根据我使用分析器的经验，性能和美观之间的最佳折衷是使用自定义委托实现，例如：

https://codereview.stackexchange.com/questions/14730/impossibly-fast-delegate-in-c11

https://codereview.stackexchange.com/questions/14730/impossably-fast-delegate-in-c11

As the std::functionis usually a bit too heavy. I can't comment on your specific circumstances, as I don't know them, though.

因为std::function通常有点太重了。我不能评论你的具体情况，因为我不了解他们。

回答by filmor

The difference highly depends on your compiler's optimizations. If it optimizes lambda in a std::functionthose are equivalent, if not you introduce an indirection in the former that you won't have in the latter.

差异在很大程度上取决于您的编译器的优化。如果它优化了 lambda，则std::function它们是等效的，否则，您将在前者中引入一个间接性，而后者则不会。