Comparison tricks in C++

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.