C++ 中与 Python 的 "in" 运算符相当的是什么？

Question

如何使用 C++ 检查一个元素是否存在于数组/列表中，类似于 Python 中的 in 运算符？

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

C++相应代码的时间复杂度与Python的in运算符相比如何？

- SanDash

---

也许 find 能够满足你的需求 - 可以参考 http://en.cppreference.com/w/cpp/algorithm/find - Support Ukraine

@4386427 但是你不会想在 map 或 set 上使用 std::find。 - juanchopanza

或者，如果容器已排序，则可以使用 std::lower_bound（如果可用，则使用成员函数，例如 std::map::lower_bound）。 - Galik

如果你关心时间复杂度，很遗憾，并没有语法等价物适用于所有容器类型。 - juanchopanza

contains(container)并不难写：https://codereview.stackexchange.com/questions/59997/contains-algorithm-for-stdvector - Deduplicator

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

标准库提供的关联容器（std::set，std::unordered_set，std::map等）提供成员函数find()和count()以及contains()（C++20）。这些函数比线性搜索更快，即根据您选择的有序或无序替代品而定的对数时间或常数时间。使用哪个函数在很大程度上取决于您之后想要实现的目标，但也有一点取决于个人喜好。（详细信息和示例请查阅文档。）

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

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

- moooeeeep

---

关联容器提供了 find() 方法来实现这个功能。std::find 函数是否有重载函数可以调用这些方法呢？ - Eric

由于该函数接受输入/前向迭代器，因此它似乎只是对容器进行正向迭代。 - moooeeeep

（实际回答问题：）std::find 没有这样的重载。 - moooeeeep

@Eric：很遗憾，不行。这也是为什么整个<algorithm>迭代器接口在回顾中不是一个好主意的原因之一，为什么范围会更好：使用范围，您可以专门针对传入类型具有某些属性/方法的算法进行延迟。 - Matthieu M.

@MatthieuM。问题不在于基于迭代器的接口；可以很容易地想象一种设置，即“find”识别来自关联容器的迭代器，并且迭代器包含足够的信息（指针）以执行二分搜索。问题在于“find”需要使用“==”，而这不需要与关联容器可能具有的任何排序一致（甚至不是默认的“<”）。 - T.C.

@T.C.：我想象一下，如果find委托给正在迭代的容器/视图，这个要求会发生变化。 - Matthieu M.

Answer 2

您可以采用两种方法：

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

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

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

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

- Omar Martinez

---

对于已排序或未排序的集合或映射，这种方法不会很好地扩展（O(N)与摊销后的O(log N)或O(1)相比）。 - juanchopanza

由于我在第一条评论中指出的原因，这是一个不好的想法。 - juanchopanza

@juanchopanza 在Python中也不是特别高效。（我相信在列表上它的时间复杂度为O（n））。在C++中，map::find是对数复杂度（除非http://www.cplusplus.com/reference/map/map/find/有误）。 - Baldrickk

@Baldrickk 显然在列表中是O(N)。但在集合或字典中不是。这就是整个重点。 - juanchopanza

这不是一个很好的答案。在这两个片段中，我们正在返回什么功能？"else"情况是什么？这甚至在你考虑对于那些具有O(lg N)或O(1)搜索的容器使用O(N)搜索的问题之前就存在了。-1。 - Barry

Answer 3

Python 根据容器类型对 in 运算符进行不同的操作。在 C++ 中，您也希望有相同的机制。标准容器的经验法则是，如果它们提供了 find() 方法，那么它的算法效率要优于 std::find()（例如，std::unordered_map 的 find() 的时间复杂度为 O(1)，而 std::find() 始终为 O(N)）。

因此，我们可以编写代码自行检查。最简洁的方法是利用 C++17 中的 if constexpr 并使用类似 Yakk 的 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);
    }
}

在 C++11 中，我们可以利用表达式 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);
}

请注意，在这两种情况下，我们都需要使用 using std :: begin; using std :: end; 这个两步操作，以处理所有标准容器、原始数组和任何用户提供/适配的容器。

- Barry

---

