What is the C++ equivalent of Python's "in" operator?

The time complexity of Python's in operator varies depending on the data structure it is actually called with. When you use it with a list, complexity is linear (as one would expect from an unsorted array without an index). When you use it to look up set membership or presence of a dictionary key complexity is constant on average (as one would expect from a hash table based implementation):

  • https://wiki.python.org/moin/TimeComplexity

In C++ you can use std::find to determine whether or not an item is contained in a std::vector. Complexity is said to be linear (as one would expect from an unsorted array without an index). If you make sure the vector is sorted, you can also use std::binary_search to achieve the same in logarithmic time.

  • http://en.cppreference.com/w/cpp/algorithm/find
  • Check if element is in the list (contains)
  • Check if element found in array c++
  • http://en.cppreference.com/w/cpp/algorithm/binary_search

The associative containers provided by the standard library (std::set, std::unordered_set, std::map, ...) provide the member functions find() and count() and contains() (C++20) for this. These will perform better than linear search, i.e., logarithmic or constant time depending on whether you have picked the ordered or the unordered alternative. Which one of these functions to prefer largely depends on what you want to achieve with that info afterwards, but also a bit on personal preference. (Lookup the documentation for details and examples.)

  • How to check that an element is in a std::set?
  • How to check if std::map contains a key without doing insert?
  • https://en.wikipedia.org/wiki/Associative_containers
  • http://en.cppreference.com/w/cpp/container

If you want to, you can use some template magic to write a wrapper function that picks the correct method for the container at hand, e.g., as presented in this answer.


You can approach this in two ways:

You can use std::find from <algorithm>:

auto it = std::find(container.begin(), container.end(), value);
if (it != container.end())
    return it;

or you can iterate through every element in your containers with for ranged loops:

for(const auto& it : container)
{
    if(it == value)
        return it;
}

Python does different things for in depending on what kind of container it is. In C++, you'd want the same mechanism. Rule of thumb for the standard containers is that if they provide a find(), it's going to be a better algorithm than std::find() (e.g. find() for std::unordered_map is O(1), but std::find() is always O(N)).

So we can write something to do that check ourselves. The most concise would be to take advantage of C++17's if constexpr and use something like Yakk's can_apply:

template <class C, class K>
using find_t = decltype(std::declval<C const&>().find(std::declval<K const&>()));

template <class Container, class Key>
bool in(Container const& c, Key const& key) {
    if constexpr (can_apply<find_t, Container, Key>{}) {
        // the specialized case
        return c.find(key) != c.end();
    } else {
        // the general case 
        using std::begin; using std::end;
        return std::find(begin(c), end(c), key) != end(c);
    }
}

In C++11, we can take advantage of expression SFINAE:

namespace details {
    // the specialized case
    template <class C, class K>
    auto in_impl(C const& c, K const& key, int )
            -> decltype(c.find(key), true) {
        return c.find(key) != c.end();
    }

    // the general case
    template <class C, class K>
    bool in_impl(C const& c, K const& key, ...) {
        using std::begin; using std::end;
        return std::find(begin(c), end(c), key) != end(c);
    }
}

template <class Container, class Key>
bool in(Container const& c, Key const& key) {
    return details::in_impl(c, key, 0);
}

Note that in both cases we have the using std::begin; using std::end; two-step in order to handle all the standard containers, raw arrays, and any use-provided/adapted containers.

Tags:

C++

Arrays

Recent Posts