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

Question

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

c++unordered-mapstd-functionstdset

9

为什么我不能拥有一个存储 std::function 的 std::set 或者 std::unordered_set 呢？

是否有任何办法可以让它工作呢？

- Qix - MONICA WAS MISTREATED

3

“doesn't work”的意思是什么？ - JVApen

6

因为你不能将 std::less（std::set所需）或 std::hash 和 std::equal_to（std::unordered_set所需）应用于它。 - HolyBlackCat

1

@Qix：编译错误信息会非常有用！ - JVApen

4

针对 std::set 的案例，什么因素会让一个函数“小于”另一个函数？这些标准是什么？ - PaulMcKenzie

3

你使用集合的目的是什么？如果你的std::function有状态，那么你可能永远无法获得相同的键/哈希值，因此使用集合没有意义。为什么不使用向量？如果你想识别函数，那么具有增量ID作为键的映射可能更加合适。你将保留id作为实际函数的参考。 - Phil1970

显示剩余6条评论

4个回答

4

为什么我不能使用std :: set或std :: unordered_set存储std :: function？

std :: set依赖于比较器，用于确定一个元素是否小于另一个元素。它默认使用std :: less，而std :: less无法处理std :: function。(因为没有办法正确比较std :: function)。同样，std :: unordered_set依赖于std :: hash和std :: equal_to(或其自定义替代品)，它们也无法操作std :: function。

有没有办法让它正常工作？

您可以编写一个包装器(或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而类型未提供，则会触发静态断言。似乎不可能对std::less和std::equal_to的可用性进行SFINAE，因此我无法为这些内容做出类似的断言。

理论上，您可以通过始终将一个类型的所有实例视为等效，并使用typeid(T).hash_code()作为哈希值，来支持不适用于std::less、std::equal_to和/或std::hash的类型。我不确定这种行为是否可取，将其实现留给读者作为练习。(缺少std::less和std::equal_to的SFINAE将使其更难以正确实现。)

不支持指定std::less、std::equal_to和std::hash的自定义替代方案，将其实现也留给读者作为练习。(这意味着此实现仅可用于将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();
        }
    };
}

- HolyBlackCat

这是这里最完整的答案。感谢您抽出时间！ :) - Qix - MONICA WAS MISTREATED

@HolyBlackCat 那真的很不错。 - JeJo

2

好的，你只能检查函数指针的（不）相等性，而不能比较它们的顺序。两个具有相同行为的函数是否必须以不同方式进行比较并不像您可能希望的那样清晰明了。

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

最后，您如何对不同类型的可调用对象进行排序？

您可以为哈希（需要无序容器）和排序（需要有序容器）提出相同的论点。甚至无序容器所需的相等比较也可能不存在。

- Deduplicator

1

对于由std::function持有的一般函数，没有有意义的等式操作。

C++函数不是数学函数。如果“函数”持有状态怎么办？而且这个状态对于不同的实例是不同的？
针对您使用“入口点地址”的建议：再次考虑状态。一个std::function可以持有某个函数/方法绑定到某些参数。那么它的“入口点地址”是什么？答案：在“绑定”包中的某个函数/方法。那么这个“入口点地址”是否唯一地标识该函数？答案：不是。
假设您有两个不同的函数（通过“入口点地址”），实际上它们在每个参数产生相同的结果，那么怎么办？它们甚至可以是相同的源代码-或机器代码。这些函数是相等的还是不相等的？（如果不是，为什么不是，如果它们的行为相同，并且不能被任何调用者区分？）

你的特定用例（将std :: function放入集合中）可能不会受到上述问题的影响。在这种情况下，只需将std :: function实例包装在自己的小结构中（通过直接包含或通过间接方式），并将这些内容放入集合中（转发调用到包含的函数对象）。请保留HTML标签。

- davidbak

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Christophe · Accepted Answer

你完全可以创建一个函数的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对集合中的元素进行排序（或在无序集合的情况下进行哈希）。