Comparison tricks in C++

Question

A class:

class foo{
public:
    int data;
};

Now I want to add a method to this class, to do some comparison, to see if its data is equal to one of given numbers.

Of course, I can write if(data==num1|| data == num2|| data ==num3.....), but honestly speaking, I feel sick when I write data == every time I compare it to a number.

So, I hope I would be able to write something like this:

if(data is equal to one of these(num1,num2,num3,num4,num5...))
    return true;
else
    return false;

I want to implement this statement, data is equal to one of these(num1, num2, num3, num4, num5...)

Here is my approach:

#include <stdarg.h>
bool is_equal_to_one_of_these(int count,...){
    int i;
    bool equal = false;
    va_list arg_ptr;
    va_start(arg_prt,count);
    for(int x=0;x<count;x++){
        i = va_arg(arg_ptr,int);
        if( i == data ){
            equal = true;
            break;
        }
    }
    va_end(arg_ptr);
    return equal;
}

This piece of code will do the job for me. But every time I use this method, I'll have to count the parameters and pass it in.

Does anyone have a better idea?

Answer 1

There are many ways of doing this with the STL.

If you have an incredibly large number of items and you want to test if your given item is a member of this set, use set or unordered_set. They allow you to check membership in log n and constant time respectively.

If you keep the elements in a sorted array, then binary_search will also test membership in log n time.

For small arrays, a linear search with find might however preform significantly faster (as there is no branching). A linear search might even do 3-8 comparisons in the time it takes the binary search to 'jump around'. This blog post suggests there to be a break-even point at proximately 64 items, below which a linear search might be faster, though this obviously depends on the STL implementation, compiler optimizations and your architecture's branch prediction.

Answer 2

The easy way

The simplest approach is to write a member function wrapper called in() around std::find with a pair of iterators to look for the data in question. I wrote a simple template<class It> in(It first, It last) member function for that

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

If you have no access to the source of foo, you can write a non-member functions of signature template<class T> bool in(foo const&, std::initializer_list<T>) etc., and call it like

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

The hard way

But let's go completely overboard with that: just add two more public overloads:

• one taking a std::initializer_list parameter that calls the previous one with the begin() and end() iterators of the corresponding initializer list argument.
• one for an arbitrary container as input that will do a little tag dispatching to two more private overloads of a detail_in() helper:
  • one overload doing a SFINAE trick with trailing return type decltype(c.find(data), bool()) that will be removed from the overload set if the container c in question does not have a member function find(), and that returns bool otherwise (this is achieved by abusing the comma operator inside decltype)
  • one fallback overload that simply takes the begin() and end() iterators and delegates to the original in() taking two iterators

Because the tags for the detail_in() helper form an inheritance hierarchy (much like the standard iterator tags), the first overload will match for the associative containers std::set and std::unordered_set and their multi-cousins. All other containers, including C-arrays, std::array, std::vector and std::list, will match the second overload.

#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";    
}

Live Example that -for all possible containers- prints 1 and 0 for both number sets.

The use cases for the std::initializer_list overload are for member-ship testing for small sets of numbers that you write out explicitly in calling code. It has O(N) complexity but avoids any heap allocations.

For anything heavy-duty like membership testing of large sets, you could store the numbers in an associative container like std::set, or its multi_set or unordered_set cousins. This will go to the heap when storing these numbers, but has O(log N) or even O(1) lookup complexity.

But if you happen to have just a sequence container full of numbers around, you can also throw that to the class and it will happily compute membership for you in O(N) time.

Answer 3

If data, num1, .. num6 are between 0 and 31, then you can use

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

If num1 to num6 are constants, the compiler will compute match at compile time.

Answer 4

Does anyone have better idea ? thanks for sharing !

There's a standard algitrithm for that:

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);

Edit: (all in one place):

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:

I prefer the interface in terms of a vector, instead of an initializer list, because it is more powerful:

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

The interface (by using a vector), doesn't restrict you to define the values, where you call is_equal_to_one_of_these.

Answer 5

The answers using std::initializer_list are fine, but I want to add one more possible solution which is exactly what you where trying with that C variadic in a type-safe and modern way: Using C++11 variadic templates:

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 );
};

Of course this only works if all values passed are of the same type. If not the initializer list unpacked cannot be deduced nor initialized.

Then:

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

EDIT: Here is a are_same metafunction to ensure that all the numbers passed are of the same type:

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

Where and_op performs n-ary logical and:

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
{};

This makes possible to force the usage of numbers of the same type in a simple way:

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 );
};

Answer 6

I would recommend to use standard container like std::vector, but that would still imply a linear complexity with worst-case runtime of 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"

Answer 7

It isn't pretty, but this should work:

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; 
}

And so on. That'll give you the exact syntax you were after. But if you are after the completely variable number of arguments then either the vector, or std::initalizer list might be the way to go:

See: http://en.cppreference.com/w/cpp/utility/initializer_list

This example shows it in action:

#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;
}

Answer 8

set is a good option, but if you really want to roll your own, initializer_list is convienient:

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

use is trivial:

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

it's O(n) thou, set / unordered is faster

Answer 9

Any optimization is going to depend on properties of the set of numbers being compared to.

If there's a definite upper bound, you can use a std::bitset. Testing membership (that is, indexing into the bitset, which behaves like an array), is O(1), effectively a few fast instructions. This is often the best solution up to limits in the hundreds, although depending on the application millions could be practical.

Answer 10

If data is really an integral or enumerated type, you can use a 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;
}