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

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

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

C ++等价物的时间复杂度与Python中的运算符相比如何？

Answer 1

Python in运算符中的时间复杂度取决于实际调用的数据结构。 在列表中使用它时，复杂性是线性的（正如从没有索引的未sorting数组中预期的那样）。 当你使用它来查找设置的成员资格或字典密钥的存在时，复杂度平均是不变的（正如人们所期望的，基于哈希表的实现）：

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

在C ++中，您可以使用std::find来确定一个项目是否包含在std::vector 。 据说复杂性是线性的（正如人们所期望的那样，没有索引的未sorting数组）。 如果你确定向量是sorting的，你也可以使用std::binary_search 。

• http://en.cppreference.com/w/cpp/algorithm/find
• 检查元素是否在列表中（包含）
• 检查在数组c ++中find的元素
• http://en.cppreference.com/w/cpp/algorithm/binary_search

由标准库（ std::set ， std::unordered_set ， std::map ，…）提供的关联容器为此提供了成员函数find() ，它将比线性search（即对数或时间长短取决于你是否select了有序的或无序的select。

• 如何检查一个元素是在一个std :: set？
• 如何检查如果std :: map包含一个没有插入的键？
• https://en.wikipedia.org/wiki/Associative_containers
• http://en.cppreference.com/w/cpp/container

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

Answer 2

你可以用两种方法来解决这个问题：

你可以使用<algorithm> std::find ：

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

或者你可以迭代你的容器中的每个元素与范围循环：

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

Answer 3

Python根据它是什么types的容器来做不同的事情。 在C ++中，你需要相同的机制。 对于标准容器来说，经验法则是如果他们提供了find() ，它将比std::find()更好一些（例如find() for std::unordered_map是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中，我们可以利用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); } 

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

Answer 4

我想有人可能会利用这个线程，并创build一个函数的自定义版本。

主要思想是使用SFINAE （replace失败不是错误）来区分关联容器（有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上的小例子。

Answer 5

这给你一个中缀*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; } 

在一个平坦的容器上，像一个向量数组或string，它是O（n）。

在一个关联的sorting容器上，像std::map ， std::set ，它是O（lg（n））。

在一个无序的关联容器上，像std::unordered_set ，它是O（1）。

testing代码：

 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)是否是一个有效的expression式。

这让我派遣search代码来使用成员查找，如果它存在。 如果不存在，则使用std::find进行线性search。

这是一个谎言。 如果你在容器的命名空间中定义一个自由函数find(c, t) ，它将使用它而不是上面的任何一个。 但是，这是我的幻想（它可以让你扩展第三方容器*in*支持*in* ）。

ADL（依赖于参数的查找）可扩展性（第三方扩展能力）就是为什么我们有三个不同的函数叫做find ，两个在助手命名空间中，另一个在notstd 。 您打算调用notstd::find 。

接下来，我们需要一个像Python一样的Python，比一个中缀运算符更像Python吗？ 要在C ++中执行此操作，您需要将您的操作员名称包装在其他操作员中。 我select了* ，所以我们*in* named操作符中得到一个中缀。

---

TL; DR

你using notstd::in; 在中导入指定的操作符。

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

这在各种各样的std容器上给你非常好的performance。

唯一不支持的是

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

因为运算符（除了= ）不能推导出我认为的初始化列表。 你可以得到

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

上class。

Answer 6

你可以使用<algorithm>的std :: find。 但是，这只适用于像std :: map，std :: vector等数据types。另外请注意，这将返回，迭代器发现等于您传递的值的第一个元素，不像IN运算符在Python中返回true /假。