Лучшее решение для сравнения / поиска нескольких целых чисел в массиве

Question

Я просто хотел спросить вас, какое решение наиболее эффективно для следующего сравнения:

Я получаю значение из своей функции.Например 6.Теперь я хочу сравнить это с несколькими целыми числами и, если оно одинаково (true), в противном случае (false), как типичное if-statement.

На данный момент я использовал array, но я почти уверен, что для каждого элемента массива очень не нужно постоянно проверять, находится ли значение в нем или нет.

Может кто-нибудь показать мне более точный и эффективный способ?

С уважением

Answer 1

Чтобы добавить к предыдущим ответам, вот простой сравнительный тест, сравнивающий unordered_set с vector / find и vector / binary_search.

LiveДемо

#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 2

Спасибо за советы!

Мое новое решение (предложение @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; }


}

Answer 3

Как @Sam Varshavchik уже упоминал в комментариях, вы можете использовать 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 << "Found\n": std::cout << "Not Found\n";

   return 0;
}