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

Question

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

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

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

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()这一点,这将不是线性搜索,即,取决于你是否已经选择有序或无序的替代或对数恒定的时间表现得更好.

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

如果你愿意,你可以使用一些模板魔术来编写一个包装器函数,为当前容器选择正确的方法,例如,如本答案中所示.

Answer 2

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

您可以使用std::find从<algorithm>:

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 in根据它的容器类型做了不同的事情.在C++中,您需要相同的机制.标准容器的经验法则是,如果它们提供a find(),它将是比std::find()(例如,find()对于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中,我们可以利用表达式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;两步,以便处理所有标准容器,原始数组和任何使用提供/适应的容器.

Answer 4

我想有人可能会使用这个线程并创建一个自定义版本的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上的小用法示例.

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;
}

在扁平容器上,如矢量数组或字符串,它是O(n).

在关联排序容器(如a 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)是一个有效的表达式.

这允许我发送搜索代码以使用member-find(如果存在).如果它不存在,std::find则使用线性搜索.

这有点谎言.如果find(c, t)在容器的命名空间中定义一个自由函数,它将使用它而不是上述任何一个.但这就是我的想象力(它可以让你通过*in*支持扩展第三方容器).

ADL(参数依赖查找)extensibity(第三方扩展能力)是为什么我们有三个不同的函数命名find,两个在helper命名空间,一个在notstd.你打算打个电话notstd::find.

接下来,我们想要一个像python一样的python in,什么比一个中缀运算符更像python？要在C++中执行此操作,您需要将运算符名称包装在其他运算符中.我选择了*,所以我们得到一个*in*名为operator 的中缀.

TL; DR

您using notstd::in;可以导入命名运算符in.

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

这使您在各种std容器上都能获得非常好的性能.

它唯一不支持的是

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

因为运营商(除了=)不能推断出我相信的初始化列表.你可以得到

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

上班.