C++ 函数判断给定函数是否单射

Question

这似乎是一个奇怪的问题，但我如何创建一个 C++ 函数来判断一个给定的 C++ 函数是否将 X 类型的变量作为参数并返回 X 类型的变量，在空间中是单射的这些变量的机器表示，即永远不会为传递给它的两个不同变量返回相同的变量？

(对于那些不是数学专业的人，如果您仍然对单射的定义感到困惑，可以查看此页面:http://en.wikipedia.org/wiki/Injective_function)

例如函数

double square(double x) { return x*x}; 

不是单射的，因为 square(2.0) = square(-2.0),

但是函数

double cube(double x) { return x*x*x};

显然是。

目标是创建一个函数

 template <typename T>
 bool is_injective(T(*foo)(T))
 {
    /* Create a set std::set<T> retVals;
       For each element x of type T: 
       if x is in retVals, return false;
       if x is not in retVals, add it to retVals;
       Return true if we made it through the above loop.
    */
 }

我想我可以实现该过程，只是我不确定如何遍历类型 T 的每个元素。我该如何完成？

此外，尝试创建这样的函数可能会出现什么问题？

Answer 1

您需要测试所有可能的长度为 sizeof(T) 的位模式.

最近有一篇广为流传的关于这个话题的博文:There are Only Four Billion Floats - So Test Them All!

在那篇文章中，作者能够在 90 秒内测试所有 32 位 float 。事实证明，64 位值需要几个世纪的时间。

所以这只适用于小输入类型。

多个输入、结构或任何带有指针的东西都将变得不可能很快。

顺便说一句，即使是 32 位值，您也可能会耗尽系统内存，试图将所有输出值存储在 std::set 中。 ，因为 std::set为指针使用大量额外内存。相反，您应该使用足够大的位图来容纳所有 2^sizeof(T)输出值。专业std::vector<bool>应该管用。这需要 2^sizeof(T) / 8字节的内存。