为什么我不能有 std::function 的 std::set 或 std::unordered_set ?

std::set 依赖于比较器，用于确定一个元素是否小于另一个.

std::set relies on a comparator, which is used to determine if one element is less than the other.

它默认使用 std::less，std::less 不适用于 std::functions.
(因为没有办法正确比较 std::functions.)

It uses std::less by default, and std::less doesn't work with std::functions.
(Because there is no way to properly compare std::functions.)

类似地，std::unordered_set 依赖于 std::hash 和 std::equal_to(或它们的自定义替换)，它们也不要对 std::function 进行操作.

Similarly, std::unordered_set relies on std::hash and std::equal_to (or custom replacements for them), which also don't operate on std::functions.

有什么办法让它工作吗?

Is there any way to get it to work anyway?

您可以围绕(或替代)std::function 编写一个包装器，它可以与 std::less、std::equal_to 一起使用code> 和/或 std::hash.

You can write a wrapper around (or a replacement for) std::function that works with std::less, std::equal_to and/or std::hash.

通过类型擦除的力量，你可以转发std::less/std::equal_to/std::hash 到存储在包装器中的对象.

Via power of type erasure, you can forward std::less/std::equal_to/std::hash to objects stored in your wrapper.

这是这种包装器的概念验证.

Here's a proof-of-concept for such a wrapper.

注意事项:

• 您可以指定是否希望 class FancyFunction 与 std::less、std::equal_to 一起使用和 std::hash 分开，通过调整模板参数.
  如果其中一些已启用，您将能够将它们应用到 FancyFunction.

• You can specify whether or not you want the class FancyFunction to work with std::less, std::equal_to and std::hash separetely, by adjusting a template argument.
  If some of those is enabled, you'll be able to apply them to FancyFunction.

当然，只有当它们可以应用于该类型时，您才能从该类型构造 FancyFunction.

Naturally, you'll be able to construct FancyFunction from a type only if they can be applied to that type.

当类型无法提供 std::hash(如果需要)时，会触发静态断言.
SFINAE 关于 std::less 和 std::equal_to 的可用性似乎是不可能的，所以我无法对这些做出类似的断言.

There is a static assertion that fires when a type fails to provide std::hash if it's needed.
It seems to be impossible to SFINAE on availability of std::less and std::equal_to, so I couldn't make similar assertions for those.

理论上，您可以支持不能用于 std::less、std::equal_to 和/或 std 的类型::hash 始终考虑一种等效类型的所有实例，并使用 typeid(T).hash_code() 作为哈希.

In theory, you could support types that don't work with std::less, std::equal_to and/or std::hash by always considering all instances of one type equivalent, and using typeid(T).hash_code() as a hash.

我不确定这种行为是否可取，实现它留给读者作为练习.
(std::less 和 std::equal_to 缺少 SFINAE 将使其难以正确实施.)

I'm not sure if that behavior is desirable or not, implementing it is left as an exercise to the reader.
(Lack of SFINAE for std::less and std::equal_to will make it harder to implement properly.)

不支持为 std::less、std::equal_to 和 std::hash 指定自定义替换，实现这也留给读者作为练习.

Specifying custom replacements for std::less, std::equal_to and std::hash is not supported, implementing that is also left as an exercise to the reader.

(这意味着该实现只能用于将 lambdas 放入常规 std::set，而不是 std::unordered_set.)

(This means that this implementation can only be used to put lambdas into a regular std::set, not std::unordered_set.)

当应用于 FancyFunction 时，std::less 和 std::equal_to 将首先比较存储的函子的类型.

When applied to FancyFunction, std::less and std::equal_to will first compare types of stored functors.

如果类型相同，它们将诉诸于在底层实例上调用 std::less/std::equal_to.

If types are identical, they'll resort to calling std::less/std::equal_to on underlying instances.

(因此，对于两种任意不同的函子类型，std::less 将始终认为其中一个的实例少于另一个的实例.程序调用之间的顺序不稳定.)

(Thus, for two arbitrary different functor types, std::less will always consider instances of one of them less than instances of the other one. The order is not stable between program invocations.)

示例用法:

// 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();
        }
    };
}