什么是Python中"in"的C ++等效项?操作员? [英] What is the C++ equivalent of Python's "in" operator?

问题描述

检查元素是否包含在数组/列表中的C ++方法是什么，类似于in运算符在Python中所做的工作?

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"

与Python的in运算符相比，C ++等效项的时间复杂度如何?

How does the time complexity of the C++ equivalent compare to Python's in operator?

推荐答案

Python的in运算符的时间复杂度取决于实际使用的数据结构.当将它与列表一起使用时，复杂度是线性的(正如人们希望从没有索引的未排序数组中得出的那样).当您使用它来查找集合成员身份或字典的存在时，键的复杂度平均是恒定的(就像从基于哈希表的实现中所期望的那样):

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

在C ++中，您可以使用std::find来确定std::vector中是否包含项目.复杂度据说是线性的(就像人们对没有索引的未排序数组所期望的那样).如果确定向量已排序，还可以使用std::binary_search来实现对数时间.

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
• 检查元素是否在列表中(包含)
• 检查元素是否在数组c ++中找到
• http://en.cppreference.com/w/cpp/algorithm/binary_search

• 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

标准库(std::set，std::unordered_set，std::map，...)提供的关联容器为此提供了成员函数find()，其性能要优于线性搜索，即对数或恒定时间，具体取决于您选择的是有序还是无序.

The associative containers provided by the standard library (std::set, std::unordered_set, std::map, ...) provide the member function find() for this, that will perform better than linear search, i.e., logarithmic or constant time depending on whether you have picked the ordered or the unordered alternative.

• 如何检查std :: set中的元素?
• 如何在不执行插入操作的情况下检查std :: map是否包含密钥?
• https://en.wikipedia.org/wiki/Associative_containers
• http://en.cppreference.com/w/cpp/container

• 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.

这篇关于什么是Python中"in"的C ++等效项?操作员?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！