What is the C++ way of checking if an element is contained in an array/list, similar to what the
in operator does in Python?
if x in arr: print "found" else print "not found"
How does the time complexity of the C++ equivalent compare to Python’s
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):
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.
- Check if element is in the list (contains)
- Check if element found in array c++
The associative containers provided by the standard library (
std::map, …) provide the member functions
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?
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.