Python 的“in”运算符的 C 等价物是什么？

Question

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

 if x in arr:
    print "found"
else
    print "not found"

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

原文由 SanDash 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

Python 的 in 运算符的时间复杂度取决于实际调用它的数据结构。当您将它与列表一起使用时，复杂性是线性的（正如人们对没有索引的未排序数组所期望的那样）。当您使用它来查找集合成员资格或字典键的存在时，复杂度平均是恒定的（正如人们对基于哈希表的实现所期望的那样）：

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

在 C++ 中，您可以使用 std::find 来确定项目是否包含在 std::vector 中。复杂性被认为是线性的（正如人们对没有索引的未排序数组所期望的那样）。如果您确保向量已排序，您还可以使用 std::binary_search 在对数时间内实现相同的效果。

• http://en.cppreference.com/w/cpp/algorithm/find
• 检查元素是否在列表中（包含）
• 检查是否在数组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() 和 contains() (C++20) 为此。这些将比线性搜索执行得更好，即对数或恒定时间取决于您是否选择了有序或无序的替代方案。更喜欢这些功能中的哪一个在很大程度上取决于你想用这些信息实现什么，但也有点取决于个人喜好。 （查找文档以获取详细信息和示例。）

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

如果你愿意，你可以使用一些模板魔法来编写一个包装函数，为手头的容器选择正确的方法，例如，如 本答案所示。

原文由 moooeeeep 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

您可以通过两种方式解决此问题：

您可以使用 std::find 来自 <algorithm> ：

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

或者您可以使用 for ranged 循环遍历容器中的每个元素：

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

原文由 Omar Martinez 发布，翻译遵循 CC BY-SA 3.0 许可协议