C++ 11 std :: ustaw funkcję porównania lambda

Question

Chcę utworzyć std::set z niestandardową funkcją porównania. Mógłbym zdefiniować go jako klasę z operator(), ale chciałem cieszyć się możliwością zdefiniowania lambda, gdzie jest on używany, więc zdecydowałem się zdefiniować funkcję lambda na liście inicjalizacyjnej konstruktora klasy, który ma std::set jako członek. Ale nie mogę uzyskać typu lambda. Zanim przystąpię, oto przykład:

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

znalazłem dwa rozwiązania po poszukiwaniach: jeden, używając std::function. Po prostu ustaw typ funkcji porównania na std::function<bool (int, int)> i przeprowadź lambdę dokładnie tak jak ja. Drugim rozwiązaniem jest napisanie funkcji make_set, takiej jak std::make_pair.

ROZWIĄZANIE 1:

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

Rozwiązanie 2:

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

Pytanie brzmi, czy mam dobry powód, aby preferować jednego rozwiązania nad drugim? Wolę pierwszy, ponieważ korzysta on ze standardowych funkcji (make_set nie jest standardową funkcją), ale zastanawiam się: czy użycie kodu std::function powoduje, że kod (potencjalnie) jest wolniejszy? Chodzi mi o to, czy obniża to szansę, że kompilator ustawia funkcję porównania, czy też powinien być na tyle sprytny, aby zachowywać się dokładnie tak samo, jakby był to typ funkcji lambda, a nie std::function (wiem, w tym przypadku nie może to być typ lambda, ale wiesz, pytam w ogóle)?

(używam GCC, ale chciałbym wiedzieć, co popularne kompilatory zrobić w ogóle)

Podsumowując, po tym jak dostać wiele świetnych odpowiedzi:

Jeśli prędkość jest krytyczny, najlepiej rozwiązaniem jest użycie klasy z operator() aka funktor. Najłatwiej jest zoptymalizować kompilator i uniknąć wszelkich pośredników.

Dla łatwiejszej konserwacji i lepszego rozwiązania ogólnego przeznaczenia, przy użyciu funkcji C++ 11, należy użyć std::function. Jest nadal szybki (tylko trochę wolniejszy od funktora, ale może być pomijalny) i można użyć dowolnej funkcji - std::function, lambda, dowolnego obiektu wywoływalnego.

Istnieje również opcja użycia wskaźnika funkcji, ale jeśli nie ma problemu z szybkością, myślę, że std::function jest lepszy (jeśli używasz C++ 11).

Istnieje możliwość zdefiniowania funkcji lambda gdzieś indziej, ale wtedy nic nie zyskujesz z funkcji porównania będącej wyrażeniem lambda, ponieważ równie dobrze możesz uczynić ją klasą z operator(), a lokalizacja definicji nie będzie i tak ustaw budowę.

Istnieje więcej pomysłów, takich jak korzystanie z delegacji. Jeśli chcesz dokładniej wyjaśnić wszystkie rozwiązania, przeczytaj odpowiedzi :)

Answer 1

Tak, std::function wprowadza prawie nieuniknione pośrednie do Twojego set. Podczas gdy kompilator zawsze może teoretycznie stwierdzić, że wszystkie użycie twojego set 's wymaga użycia go w lambda, który jest zawsze dokładnie taki sam lambda, który jest zarówno twardy, jak i bardzo delikatny.

Kruchy, ponieważ przed kompilator może okazać się, że wszystkie połączenia do tego std::function są w rzeczywistości nazywa się twój lambda, musi udowodnić, że nie ma dostępu do std::set kiedykolwiek ustawia std::function do niczego ale twój lambda. Oznacza to, że musi wyśledzić wszystkie możliwe trasy, aby osiągnąć numer std::set we wszystkich jednostkach kompilacji i udowodnić, że żaden z nich nie robi tego.

Może to być możliwe w niektórych przypadkach, ale względnie nieszkodliwe zmiany mogą je zepsuć, nawet jeśli kompilator zdołał to udowodnić.

