Сравнение трюков в С++

Ответ 1

Простой способ

Самый простой способ - написать оболочку функции-члена, которая называется in() вокруг std::find, с парой итераторов для поиска данных. Я написал простую функцию-член template<class It> in(It first, It last) для этого

template<class It>
bool in(It first, It last) const
{
    return std::find(first, last, data) != last;
}

Если у вас нет доступа к источнику foo, вы можете записать не-членные функции подписи template<class T> bool in(foo const&, std::initializer_list<T>) и т.д. и называть его как

in(f, {1, 2, 3 });

Трудный путь

Но отпустите полностью за борт: просто добавьте еще две перегрузки public:

• один принимает параметр std::initializer_list, который вызывает предыдущий стераторами begin() и end() соответствующего аргумента списка инициализатора.
• один для произвольного контейнера в качестве ввода, который будет немного терять диспетчеризацию еще две private перегрузки хедера detail_in():
  • одна перегрузка делает трюк SFINAE с возвращаемым типом возврата decltype(c.find(data), bool()), который будет удален из набора перегрузки, если в рассматриваемом контейнере c нет функции-члена find(), и возвращается bool в противном случае ( это достигается за счет злоупотребления запятой внутри decltype)
  • одна резервная перегрузка, которая просто принимает итераторы begin() и end() и передает на исходный in() два итератора

Поскольку теги для хелпера detail_in() образуют иерархию наследования (так же, как и стандартные теги итератора), первая перегрузка будет соответствовать ассоциативным контейнерам std::set и std::unordered_set и их нескольким кузенам. Все остальные контейнеры, включая C-массивы, std::array, std::vector и std::list, будут соответствовать второй перегрузке.

#include <algorithm>
#include <array>
#include <initializer_list>
#include <type_traits>
#include <iostream>
#include <set>
#include <unordered_set>
#include <vector>

class foo
{
public:
    int data;

    template<class It>
    bool in(It first, It last) const
    {
        std::cout << "iterator overload: ";
        return std::find(first, last, data) != last;
    }

    template<class T>
    bool in(std::initializer_list<T> il) const
    {
        std::cout << "initializer_list overload: ";
        return in(begin(il), end(il));
    }

    template<class Container>
    bool in(Container const& c) const 
    {
        std::cout << "container overload: ";
        return detail_in(c, associative_container_tag{});    
    }

private:
    struct sequence_container_tag {};
    struct associative_container_tag: sequence_container_tag {};

    template<class AssociativeContainer>
    auto detail_in(AssociativeContainer const& c, associative_container_tag) const 
    -> decltype(c.find(data), bool())
    {
        std::cout << "associative overload: ";
        return c.find(data) != end(c);    
    }

    template<class SequenceContainer> 
    bool detail_in(SequenceContainer const& c, sequence_container_tag) const
    {
        std::cout << "sequence overload: ";
        using std::begin; using std::end;
        return in(begin(c), end(c));    
    }
};

int main()
{
    foo f{1};
    int a1[] = { 1, 2, 3};
    int a2[] = { 2, 3, 4};

    std::cout << f.in({1, 2, 3}) << "\n";
    std::cout << f.in({2, 3, 4}) << "\n";

    std::cout << f.in(std::begin(a1), std::end(a1)) << "\n";
    std::cout << f.in(std::begin(a2), std::end(a2)) << "\n";

    std::cout << f.in(a1) << "\n";
    std::cout << f.in(a2) << "\n";

    std::cout << f.in(std::array<int, 3>{ 1, 2, 3 }) << "\n";
    std::cout << f.in(std::array<int, 3>{ 2, 3, 4 }) << "\n";

    std::cout << f.in(std::vector<int>{ 1, 2, 3 }) << "\n";
    std::cout << f.in(std::vector<int>{ 2, 3, 4 }) << "\n";

    std::cout << f.in(std::set<int>{ 1, 2, 3 }) << "\n";
    std::cout << f.in(std::set<int>{ 2, 3, 4 }) << "\n";

    std::cout << f.in(std::unordered_set<int>{ 1, 2, 3 }) << "\n";
    std::cout << f.in(std::unordered_set<int>{ 2, 3, 4 }) << "\n";    
}

