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

Question

我想std::set用自定义比较函数创建一个.我可以将它定义为一个类operator(),但我想享受定义使用它的lambda的能力,所以我决定在具有std::setas成员的类的构造函数的初始化列表中定义lambda函数.但我无法得到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::functionmake代码(可能)更慢？我的意思是,它是否降低了编译器内联比较函数的可能性,或者它应该足够聪明,行为完全相同,就像它是lambda函数类型一样而不是std::function(我知道,在这种情况下它不能是lambda类型,但是你知道,我一般都在问)？

(我使用GCC,但我想知道流行的编译器一般做什么)

总结之后,我得到了很多好的答案:

如果速度至关重要,最好的解决方案是使用带有operator()仿函数的类.编译器最容易优化并避免任何间接.

为了便于维护和更好的通用解决方案,使用C++ 11功能std::function.它仍然很快(比仿函数慢一点,但它可以忽略不计)并且您可以使用任何函数 - std::function,lambda,任何可调用对象.

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

有一个选项可以在其他地方定义lambda函数,但是你不会从比较函数中获得lambda表达式,因为你也可以使它成为一个类,operator()并且定义的位置无论如何都不是set结构.

有更多的想法,例如使用委托.如果您想要更全面地解释所有解决方案,请阅读答案:)

Answer 1

编译器不太可能内联std :: function调用,而任何支持lambdas的编译器几乎肯定会内联functor版本,包括该functor是不是由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上运行.

Answer 2

是的,一个std::function几乎不可避免的间接引入你的set.虽然编译器可以随时在理论上,找出所有使用您的set的std::function需要调用它的λ,始终是完全相同的拉姆达,既硬又极为脆弱.

脆弱的,因为之前的编译器可以证明自己的所有调用到std::function实际上是调用您的拉姆达,它必须证明没有用上你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算法.

Answer 3

无状态lambda(即没有捕获的lambda)可以衰减为函数指针,因此您的类型可以是:

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

否则我会去寻求make_set解决方案.如果你不使用单行创建函数,因为它是非标准的,你不会得到很多代码!