Почему я не могу использовать std :: function в качестве типа значения std :: set или std :: unordered_set?

Question

Почему у меня не может быть std::set или std::unordered_set из std::function с?

Можно ли как-нибудь заставить его работать?

Answer 1

Почему я не могу иметь std::set или std::unordered_set из std::function с?

std::set полагается на компаратор, который используется для определения, если одинэлемент меньше другого.

По умолчанию он использует std::less, а std::less не работает с std::function s.
(потому что нет способа правильно сравнить std::functions.)

Аналогично, std::unordered_set полагается на std::hash и std::equal_to (или их замену), которые также не работают на std::function s.

---

Можно ли как-нибудь заставить его работать?

Вы можете написать обертку (или замену) std::function, которая работает с std::less, std::equal_toи / или std::hash.

С помощью типа стирания вы можете перенаправить std::less / std::equal_to / std::hash на объекты, хранящиеся в вашей оболочке.

Вот подтверждение концепции такой оболочки.

Примечания:

• Вы можете указать, хотите ли вы, чтобы class FancyFunction работал с std::less, std::equal_to и std::hash отдельно, путем настройки аргумента шаблона.
  Если некоторые из них включены, вы сможете применить их к FancyFunction.

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

  Существует статическое утверждение, которое срабатывает, когда тип не может предоставить std::hash, если это необходимо.
  Кажется невозможным SFINAE при наличии std::less и std::equal_toпоэтому я не могу сделать аналогичные утверждения для них.

• Теоретически вы можете поддерживать типы, которые не работают с std::less, std::equal_to и / или std::hashвсегда рассматривая все экземпляры одного эквивалентного типа и используя typeid(T).hash_code() в качестве хэша.

  Я не уверен, является ли это поведение желательным или нет, его реализация оставлена ​​читателю в качестве упражнения.
  (Недостаток SFINAE для std::less и std::equal_to затруднит правильную реализацию.)

• Указание пользовательских замен для std::less, std::equal_to и std::hashне поддерживается, реализация которого также оставлена ​​читателю в качестве упражнения.

  (Tэто означает, что эту реализацию можно использовать только для помещения лямбд в обычные std::set, а не std::unordered_set.)

• Применительно к FancyFunction, std::less и std::equal_to сначала сравнивает типы хранимых функторов.

  Если типы идентичны, они будут прибегать к вызову std::less / std::equal_to в базовых экземплярах.

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

Пример использования:

// With `std::set`:

#include <iostream>
#include <set>

struct AddN
{
    int n;
    int operator()(int x) const {return n + x;}
    friend bool operator<(AddN a, AddN b) {return a.n < b.n;}
};

int main()
{   
    using func_t = FancyFunction<int(int), FunctionFlags::comparable_less>;

    // Note that `std::less` can operate on stateless lambdas by converting them to function pointers first. Otherwise this wouldn't work.
    auto square = [](int x){return x*x;};
    auto cube = [](int x){return x*x*x;};

    std::set<func_t> set;
    set.insert(square);
    set.insert(square); // Dupe.
    set.insert(cube);
    set.insert(AddN{100});
    set.insert(AddN{200});
    set.insert(AddN{200}); // Dupe.

    for (const auto &it : set)
        std::cout << "2 -> " << it(2) << '\n';
    std::cout << '\n';
    /* Prints:
     * 2 -> 4   // `square`, note that it appears only once.
     * 2 -> 8   // `cube`
     * 2 -> 102 // `AddN{100}`
     * 2 -> 202 // `AddN{200}`, also appears once.
     */

    set.erase(set.find(cube));
    set.erase(set.find(AddN{100}));

    for (const auto &it : set)
        std::cout << "2 -> " << it(2) << '\n';
    std::cout << '\n';
    /* Prints:
     * 2 -> 4   // `square`
     * 2 -> 202 // `AddN{200}`
     * `cube` and `AddN{100}` were removed.
     */
}


// With `std::unordered_set`:

#include <iostream>
#include <unordered_set>

struct AddN
{
    int n;
    int operator()(int x) const {return n + x;}
    friend bool operator==(AddN a, AddN b) {return a.n == b.n;}
};

struct MulByN
{
    int n;
    int operator()(int x) const {return n * x;}
    friend bool operator==(MulByN a, MulByN b) {return a.n == b.n;}
};

namespace std
{
    template <> struct hash<AddN>
    {
        using argument_type = AddN;
        using result_type = std::size_t;
        size_t operator()(AddN f) const {return f.n;}
    };