decltype(c.find(key) != c.end()) 的翻译内容是： - T.C.

@T.C. 这个更长一些 :-P - Barry

除非你处于全面偏执模式下，否则不需要这样做 ;) - T.C.

Answer 4

这将为您提供一个中缀 *in* 运算符：

namespace notstd {
  namespace ca_helper {
    template<template<class...>class, class, class...>
    struct can_apply:std::false_type{};
    template<class...>struct voider{using type=void;};
    template<class...Ts>using void_t=typename voider<Ts...>::type;

    template<template<class...>class Z, class...Ts>
    struct can_apply<Z,void_t<Z<Ts...>>, Ts...>:std::true_type{};
  }
  template<template<class...>class Z, class...Ts>
  using can_apply = ca_helper::can_apply<Z,void,Ts...>;

  namespace find_helper {
    template<class C, class T>
    using dot_find_r = decltype(std::declval<C>().find(std::declval<T>()));
    template<class C, class T>
    using can_dot_find = can_apply< dot_find_r, C, T >;
    template<class C, class T>
    constexpr std::enable_if_t<can_dot_find<C&, T>{},bool>
    find( C&& c, T&& t ) {
      using std::end;
      return c.find(std::forward<T>(t)) != end(c);
    }
    template<class C, class T>
    constexpr std::enable_if_t<!can_dot_find<C&, T>{},bool>
    find( C&& c, T&& t ) {
      using std::begin; using std::end;
      return std::find(begin(c), end(c), std::forward<T>(t)) != end(c);
    }
    template<class C, class T>
    constexpr bool finder( C&& c, T&& t ) {
      return find( std::forward<C>(c), std::forward<T>(t) );
    }
  }
  template<class C, class T>
  constexpr bool find( C&& c, T&& t ) {
    return find_helper::finder( std::forward<C>(c), std::forward<T>(t) );
  }
  struct finder_t {
    template<class C, class T>
    constexpr bool operator()(C&& c, T&& t)const {
      return find( std::forward<C>(c), std::forward<T>(t) );
    }
    constexpr finder_t() {}
  };
  constexpr finder_t finder{};
  namespace named_operator {
    template<class D>struct make_operator{make_operator(){}};

    template<class T, char, class O> struct half_apply { T&& lhs; };

    template<class Lhs, class Op>
    half_apply<Lhs, '*', Op> operator*( Lhs&& lhs, make_operator<Op> ) {
      return {std::forward<Lhs>(lhs)};
    }

    template<class Lhs, class Op, class Rhs>
    auto operator*( half_apply<Lhs, '*', Op>&& lhs, Rhs&& rhs )
    -> decltype( named_invoke( std::forward<Lhs>(lhs.lhs), Op{}, std::forward<Rhs>(rhs) ) )
    {
      return named_invoke( std::forward<Lhs>(lhs.lhs), Op{}, std::forward<Rhs>(rhs) );
    }
  }
  namespace in_helper {
    struct in_t:notstd::named_operator::make_operator<in_t> {};
    template<class T, class C>
    bool named_invoke( T&& t, in_t, C&& c ) {
      return ::notstd::find(std::forward<C>(c), std::forward<T>(t));
    }
  }
  in_helper::in_t in;
}

在一个平坦的容器上（例如向量数组或字符串），时间复杂度为O(n)。

在一个关联排序的容器中（例如std::map、std::set），时间复杂度为O(lg(n))。

在一个无序关联容器中（例如std::unordered_set），时间复杂度为O(1)。

测试代码：

std::vector<int> v{1,2,3};
if (1 *in* v)
    std::cout << "yes\n";
if (7 *in* v)
    std::cout << "no\n";
std::map<std::string, std::string, std::less<>> m{
    {"hello", "world"}
};
    
if ("hello" *in* m)
    std::cout << "hello world\n";

演示实例。

这是关于C++14和enable_if_t的内容。

那么这里发生了什么？

好吧，can_apply是一段代码，让我可以编写can_dot_find，它可以（在编译时）检测container.find(x)是否为有效表达式。

