如何使用 C++ 检查一个元素是否存在于数组/列表中,类似于 Python 中的 in
运算符?
if x in arr:
print "found"
else
print "not found"
C++相应代码的时间复杂度与Python的in
运算符相比如何?
in
运算符的时间复杂度取决于它实际调用的数据结构。当您将其用于列表时,复杂度是线性的(就像从未排序的数组没有索引一样)。当您使用它查找集合成员或字典键的存在性时,平均复杂度为常数(正如基于哈希表的实现所期望的那样):
在C++中,您可以使用std::find
来确定一个项是否包含在std::vector
中。复杂度被认为是线性的(正如我们从没有索引的未排序数组所期望的那样)。如果您确保向量已排序,则还可以使用std::binary_search
以对数时间实现相同的功能。
std::set
,std::unordered_set
,std::map
等)提供成员函数find()
和count()
以及contains()
(C++20)。这些函数比线性搜索更快,即根据您选择的有序或无序替代品而定的对数时间或常数时间。使用哪个函数在很大程度上取决于您之后想要实现的目标,但也有一点取决于个人喜好。(详细信息和示例请查阅文档。)
find()
方法来实现这个功能。std::find
函数是否有重载函数可以调用这些方法呢? - Ericstd::find
没有这样的重载。 - moooeeeep<algorithm>
迭代器接口在回顾中不是一个好主意的原因之一,为什么范围会更好:使用范围,您可以专门针对传入类型具有某些属性/方法的算法进行延迟。 - Matthieu M.find
委托给正在迭代的容器/视图,这个要求会发生变化。 - Matthieu M.您可以采用两种方法:
您可以使用来自<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;
}
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;
这个两步操作,以处理所有标准容器、原始数组和任何用户提供/适配的容器。
decltype(c.find(key) != c.end())
的翻译内容是: - T.C.*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*
的中缀运算符。
您可以使用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))
工作。
in
函数。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);
}
<algorithm>
的std::find
,但这仅适用于像std::map
和std::vector
等数据类型。
另外请注意,与Python中返回布尔值的in
运算符不同,这将返回到找到的第一个等于您传递的值的迭代器。
我认为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”运算符调用这些函数进行操作。
该实现在此存储库中:
find
能够满足你的需求 - 可以参考 http://en.cppreference.com/w/cpp/algorithm/find - Support Ukrainestd::find
。 - juanchopanzacontains(container)
并不难写:https://codereview.stackexchange.com/questions/59997/contains-algorithm-for-stdvector - Deduplicator