    template <> struct hash<MulByN>
    {
        using argument_type = MulByN;
        using result_type = std::size_t;
        size_t operator()(MulByN f) const {return f.n;}
    };
}

int main()
{   
    using hashable_func_t = FancyFunction<int(int), FunctionFlags::hashable | FunctionFlags::comparable_eq>;
    std::unordered_set<hashable_func_t> set;
    set.insert(AddN{100});
    set.insert(AddN{100}); // Dupe.
    set.insert(AddN{200});
    set.insert(MulByN{10});
    set.insert(MulByN{20});
    set.insert(MulByN{20}); // Dupe.

    for (const auto &it : set)
        std::cout << "2 -> " << it(2) << '\n';
    std::cout << '\n';
    /* Prints:
     * 2 -> 40  // `MulByN{20}`
     * 2 -> 20  // `MulByN{10}`
     * 2 -> 102 // `AddN{100}`
     * 2 -> 202 // `AddN{200}`
     */

    set.erase(set.find(AddN{100}));
    set.erase(set.find(MulByN{20}));

    for (const auto &it : set)
        std::cout << "2 -> " << it(2) << '\n';
    std::cout << '\n';
    /* Prints:
     * 2 -> 20  // `MulByN{10}`
     * 2 -> 202 // `AddN{200}`
     * `MulByN{20}` and `AddN{100}` were removed.
     */
}

Реализация:

#include <cstddef>
#include <functional>
#include <experimental/type_traits>
#include <utility>

enum class FunctionFlags
{
    none            = 0,
    comparable_less = 0b1,
    comparable_eq   = 0b10,
    hashable        = 0b100,
};
constexpr FunctionFlags operator|(FunctionFlags a, FunctionFlags b) {return FunctionFlags(int(a) | int(b));}
constexpr FunctionFlags operator&(FunctionFlags a, FunctionFlags b) {return FunctionFlags(int(a) & int(b));}


template <typename T> using detect_hashable = decltype(std::hash<T>{}(std::declval<const T &>()));


template <typename T, FunctionFlags Flags = FunctionFlags::none>
class FancyFunction;

template <typename ReturnType, typename ...ParamTypes, FunctionFlags Flags>
class FancyFunction<ReturnType(ParamTypes...), Flags>
{
    struct TypeDetails
    {
        int index = 0;
        bool (*less)(const void *, const void *) = 0;
        bool (*eq)(const void *, const void *) = 0;
        std::size_t (*hash)(const void *) = 0;

        inline static int index_counter = 0;
    };

    template <typename T> const TypeDetails *GetDetails()
    {
        static TypeDetails ret = []()
        {
            using type = std::remove_cv_t<std::remove_reference_t<T>>;

            TypeDetails d;

            d.index = TypeDetails::index_counter++;

            if constexpr (comparable_less)
            {
                // We can't SFINAE on `std::less`.
                d.less = [](const void *a_ptr, const void *b_ptr) -> bool
                {
                    const type &a = *static_cast<const FancyFunction *>(a_ptr)->func.template target<type>();
                    const type &b = *static_cast<const FancyFunction *>(b_ptr)->func.template target<type>();
                    return std::less<type>{}(a, b);
                };
            }

            if constexpr (comparable_eq)
            {
                // We can't SFINAE on `std::equal_to`.
                d.eq = [](const void *a_ptr, const void *b_ptr) -> bool
                {
                    const type &a = *static_cast<const FancyFunction *>(a_ptr)->func.template target<type>();
                    const type &b = *static_cast<const FancyFunction *>(b_ptr)->func.template target<type>();
                    return std::equal_to<type>{}(a, b);
                };
            }

            if constexpr (hashable)
            {
                static_assert(std::experimental::is_detected_v<detect_hashable, type>, "This type is not hashable.");
                d.hash = [](const void *a_ptr) -> std::size_t
                {
                    const type &a = *static_cast<const FancyFunction *>(a_ptr)->func.template target<type>();
                    return std::hash<type>(a);
                };
            }

            return d;
        }();
        return &ret;
    }

    std::function<ReturnType(ParamTypes...)> func;
    const TypeDetails *details = 0;

  public:
    inline static constexpr bool
        comparable_less = bool(Flags & FunctionFlags::comparable_less),
        comparable_eq   = bool(Flags & FunctionFlags::comparable_eq),
        hashable        = bool(Flags & FunctionFlags::hashable);

    FancyFunction(decltype(nullptr) = nullptr) {}

    template <typename T>
    FancyFunction(T &&obj)
    {
        func = std::forward<T>(obj);    
        details = GetDetails<T>();
    }

