Что такое С++-метод проверки того, содержится ли элемент в массиве/списке, аналогично тому, что делает оператор in в Python?
if x in arr:
print "found"
else
print "not found"
Как временная сложность эквивалента С++ сравнивается с оператором Python in?
Временная сложность Python in операторе варьируется в зависимости от структуры данных, с которой он фактически вызывается. Когда вы используете его со списком, сложность линейна (как и следовало ожидать от несортированного массива без индекса). Когда вы используете его для поиска заданного членства или наличия словарного ключа, сложность в среднем постоянна (как и следовало ожидать от реализации на основе хеш-таблицы):
В C++ вы можете использовать std::find чтобы определить, содержится ли элемент в std::vector. Сложность называется линейной (как и следовало ожидать от несортированного массива без индекса). Если вы убедитесь, что вектор отсортирован, вы также можете использовать std::binary_search для достижения того же самого в логарифмическом времени.
Ассоциативные контейнеры, предоставляемые стандартной библиотекой (std::set, std::unordered_set, std::map ,...), предоставляют для этого функцию-член find(), которая будет работать лучше, чем линейный поиск, т.е. Логарифмический или постоянное время в зависимости от того, выбрали ли вы заказанную или неупорядоченную альтернативу.
Если вы хотите, вы можете использовать некоторую магию шаблона, чтобы написать функцию-обертку, которая выбирает правильный метод для имеющегося контейнера, например, как представлено в этом ответе.
Вы можете подойти к этому двумя способами:
Вы можете использовать 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;
}
Python делает разные вещи для in в зависимости от того, какой контейнер он есть. В С++ вам нужен тот же механизм. Правило большого пальца стандартных контейнеров заключается в том, что если они обеспечивают find(), он будет лучшим алгоритмом, чем std::find() (например, find() для std::unordered_map есть O (1), но std::find() всегда O (N)).
Итак, мы можем написать что-то, чтобы это проверить. Наиболее кратким было бы использовать С++ 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);
}
}
В С++ 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; двухступенчатый, чтобы обрабатывать все стандартные контейнеры, необработанные массивы и любые контейнеры, предназначенные для использования/адаптированные.
Я предполагаю, что можно использовать этот поток и создать пользовательскую версию функции 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.
Это дает вам инфикс *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";
С++ 14, но главным образом для enable_if_t.
Итак, что здесь происходит?
Ну, can_apply - это немного кода, который позволяет мне писать can_dot_find, который обнаруживает (во время компиляции), если container.find(x) является допустимым выражением.
Это позволяет мне отправлять код поиска, чтобы использовать элемент-find, если он существует. Если этого не существует, вместо этого используется линейный поиск с использованием std::find.
Это немного ложь. Если вы определяете свободную функцию find(c, t) в пространстве имен вашего контейнера, она будет использовать это, а не любое из указанных выше. Но это мне очень нравится (и это позволяет вам расширять сторонние контейнеры с поддержкой *in*).
То, что ADL (зависящий от аргументов поиск) extensibity (способность стороннего расширения) заключается в том, что у нас есть три разные функции с именем find, два в пространстве имен помощников и один в notstd. Вы должны называть notstd::find.
Далее, нам нужен python-подобный in, и что больше похоже на python, чем на инфиксный оператор? Чтобы сделать это на С++, вам нужно обернуть свое имя оператора в других операторах. Я выбрал *, поэтому мы получаем оператор infix *in* named.
Вы выполняете 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))
для работы.
Вы можете использовать std:: find from < алгоритм > . Но это работает только для типов данных типа: std:: map, std::vector и т.д. Также обратите внимание, что это вернет итератор к первому элементу, который окажется равным значению, которое вы передаете, в отличие от оператора IN в python, который возвращает true/false.