比较/搜索数组中多个整数的最佳解决方案

Question

我只是想问你，进行以下比较的最有效解决方案是什么：

我从我的函数中获取值。例如6.现在我想将其与多个整数进行比较，如果它相同(true(，否则(false(像典型的if-statement。

现在，我已经使用了array但我很确定每个数组元素都非常没有必要一直检查值是否在其中。

谁能告诉我一种更准确、更有效的方法？

问候

Answer 1

正如 Varshavchik 在注释中已经提到的@Sam，您可以使用std::unordered_set<>将所有值存储在数组及其查找std::unordered_set::find()中，这在平均情况下具有恒定的时间复杂度。

下面是示例代码：

#include <iostream>
#include <unordered_set>
int fun()
{
/* return some integer */
return 1;
}
int main()
{
std::unordered_set<int> Arr = {1,2,3,4,5,6};
std::cout << std::boolalpha << (Arr.find( fun() ) != Arr.cend());
// or
// (Arr.find( fun() ) != Arr.cend()) ?  std::cout << "Foundn": std::cout << "Not Foundn";
return 0;
}

Answer 2

为了补充以前的答案，这里有一个简单的基准测试，将unordered_set与vector/find和vector/binary_search进行比较。

现场演示

#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_set>
#include <random>
#include <boost/timer/timer.hpp>
std::random_device rd;     // only used once to initialise (seed) engine
std::mt19937 rng(rd());    // random-number engine used (Mersenne-Twister in this case)
std::uniform_int_distribution<int> uni(0, 6); // guaranteed unbiased
int fun()
{
/* return some integer */
return uni(rng);
}
const size_t nTries = 1000000;
int main()
{  
volatile bool isFound;
{ // unordered_set
std::unordered_set<int> vals = {1,2,3,4,5,6};
{
boost::timer::auto_cpu_timer timer;
for(volatile size_t i=0; i<nTries; i++)
isFound = (vals.find(fun()) != vals.cend());
}     
}
{ // vector
std::vector<int> vals = {1,2,3,4,5,6};
{
boost::timer::auto_cpu_timer timer;
for(volatile size_t i=0; i<nTries; i++)
isFound = (std::find(vals.cbegin(), vals.cend(), fun()) != vals.cend());
}
}
{ // vector, binary search
std::vector<int> vals = {1,2,3,4,5,6};
std::sort (vals.begin(), vals.end());
{
boost::timer::auto_cpu_timer timer;
for(volatile size_t i=0; i<nTries; i++)
isFound = std::binary_search (vals.cbegin(), vals.cend(), fun());
}
}
return 0;
}

数字变化很大，gcc 和 clang 的行为也不同，但似乎使用unordered_set是一个安全的选择。

Answer 3

感谢您的建议！

我的新解决方案(@SamVarshavchik建议(现在如下所示：

std::unorderet_set<int> values= { 7, 8, 10, 13, 14, 16, 60, 17, 19, 24, 26, 27, 28, 33, 34, 39 };
bool check_value() {

if (values.find( grabvalues() ) != values.cend()) { return true; }
else { return false; }

}