Живой пример, который - для всех возможных контейнеров - печатает 1 и 0 для оба набора чисел.

Варианты использования для перегрузки std::initializer_list предназначены для тестирования членов для небольших наборов чисел, которые вы явно выписываете при вызове кода. Он имеет сложность O(N), но избегает любых распределений кучи.

Для любых тяжелых испытаний, таких как тестирование членства больших наборов, вы можете сохранить числа в ассоциативном контейнере, например std::set, или его кузенах multi_set или unordered_set. Это будет полезно для кучи при сохранении этих чисел, но имеет сложность поиска O(log N) или даже O(1).

Но если у вас есть только контейнер последовательности с числами, вы можете также бросить это в класс, и он будет счастливо вычислять членство для вас в O(N) времени.

Ответ 2

Есть много способов сделать это с помощью STL.

Если у вас есть невероятно большое количество элементов, и вы хотите проверить, является ли ваш данный элемент членом этого набора, используйте set или unordered_set. Они позволяют вам проверять членство в log n и постоянном времени соответственно.

Если вы сохраните элементы в отсортированном массиве, то binary_search также проверит членство в log n время.

Для небольших массивов linear search может, однако, преформировать значительно быстрее (поскольку нет ветвления). Линейный поиск может даже сделать 3-8 сравнений за время, когда бинарный поиск "прыгает" . Это сообщение в блоге предполагает наличие точки безубыточности примерно на 64 элементах, ниже которых линейный поиск может быть быстрее, хотя это, очевидно, зависит на реализацию STL, оптимизацию компилятора и предсказание ветвей вашей архитектуры.

Ответ 3

Если data действительно является интегральным или перечислимым типом, вы можете использовать switch:

switch (data) {
  case 1:
  case 2:
  case 2000:
  case 6000:
  case /* whatever other values you want */:
    act_on_the_group();
    break;
  default:
    act_on_not_the_group();
    break;
}

Ответ 4

Ответы с использованием std::initializer_list прекрасны, но я хочу добавить еще одно возможное решение, которое именно то, что вы пытаетесь использовать с этим вариатором C в безопасном и современном виде: Использование С++ 11 variadic шаблоны

template<typename... NUMBERS>
bool any_equal( const foo& f , NUMBERS&&... numbers )
{
    auto unpacked = { numbers... };

    return std::find( std::begin( unpacked ) , std::end( unpacked ) , f.data ) 
           != std::end( unpacked );
};

Конечно, это работает только в том случае, если все переданные значения имеют один и тот же тип. Если список инициализаторов unpacked не выводится и не инициализируется.

Тогда:

bool equals = any_equal( f , 1,2,3,4,5 );

РЕДАКТИРОВАТЬ: Вот метафайла are_same, чтобы все переданные числа имели один и тот же тип:

template<typename HEAD , typename... TAIL>
struct are_same : public and_op<std::is_same<HEAD,TAIL>::value...>
{};

Где and_op выполняет n-ary логическое и:

template<bool HEAD , bool... TAIL>
struct and_op : public std::integral_constant<bool,HEAD && and_op<TAIL...>::value>
{};

template<>
struct and_op<> : public std::true_type
{};

Это позволяет принудительно использовать номера одного и того же типа:

template<typename... NUMBERS>
bool any_equal( const foo& f , NUMBERS&&... numbers )
{
    static_assert( all_same<NUMBERS...>::value , 
                   "ERROR: You should use numbers of the same type" );


    auto unpacked = { numbers... };

    return std::find( std::begin( unpacked ) , std::end( unpacked ) , f.data ) 
           != std::end( unpacked );
};

Ответ 5

Любая оптимизация будет зависеть от свойств сравниваемого набора чисел.

