为什么我不能将 std::function 用作 std::set 或 std::unordered_set 值类型？

Question

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

有什么办法让它正常工作吗？

Answer 1

通用函数没有有意义的相等操作，由std::function持有。

C++ 函数不是数学函数。如果 "function" 保持状态怎么办？那个状态对于不同的实例是不同的？
关于您使用 "entry point address" 的建议：再次，考虑状态。 std::function 可以绑定一些 function/method 到一些参数。那是什么"entry point address"？答："bind" 包中的一些 function/method。然后 "entry point address" 是否唯一标识该功能？答：没有。
假设您有两个不同的函数（"entry point address"），它们实际上是相同的，因为它们对每个参数都产生相同的结果？它们甚至可能是相同的源代码——或机器代码。这些函数是否相等？（如果不是，为什么不呢，如果它们在行为上是相同的并且不能被任何调用者区分？）

您的特定用例（将 std::function 粘在一个集合中）可能不会受到上述问题的影响。在那种情况下，只需将 std::function 实例包装在您自己的一个小结构中（通过直接包含或通过间接）（转发对包含的函数对象的调用）并将这些东西放入您的集合中。

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;

然后您可以在集合中插入函数。但这不会很好地工作，因为你取的是元素的地址，如果交换相同的元素，顺序是不同的。

我认为最好的方法是使用一个带有定义 id 的成员字符串的包装器，并使用这个 id 对集合中的元素进行排序（或者在 unordered_set)

Answer 3

好吧，您只能检查函数指针的（不）相等性，而不能检查顺序。 And whether two functions with the same behavior must compare differently 并不像您希望的那样一成不变。

接下来，您不仅可以存储函数指针，还可以存储其他可调用对象。不能保证任何随机用户定义的 class 具有严格的弱排序。例如，lambda 就不会。

最后，您将如何订购不同类型的可调用对象？

您可以为散列（无序容器需要）和排序（有序容器需要）创建相同的参数。甚至可能不存在无序容器所需的相等比较。

Answer 4

Why can't I have a std::set or std::unordered_set of std::functions?

std::set依赖于一个比较器，用于判断一个元素是否小于另一个。

默认使用std::less，std::less不适用于std::function。
（因为无法正确比较 std::functions。）

同样，std::unordered_set 依赖于 std::hash 和 std::equal_to（或它们的自定义替换），它们也不在 std::function 上运行。

Is there any way to get it to work anyway?

您可以围绕 std::function 编写一个包装器（或替代），它适用于 std::less、std::equal_to and/or std::hash.

通过 类型擦除 的强大功能，您可以将 std::less/std::equal_to/std::hash 转发到存储在包装器中的对象。

这是此类包装器的概念验证。

备注：

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

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

有一个静态断言会在类型无法提供 std::hash 需要时触发。
std::less 和 std::equal_to 的可用性对 SFINAE 来说似乎是不可能的，所以我无法对它们做出类似的断言。
理论上，您可以通过始终考虑所有实例来支持不适用于 std::less、std::equal_to and/or std::hash一种等效类型，并使用 typeid(T).hash_code() 作为散列。

我不确定这种行为是否可取，实施它留给 reader.
作为练习。（缺少 std::less 和 std::equal_to 的 SFINAE 将使其更难正确实施。）
不支持为 std::less、std::equal_to 和 std::hash 指定自定义替换，实现它也留给 reader 作为练习.

（这意味着此实现只能用于将 lambda 放入常规 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();
        }
    };
}

为什么我不能将 std::function 用作 std::set 或 std::unordered_set 值类型？

Why can't I use std::function as a std::set or std::unordered_set value type?

c++

unordered-map

stdset

std-function