    explicit operator bool() const
    {
        return bool(func);
    }

    ReturnType operator()(ParamTypes ... params) const
    {
        return ReturnType(func(std::forward<ParamTypes>(params)...));
    }

    bool less(const FancyFunction &other) const
    {
        static_assert(comparable_less, "This function is disabled.");
        if (int delta = bool(details) - bool(other.details)) return delta < 0;
        if (!details) return 0;
        if (int delta = details->index - other.details->index) return delta < 0;
        return details->less(this, &other);
    }

    bool equal_to(const FancyFunction &other) const
    {
        static_assert(comparable_eq, "This function is disabled.");
        if (bool(details) != bool(other.details)) return 0;
        if (!details) return 1;
        if (details->index != other.details->index) return 0;
        return details->eq(this, &other);
    }

    std::size_t hash() const
    {
        static_assert(hashable, "This function is disabled.");
        if (!details) return 0;
        return details->hash(this);
    }

    friend bool operator<(const FancyFunction &a, const FancyFunction &b) {return a.less(b);}
    friend bool operator>(const FancyFunction &a, const FancyFunction &b) {return b.less(a);}
    friend bool operator<=(const FancyFunction &a, const FancyFunction &b) {return !b.less(a);}
    friend bool operator>=(const FancyFunction &a, const FancyFunction &b) {return !a.less(b);}
    friend bool operator==(const FancyFunction &a, const FancyFunction &b) {return a.equal_to(b);}
    friend bool operator!=(const FancyFunction &a, const FancyFunction &b) {return !a.equal_to(b);}
};

namespace std
{
    template <typename T, FunctionFlags Flags> struct hash<FancyFunction<T, Flags>>
    {
        using argument_type = FancyFunction<T, Flags>;
        using result_type = std::size_t;
        size_t operator()(const FancyFunction<T, Flags> &f) const
        {
            return f.hash();
        }
    };
}

Answer 2

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

К сожалению, не существует порядка между функциями.Предположим, что у вас есть две функции f1() и f2(), что будет означать f1 < f2?

Также равенство на самом деле не определено.Например, если у вас есть

int fun1(int) { return 1; }
int fun2(int) { return 1; }
function<int(int)> f1=fun1, f2=fun2; 

Должны ли f1 и f2 быть одним и тем же значением, если вы вставите их в набор (потому что это всегда один и тот же результат), или это что-то другое (потому что это другоефункции, хотя они имеют одинаковое тело)?

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

struct Comp {
    using T = function<int(int)>;
    bool operator()(const T &lhs, const T &rhs) const 
    {
        return &lhs < &rhs;
    }
};

set <function<int(int)>,Comp> s; 

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

Я думаю, что лучший способ продолжить - это использовать оболочку со строкой члена, которая определяет идентификатор, и использовать этот идентификатор для сортировки элементов в наборе (или для хеширования в случае* * тысяча двадцать-одина)

Answer 3

Ну, вы можете проверять только указатели функций на (не) равенство, а не порядок. И то, должны ли две функции с одним и тем же поведением сравниваться по-разному не так уж просто, как вы, возможно, надеетесь.

Далее, вы можете не только хранить указатели на функции,но и другие вызываемые.Нет гарантии, что произвольный пользовательский класс имеет строгий слабый порядок.В качестве примера, лямбды не делают.

И, наконец, как бы вы заказывали вызываемые элементы разных типов?

Вы можете сделать тот же Аргумент для хеширования (необходимый для неупорядоченных контейнеров), что и для заказа(необходимо для заказанных контейнеров).Даже сравнения равенства, необходимого для неупорядоченных контейнеров, может не существовать.

Answer 4

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

• C ++ не являются математическими функциями.Что если «функция» удерживает состояние?И это состояние отличается для разных экземпляров?
• На ваше предложение использовать «адрес точки входа»: Опять же, рассмотрите состояние.std::function может содержать привязку некоторой функции / метода к некоторым параметрам.Что это за «адрес точки входа»?Ответ: Некоторая функция / метод в пакете "bind".И тогда этот «адрес точки входа» однозначно идентифицирует эту функцию?Ответ: Нет.
• Предположим, у вас есть две разные функции (по «адресу точки входа»), которые фактически идентичны в том смысле, что они дают одинаковый результат для каждого параметра?Это может быть даже один и тот же исходный код или машинный код.Равны ли эти функции или нет?(Если нет, то почему, если они поведенчески идентичны и не могут быть различены любым вызывающим абонентом?)

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