Z drugiej strony funktor z bezpaństwowym operator() ma łatwe do udowodnienia zachowanie, a optymalizacje w tym zakresie są codziennymi sprawami.

Tak, tak, w praktyce podejrzewam, że std::function może być wolniejszy. Z drugiej strony, rozwiązanie std::function jest łatwiejsze w utrzymaniu niż wymiana make_set, a wymiana czasu programisty na działanie programu jest dość zamienna.

make_set ma poważną wadę, że musi być wyprowadzone wszelkie takie set „S Type z wezwania do make_set. Często set przechowuje stan trwały, a nie coś, co tworzysz na stosie, a następnie pozwól wypaść z zakresu.

Jeśli utworzono statyczny lub globalnego bezstanową lambda auto MyComp = [](A const&, A const&)->bool { ... }, można użyć składni std::set<A, decltype(MyComp)> stworzyć set, które mogą utrzymywać się jeszcze to łatwe dla kompilatora do optymalizacji (ponieważ wszystkie instancje decltype(MyComp) są bezpaństwowców funktory) i inline. Wskażę to, ponieważ przyklejasz set do struct. (A może Twój wsparcie kompilator

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

które chciałbym znaleźć zaskakujące!)

Wreszcie, jeśli martwisz się o wydajność, uważają, że std::unordered_set jest znacznie szybszy (kosztem niezdolności do iteracyjne nad zawartość w kolejności i konieczność napisania/znalezienia dobrego skrótu), a sortowana std::vector jest lepsza, jeśli masz 2-fazowe "wstaw wszystko", a następnie "powtarzaj zawartość zapytania wielokrotnie". Po prostu włóż go najpierw do vector, następnie sortuniqueerase, a następnie użyj darmowego algorytmu equal_range.

Answer 2

Różnica zależy w dużej mierze od optymalizacji kompilatora. Jeśli optymalizuje lambda w postaci std::function, to są one równoważne, jeśli nie, wprowadzasz w tym pierwszym kierunku, którego nie będziesz mieć w drugim.

Answer 3

Jest mało prawdopodobne, że kompilator nie będzie mógł wstawić std :: function call, podczas gdy każdy kompilator obsługujący lambdas prawie na pewno będzie inline dla wersji functor, w tym jeśli ten funktor jest lambda nie ukryty przez std::function .

Można użyć decltype dostać lambda za rodzaj komparatora:

#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")); 
} 

która drukuje:

1 
2 
10 

See it run on Coliru.

Answer 4

Z mojego doświadczenia zabawy z profilera, najlepszy kompromis między wydajnością i urody jest użycie realizację niestandardowych delegata, takich jak:

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

Jako std::function jest zwykle nieco zbyt ciężkie. Nie mogę wypowiedzieć się na temat konkretnych okoliczności, ponieważ ich nie znam.

Answer 5

bezstanowy lambda (to znaczy jeden bez przechwytywania) można rozkładać do wskaźnika funkcji, dzięki czemu może być typu:

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

Inaczej pójdę do roztworu make_set. Jeśli nie użyjesz jednoliniowej funkcji tworzenia, ponieważ jest to niestandardowe, nie będziesz pisał zbyt wiele kodu!

Answer 6

Jeśli jesteś zdeterminowany, aby set jako członek klasy, inicjowanie komparatora w czasie konstruktora, to co najmniej jeden poziom pośredni jest nieuniknione. Uważają, że jeśli chodzi o kompilator wie, można dodać innego konstruktora:

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

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

Gdy masz obiekt typu Foo, typ z set nie niesie informacji, na których konstruktor zainicjowany jego komparator, więc wywołanie prawidłowej wartości lambda wymaga ustawienia w kierunku do wybranego czasu lambda operator().

Ponieważ używasz przechwytujących lambd, możesz użyć funkcji wskaźnikowej typu bool (*)(int, int) jako typu komparatora, ponieważ lambdy bez przechwytywania mają odpowiednią funkcję konwersji. To oczywiście wiązałoby się z pośredniczeniem przez wskaźnik funkcji.