Comparison tricks in C++

c++, comparison

Solution

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.

Problem

Original source

Related problems

• binary search efficiency vs. linear search efficiency in fortran