C++11 std:: установить функцию сравнения лямбда


я хочу создать 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, лямда, любой callable объект.

есть также возможность использовать указатель на функцию, но если нет проблемы скорости, я думаю std::function лучше (если вы используете C++11).

есть возможность определить лямбда-функцию где-то еще, но тогда вы ничего не получите от функции сравнения, являющейся лямбда-выражением, так как вы также можете сделать ее классом с operator() и расположение определения не было бы заданной конструкцией в любом случае.

есть еще идеи, такие как использование делегирования. Если вы хотите получить более подробное объяснение всех решений, прочитайте ответы :)

6 67

6 ответов:

да, a std::function вводит почти неизбежное косвенное обращение к вашему set. В то время как компилятор всегда может, в теории, выяснить, что все использование вашего set ' s std::function включает вызов его на лямбду, которая всегда является точно такой же лямбдой, которая является одновременно жесткой и чрезвычайно хрупкой.

хрупкий, потому что перед компилятором может доказать себе, что все вызовы к этому std::function на самом деле звонки на ваш лямбда, он должен доказать, что нет доступа к вашему std::set когда-нибудь задает std::function все, кроме лямбды. Это означает, что он должен отслеживать все возможные маршруты, чтобы добраться до вашего std::set во всех единицах компиляции и доказать, что ни один из них не делает этого.

это может быть возможно в некоторых случаях, но относительно безобидные изменения могут нарушить его, даже если ваш компилятор сумел это доказать.

С другой стороны, функтор с имеет легко доказать поведение, и оптимизации с участием, которые являются повседневными вещами.

так да, на практике я бы заподозрил std::function может быть медленнее. С другой стороны, std::function решение легче поддерживать, чем make_set одно, и обменивать время программиста для представления программы довольно заменим.

make_set имеет серьезный недостаток, что любая такая set'S тип должен быть выведен из Звонка make_set. Часто set сохраняет постоянное состояние, а не то, что вы создаете в стеке, а затем выходите из области видимости.

если вы создали статическая или глобальная лямбда без состояния auto MyComp = [](A const&, A const&)->bool { ... } можно использовать std::set<A, decltype(MyComp)> синтаксис для создания set это может сохраняться, но компилятору легко оптимизировать (потому что все экземпляры decltype(MyComp) являются функторами без состояния) и inline. Я указываю на это, потому что вы вставляете set на struct. (Или ваш компилятор поддерживает

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

который я бы нашел удивительным!)

наконец, если вы беспокоитесь о производительности, следует, что std::unordered_set намного быстрее (за счет невозможности перебирать содержимое по порядку и необходимости писать / находить хороший хэш), и что сортировка std::vector лучше, если у вас есть 2-фазный "вставить все", а затем "повторно запросить содержимое". Просто набейте его в vector во-первых, тогда sortuniqueerase, затем используйте бесплатный .

маловероятно, что компилятор сможет встроить вызов std:: function, тогда как любой компилятор, поддерживающий лямбды, почти наверняка встроит версию функтора, в том числе если этот функтор является лямбдой, не скрытой std::function.

вы можете использовать decltype, чтобы получить тип компаратора лямбды:

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

лямбда без состояния (т. е. без захватов) может распадаться на указатель функции, поэтому ваш тип может быть:

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

в противном случае я бы пошел на make_set решение. Если вы не будете использовать однострочную функцию создания, потому что это нестандартно, вы не получите много кода!

по моему опыту игры с профилировщиком, лучшим компромиссом между производительностью и красотой является использование пользовательской реализации делегата, например:

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

Как std::function обычно немного тяжеловато. Я не могу комментировать ваши конкретные обстоятельства, так как я их не знаю.

если вы решили иметь set как член класса, инициализирующий свой компаратор во время конструктора, то по крайней мере один уровень косвенности неизбежен. Учтите, что, насколько известно компилятору, вы можете добавить еще один конструктор:

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

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

когда у вас есть объект типа Foo, тип set не несет информации о том, какой конструктор инициализировал свой компаратор, поэтому для вызова правильной лямбды требуется косвенное обращение к времени выполнения выбранная лямбда operator().

поскольку вы используете captureless лямбда-выражения, вы можете использовать тип указателя на функцию bool (*)(int, int) как ваш тип компаратора, как captureless лямбды имеют соответствующую функцию преобразования. Это, конечно, будет включать косвенное использование указателя функции.

разница сильно зависит от оптимизации вашего компилятора. Если он оптимизирует лямбда в std::function они эквивалентны, если вы не вводите косвенность в первом, которую вы не будете иметь во втором.