Если существует определенная верхняя граница, вы можете использовать std::bitset. Тестирование членства (то есть индексация в битете, который ведет себя как массив), - это O (1), а также несколько быстрых инструкций. Это часто лучшее решение до пределов в сотни, хотя в зависимости от приложения миллионы могут быть практичными.

Ответ 6

Это не очень, но это должно работать:

class foo {
    bool equals(int a) { return a == data; }
    bool equals(int a, int b) { return (a == data) || (b == data); }
    bool equals(int a, int b, int c) {...}     
    bool equals(int a, int b, int c, int d) {...} 
private:
    int data; 
}

И так далее. Это даст вам точный синтаксис, который вам нужен. Но если вы после полностью переменного количества аргументов, то может быть как вектор, так и std:: initalizer:

Смотрите: http://en.cppreference.com/w/cpp/utility/initializer_list

Этот пример показывает это в действии:

#include <assert.h>
#include <initializer_list>

class foo {
public:
        foo(int d) : data(d) {}
        bool equals_one_of(std::initializer_list<int> options) {
                for (auto o: options) {
                        if (o == data) return true;
                }
                return false;
        }
private:
        int data;
};

int main() {
        foo f(10);
        assert(f.equals_one_of({1,3,5,7,8,10,14}));
        assert(!f.equals_one_of({3,6,14}));
        return 0;
}

Ответ 7

У кого-нибудь есть идея? спасибо за обмен!

Для этого существует стандартный альгитрит:

using std::vector; // & std::begin && std::end

// if(data is equal to one of these(1,2,3,4,5,6))
/* maybe static const */vector<int> criteria{ 1, 2, 3, 4, 5, 6 };
return end(criteria) != std::find(begin(criteria), end(criteria), data);

Изменить: (все в одном месте):

bool is_equal_to_one_of_these(int data, const std::vector<int>& criteria)
{
    using std::end; using std::begin; using std::find;
    return end(criteria) != find(begin(criteria), end(criteria), data);
}

auto data_matches = is_equal_to_one_of_these(data, {1, 2, 3, 4, 5, 6});

Edit:

Я предпочитаю интерфейс в терминах вектора вместо списка инициализаторов, потому что он более мощный:

std:vector<int> v = make_candidate_values_elsewhere();
auto data_matches = is_equal_to_one_of_these(data, v);

Интерфейс (с помощью вектора) не ограничивает вас для определения значений, где вы вызываете is_equal_to_one_of_these.

Ответ 8

set - хороший вариант, но если вы действительно хотите сворачивать свой собственный, initializer_list является убедительным:

bool is_in( int val, initializer_list<int> lst )
{
    for( auto i : lst )
        if( i == val ) return true;
    return false;
}

использование тривиально:

is_in( x, { 3, 5, 7 } ) ;

это O (n) ты, установить/неупорядочен быстрее

Ответ 9

Я бы рекомендовал использовать стандартный контейнер, например std::vector, но это все равно подразумевает линейную сложность с наихудшим временем выполнения O(N).

class Foo{
public:
    int data;
    bool is_equal_to_one_of_these(const std::vector<int>& arguments){
        bool matched = false;
        for(int arg : arguments){ //if you are not using C++11: for(int i = 0; i < arguments.size(); i++){
            if( arg == data ){ //if you are not using C++11: if(arguments[i] == data){
                matched = true;
            }
        }
        return matched;
    }
};

std::vector<int> exampleRange{ {1,2,3,4,5} };
Foo f;
f.data = 3;
std::cout << f.is_equal_to_one_of_these(exampleRange); // prints "true"

Ответ 10

Если данные, num1,.. num6 находятся между 0 и 31, вы можете использовать

int match = ((1<<num1) | (1<<num2) | ... | (1 << num6));
if( ( (1 << data) & match ) != 0 ) ...

Если num1 to num6 являются константами, компилятор будет вычислять совпадение во время компиляции.