首页 文章

C 11 std :: set lambda比较函数

提问于
浏览 次
68

我想创建一个带有自定义比较功能的 std::set . 我可以将它定义为一个带有 operator() 的类，但我想享受定义使用它的lambda的能力，所以我决定在类的构造函数的初始化列表中定义lambda函数，该函数的 std::set 为会员 . 但我可以举个例子：

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 （我知道，在这种情况下它可以't be a lambda type, but you know, I'问一般来说） ？

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

SUMMARY, AFTER I GOT LOTS OF GREAT ANSWERS:

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

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

有's also an option to use a function pointer, but if there'没有速度问题我认为 std::function 更好（如果你使用C 11） .

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

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

c++ stl c++11 lambda std-function

6 回答

  • 1

    是的， std::function 几乎不可避免的间接引入你的 set . 理论上，编译器总是能够发现 set 的 std::function 的所有使用都涉及在一个总是完全相同的lambda的lambda上调用它，这既困难又极其脆弱 .

    易碎，因为在编译器可以向自己证明对 std::function 的所有调用实际上都是对lambda的调用之前，它必须证明对 std::set 的访问权限永远不会将 std::function 设置为除了你的lambda之外的任何东西 . 这意味着它必须跟踪所有可能的路由，以便在所有编译单元中到达 std::set 并证明它们都没有 .

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

    另一方面，具有无状态 operator() 的仿函数易于证明行为，并且涉及这些的优化是日常事物 .

    所以是的，在实践中我怀疑_2456333可能会慢一些 . 另一方面， std::function 解决方案比 make_set 解决方案更容易维护，并且为程序性能交换程序员时间是相当可靠的 .

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

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

    struct Foo {
  auto mySet = make_set<int>([](int l, int r){ return l<r; });
};

    我觉得很惊讶！）

    最后，如果您担心性能，请考虑 std::unordered_set 要快得多（代价是无法按顺序迭代内容，并且必须编写/找到一个好的哈希），并且排序 std::vector 更好，如果你有一个2阶段"insert everything"然后"query contents repeatedly" . 只需先将其填入 vector ，然后再使用 sort unique erase ，然后使用免费的 equal_range 算法 .

    回复于
  • 22

    编译器不太可能内联一个std :: function调用，而任何支持lambdas的编译器几乎肯定会内联functor版本，包括该functor是否是一个未被 std::function 隐藏的lambda .

    您可以使用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

    See it run on Coliru .

    回复于
  • 0

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

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

    否则我会去找 make_set 解决方案 . 如果你赢了't use a one-line creation function because it'的非标准你就不会得到太多的代码！

    回复于
  • 1

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

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

    因为 std::function 通常有点太重了 . 不过，我可以不知道他们 .

    回复于
  • 23

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

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

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

    一旦你有一个 Foo 类型的对象， set 的类型不包含哪个构造函数初始化其比较器的信息，所以要调用正确的lambda需要间接到运行时选择的lambda operator() .

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

    回复于
  • 5

    差异在很大程度上取决于编译器的优化 . 如果它优化了 std::function 中的lambda，那么它们是等价的，如果没有，你会在前者中引入一个你不会在后者中使用的间接 .

    回复于

相关问题