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

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

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

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

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

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

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

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

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

你可以使用<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; } 

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; 为了处理所有的标准容器,原始数组和任何使用提供的/适应的容器,需要两步操作。

我想有人可能会利用这个线程,并创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上的小例子。

这给你一个中缀*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::mapstd::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::endstd::find进行c的线性search。

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

唯一不支持的是

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

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

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

上class。

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