C ++ 11 std :: set lambda比较函数 [英] C++11 std::set lambda comparison function

问题描述

我想用自定义比较函数创建一个 std :: set 。我可以将它定义为一个类 operator（），但我想享受定义一个lambda的能力，因此我决定定义lambda函数将 std :: set 作为成员的类的构造函数的初始化列表。但我不能得到lambda的类型。在我继续之前，这里有一个例子：

  class Foo 
 {
 private：
 std :: set< int，/ * ??? * />数字; 
 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）>数字; 
 public：
 Foo（）：numbers（[]（int x，int y）
 {
 return x< y; 
}）
 {
} 
}; 
  

解决方案2：

  template< class Key，class Compare> 
 std :: set< Key，Compare> make_set（比较比较）
 {
 return std :: set< Key，Compare> （比较）; 
} 
  

问题是，我有一个很好的理由，其他？我喜欢第一个，因为它使用标准功能（make_set不是一个标准函数），但我不知道：使用 std :: function 使代码（潜在）慢点？我的意思是，它降低了编译器嵌入比较函数的机会，或者它应该足够聪明，行为完全一样，就像它是一个lambda函数类型，而不是 std :: function （我知道，在这种情况下，它不能是一个lambda类型，但你知道，我一般问）。

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

总结，在我有很多很好的答案： p>

如果速度很关键，最好的解决方案是使用一个 operator（） aka函子。

为了便于维护和更好的通用解决方案，使用C ++ 11的功能，使用 std :: function 。它仍然很快（只是稍微慢于函子，但它可以忽略），你可以使用任何函数 - std :: function ，lambda，任何可调用的对象。

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

有一个选项定义lambda函数在其他地方，但然后你不从比较函数是一个lambda表达式，因为你也可以使其成为 operator（）的类，并且定义的位置不会是集合结构。

有更多的想法，如使用委派。如果你想更全面地解释所有的解决方案，请阅读答案：）

解决方案

是的， std :: function 向您的 set 引入几乎不可避免的间接。虽然编译器可以总是理解，所有使用你的设置的的std ::函数涉及调用它的lambda总是完全相同的lambda，这是非常困难和非常脆弱。

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

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

，具有无状态运算符（）的函数容易证明行为，并且涉及这些行为的优化是日常事物。

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

make_set 有一个严重的缺点，任何这样的 / code>的类型必须从调用 make_set 中推断。通常，设置存储持久状态，而不是您在堆栈上创建的内容，而不会超出范围。

如果您创建了一个静态或全局无状态lambda auto MyComp = []（A const& A const&） - > bool {...} std :: set< A，decltype（MyComp）> 语法创建可以持久保存的 set 易于编译器优化（因为 decltype（MyComp）的所有实例都是无状态函子）和inline。我指出这一点，因为你在 struct 中插入 set 。 （或你的编译器支持

  struct Foo {
 auto mySet = make_set< int>（int ，int r）{return l< r;}）; 
}; 
  

会发现令人惊讶的！）

最后，如果你担心性能，考虑 std :: unordered_set 更快（以不能按顺序迭代内容，并且必须写/找到一个好的哈希）为代价，并且排序的 std :: vector 更好如果你有一个2阶段插入一切，然后重复查询内容。只需将它放入向量中，然后 sort unique erase ，然后使用免费的 equal_range 算法。

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 :)

解决方案

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.

这篇关于C ++ 11 std :: set lambda比较函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！