C ++ 11 std :: set 람다 비교 함수

C ++ 11 std :: set 람다 비교 함수

---

std::set사용자 지정 비교 기능으로 를 만들고 싶습니다 . 를 사용하여 클래스로 정의 할 수 operator()있지만 사용되는 람다를 정의하는 기능을 즐기고 싶었 기 때문에를 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)>하고 내가 한 것처럼 람다를 전달하십시오. 두 번째 해결책은 다음과 같은 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하면 코드가 (잠재적으로) 느려질까요? 내 말은, 컴파일러가 비교 함수를 인라인 할 가능성을 낮추는가, 아니면 람다 함수 유형이 아닌 람다 함수 유형과 동일하게 작동 할만큼 충분히 똑똑해야 std::function합니까 (이 경우에는 람다 유형이지만 일반적으로 묻습니다)?

(저는 GCC를 사용하지만 일반적으로 인기있는 컴파일러가 무엇을하는지 알고 싶습니다.)

요약, 훌륭한 답변을 많이 얻은 후 :

속도가 중요한 경우 가장 좋은 해결책은 operator()펑터라고 하는 클래스를 사용하는 것 입니다. 컴파일러가 간접적 인 것을 최적화하고 피하는 것이 가장 쉽습니다.

C ++ 11 기능을 사용하는 쉬운 유지 관리와 더 나은 범용 솔루션을 위해 std::function. 여전히 빠르며 (펑터보다 약간 느리지 만 무시할 수 있음) 모든 함수 std::function, 람다, 모든 호출 가능한 객체를 사용할 수 있습니다 .

함수 포인터를 사용하는 옵션도 있지만 속도 문제가 없으면 std::function더 좋다고 생각 합니다 (C ++ 11을 사용하는 경우).

람다 함수를 다른 곳에서 정의 할 수있는 옵션이 있지만 람다 식인 비교 함수에서 아무것도 얻지 못합니다. 왜냐하면 클래스로 만들 수 있고 operator()정의 위치는 어쨌든 집합 구성이 아니기 때문입니다.

위임 사용과 같은 더 많은 아이디어가 있습니다. 모든 솔루션에 대한 자세한 설명을 원하면 답변을 읽으십시오. :)

---

예, a 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스택에 생성 한 것이 아닌 영구 상태를 저장 한 다음 범위를 벗어납니다.

정적 또는 전역 비 저장 람다를 만든 경우 auto MyComp = [](A const&, A const&)->bool { ... }, 당신은 사용할 수 std::set<A, decltype(MyComp)>생성 구문을 set지속 할 수 있습니다를, 아직 최적화 컴파일러 쉽게 (모든 인스턴스가 있기 때문에 decltype(MyComp)무 펑터 있습니다) 및 인라인. 당신이를 고집하고 있기 때문에 나는이 밖으로 지점 setA의 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알고리즘 을 사용하십시오 .

---

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.

You could use decltype to get the lambda's comparator type:

#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.

---

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

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

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

---

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

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

---

If you're determined to have the set as 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:

 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 set doesn'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().

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.

---

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

참고URL : https://stackoverflow.com/questions/14896032/c11-stdset-lambda-comparison-function