Qix*_*Qix 7 c++ unordered-map stdset std-function
为什么我不能有一个std::set或std::unordered_set的std::functionS'
有什么方法可以让它工作吗？
你可以很好地创建一个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插入一个集合(因为它总是相同的结果),或者它是不同的东西(因为即使它们具有相同的主体,它是不同的功能),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)
为什么我不能有 a
std::set或std::unordered_setofstd::functions？
std::set依赖于比较器，该比较器用于确定一个元素是否小于另一个元素。
它std::less默认使用，并且std::less不适用于std::functions。
（因为没有办法正确比较std::functions。）
同样，std::unordered_set依赖于std::hashand std::equal_to（或它们的自定义替换），它们也不适用于std::functions。
有什么办法让它发挥作用吗？
您可以编写一个与,和/或 一起std::function使用的包装器（或替代品）。std::lessstd::equal_tostd::hash
通过类型擦除的能力，您可以将std::less//转发std::equal_to到std::hash存储在包装器中的对象。
这是此类包装器的概念验证。
笔记：
您可以通过调整模板参数来指定是否希望分别与和一起class FancyFunction使用。
如果启用其中一些，您将能够将它们应用到.std::lessstd::equal_tostd::hashFancyFunction
FancyFunction当然，只有当它们可以应用于该类型时，您才能够从该类型进行构造。
std::hash当类型无法提供所需的静态断言时，会触发静态断言。
SFINAE 似乎不可能对std::less和的可用性做出判断std::equal_to，因此我无法对这些做出类似的断言。
理论上，您可以支持不能与 , 一起使用的类型std::less，std::equal_to和/或std::hash通过始终考虑一种等效类型的所有实例并用作typeid(T).hash_code()哈希。
我不确定这种行为是否可取，实现它是留给读者的练习。
（缺乏 SFINAEstd::less和std::equal_to将使正确实施变得更加困难。）
不支持指定 和 的自定义替换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();
}
};
}