这使我可以将搜索代码分派到使用成员查找（如果存在）的代码。如果不存在，则使用线性搜索std::find。

这有点不真实。如果您在容器的命名空间中定义了自由函数find(c, t)，则会使用该函数而不是上述任何一个。但这只是我花哨的做法（它允许您扩展第三方容器以支持*in*）。

ADL（参数依赖查找）可扩展性（第三方扩展能力）正是我们拥有三个名为find的不同函数的原因，其中两个位于帮助程序命名空间中，一个位于notstd中。您应该调用notstd::find。

接下来，我们想要像Python一样的in，什么比中缀运算符更像Python呢？为了在C++中实现此操作，您需要在其他运算符中包装运算符名称。我选择了*，因此我们得到了一个名为*in*的中缀运算符。

---

TL;DR

您可以使用using notstd::in;导入命名运算符in。

之后，t *in* c首先检查find(t,c)是否有效。如果无效，则检查c.find(t)是否有效。如果失败，则使用std::begin、std::end和std::find对c进行线性搜索。

这可以在各种std容器上提供非常好的性能。

唯一不支持的是

if (7 *in* {1,2,3})

我认为，除了=运算符外，其他运算符无法推断初始化列表。你可以得到：

if (7 *in* il(1,2,3))

工作。

- Yakk - Adam Nevraumont

---

哇，这种巫术是让C++变得有趣的原因。 - kizzx2

Answer 5

我想你可以使用这个线程，并创建一个自定义版本的in函数。

主要思路是利用SFINAE（模板子类型可替换失败不是错误）来区分关联式容器（具有key_type成员）和序列式容器（没有key_type成员）。

以下是可能的实现：

namespace detail
{
    template<typename, typename = void>
    struct is_associative : std::false_type {};

    template<typename T>
    struct is_associative<T,
        std::enable_if_t<sizeof(typename T::key_type) != 0>> : std::true_type {};

    template<typename C, typename T>
    auto in(const C& container, const T& value) ->
        std::enable_if_t<is_associative<C>::value, bool>
    {
        using std::cend;

        return container.find(value) != cend(container);
    }

    template<typename C, typename T>
    auto in(const C& container, const T& value) ->
        std::enable_if_t<!is_associative<C>::value, bool>
    {
        using std::cbegin;
        using std::cend;

        return std::find(cbegin(container), cend(container), value) != cend(container);
    }

}

template<typename C, typename T>
auto in(const C& container, const T& value)
{
    return detail::in(container, value);
}

在 WANDBOX 上有一个关于如何使用的小例子。

- Edgar Rokjān

---

为了在这种情况下启用SFINAE，您必须在代码顶部添加“/* deliberately killing KISS */”。 - edmz

Answer 6

你可以使用来自<algorithm>的std::find，但这仅适用于像std::map和std::vector等数据类型。

另外请注意，与Python中返回布尔值的in运算符不同，这将返回到找到的第一个等于您传递的值的迭代器。

- pHM

Answer 7

我认为Python中“in”运算符的一个好处是它可以与不同的数据类型一起使用（字符串对比字符串，数字对比列表等）。

我正在开发一个库，用于在C++中使用Python结构。它包括“in”和“not_in”运算符。

它基于以前回答中发布的实现in运算符所使用的相同技术，其中实现了make_operator<in_t>。但是，它被扩展以处理更多情况：

• 在字符串中搜索字符串
• 在向量和映射中搜索元素

它通过为函数定义几个重载来工作：bool in__(T1 &v1, T2 &v2)，其中T1和T2考虑对象的不同可能类型。还定义了函数的重载：bool not_in__(T1 &v1, T2 &v2)。然后，“in”和“not_in”运算符调用这些函数进行操作。

该实现在此存储库中：

https://github.com/ploncomi/python_like_cpp

- Patricio Loncomilla

---

我们通常更喜欢在答案中提供答案，而不是提供到其他地方的链接。你能提供一下解释吗？ - Andy Newman

抱歉，但这不是答案的链接，而是一个实现所需功能的存储库链接（我正在处理中）。我会修改我的回答以更加详细地说明。 - Patricio Loncomilla