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() и местоположение определения в любом случае не будет заданной конструкцией.
Есть еще идеи, такие как использование делегирования. Если вы хотите более подробное объяснение всех решений, прочитайте ответы:)
6 ответов
Да std::function вводит почти неизбежное косвенное отношение к вашему set, В то время как компилятор всегда может теоретически выяснить, что все set"s 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) являются функторами без состояния) и встроенными. Я указываю на это, потому что вы придерживаетесь set в struct, (Или ваш компилятор поддерживает
struct Foo {
auto mySet = make_set<int>([](int l, int r){ return l<r; });
};
что я нахожу удивительным!)
Наконец, если вы беспокоитесь о производительности, учтите, что std::unordered_set намного быстрее (за счет невозможности перебирать содержимое по порядку и необходимости писать / находить хороший хеш), и это сортирует std::vector Лучше, если у вас есть 2-фазный "вставить все", а затем "повторно запрашивать содержимое". Просто вставьте это в vector будет первый sortuniqueerase, а затем использовать бесплатный equal_range алгоритм.
Маловероятно, что компилятор сможет встроить вызов 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
Лямбда без сохранения состояния (т. Е. Та, у которой нет перехватов) может распадаться на указатель функции, поэтому ваш тип может быть:
std::set<int, bool (*)(int, int)> numbers;
В противном случае я бы пошел на make_set решение. Если вы не будете использовать функцию создания в одну строку, потому что она нестандартна, вы не получите много написанного кода!
Если вы полны решимости иметь set как член класса, инициализирующий его компаратор во время конструктора, тогда по крайней мере один уровень косвенности неизбежен. Учтите, что, насколько известно компилятору, вы можете добавить еще один конструктор:
Foo () : numbers ([](int x, int y)
{
return x < y;
})
{
}
Foo (char) : numbers ([](int x, int y)
{
return x > y;
})
{
}
После того, как у вас есть объект типа Fooтип set не несет информацию о том, какой конструктор инициализировал свой компаратор, поэтому для вызова правильной лямбды требуется косвенное обращение к выбранной лямбда времени выполнения operator(),
Поскольку вы используете лямбды без захвата, вы можете использовать тип указателя на функцию bool (*)(int, int) как ваш тип компаратора, поскольку лямбды без захвата имеют соответствующую функцию преобразования. Это, конечно, будет связано с косвенным обращением через указатель на функцию.
Исходя из моего опыта работы с профилировщиком, лучший компромисс между производительностью и красотой заключается в использовании пользовательской реализации делегата, такой как:
https://codereview.stackexchange.com/questions/14730/impossibly-fast-delegate-in-c11
Как std::function обычно слишком тяжелый. Я не могу комментировать ваши конкретные обстоятельства, потому что я их не знаю.
Разница во многом зависит от оптимизации вашего компилятора. Если он оптимизирует лямбда в std::function они эквивалентны, если вы не введете косвенное указание в первом, которого у вас не будет во втором.