79

我想创建一个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;
                       })
     {
     }
};

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

解决方案 1：

class Foo
{
private:
     std::set<int, std::function<bool (int, int)> numbers;
public:
     Foo () : numbers ([](int x, int y)
                       {
                           return x < y;
                       })
     {
     }
};

解决方案 2：

template <class Key, class Compare>
std::set<Key, Compare> make_set (Compare compare)
{
     return std::set<Key, Compare> (compare);
}

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

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

总结，在我得到很多很好的答案之后：

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

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

还有一个使用函数指针的选项，但如果没有速度问题我认为std::function更好（如果你使用 C++11）。

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

还有更多的想法，比如使用委托。如果您想更全面地解释所有解决方案，请阅读答案:)

4

6 回答 6

36

编译器不太可能内联 std::function 调用，而任何支持 lambda 的编译器几乎肯定会内联仿函数版本，包括如果该仿函数是不被 a 隐藏的 lambda std::function。

您可以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") );
}

哪个打印：

1
2
10

看到它在现场直播Coliru。

于 2013-02-15T13:49:44.193 回答
28

是的，astd::function向您的set. 虽然编译器总是可以，理论上，找出你set的所有使用都std::function涉及在一个总是完全相同的 lambda 的 lambda 上调用它，这既困难又极其脆弱。

脆弱，因为在编译器可以向自己证明所有std::function对它的调用实际上都是对你的 lambda 的调用之前，它必须证明除了你的 lambda 之外，没有任何访问你std::set的权限std::function。这意味着它必须在所有编译单元中跟踪所有可能的路线以到达您std::set的位置，并证明它们都没有这样做。

在某些情况下这可能是可能的，但是即使您的编译器设法证明了这一点，相对无害的更改也可能会破坏它。

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

所以是的，在实践中我怀疑std::function可能会更慢。另一方面，std::function解决方案比一个更容易维护make_set，并且用程序员的时间换取程序性能是相当可替代的。

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

如果您创建了一个静态或全局无状态 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; });
};

我会感到惊讶！）

最后，如果您担心性能，请考虑std::unordered_set更快（代价是无法按顺序迭代内容，并且必须编写/找到一个好的哈希），并且std::vector如果您有一个排序更好2阶段“插入所有内容”然后“重复查询内容”。只需将其填充到第vector一个，然后sort unique erase，然后使用免费equal_range算法。

于 2013-02-15T14:10:50.160 回答
7

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

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

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

于 2013-02-15T14:04:04.203 回答
1

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

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

因为std::function通常有点太重了。我无法评论你的具体情况，因为我不知道。

于 2013-02-15T13:55:19.330 回答
1

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

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

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

一旦你有一个 type 的对象Foo，它的类型set就不会携带关于哪个构造函数初始化了它的比较器的信息，所以要调用正确的 lambda 需要间接到运行时选择的 lambda operator()。

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

于 2013-02-15T14:15:59.570 回答
0

差异很大程度上取决于编译器的优化。如果它优化了 lambdastd::function那些是等价的，如果不是，你在前者中引入一个间接，你在后者中不会有。

于 2013-02-15T13:43:08.733 回答