Что такое эквивалент С++ для оператора Python?

Что такое С++-метод проверки того, содержится ли элемент в массиве/списке, аналогично тому, что делает оператор in в Python?

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

Как временная сложность эквивалента С++ сравнивается с оператором Python in?

Ответы

Ответ 1

Временная сложность Python in операторе варьируется в зависимости от структуры данных, с которой он фактически вызывается. Когда вы используете его со списком, сложность линейна (как и следовало ожидать от несортированного массива без индекса). Когда вы используете его для поиска заданного членства или наличия словарного ключа, сложность в среднем постоянна (как и следовало ожидать от реализации на основе хеш-таблицы):

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

В C++ вы можете использовать std::find чтобы определить, содержится ли элемент в std::vector. Сложность называется линейной (как и следовало ожидать от несортированного массива без индекса). Если вы убедитесь, что вектор отсортирован, вы также можете использовать std::binary_search для достижения того же самого в логарифмическом времени.

Ассоциативные контейнеры, предоставляемые стандартной библиотекой (std::set, std::unordered_set, std::map ,...), предоставляют для этого функцию-член find(), которая будет работать лучше, чем линейный поиск, т.е. Логарифмический или постоянное время в зависимости от того, выбрали ли вы заказанную или неупорядоченную альтернативу.

Если вы хотите, вы можете использовать некоторую магию шаблона, чтобы написать функцию-обертку, которая выбирает правильный метод для имеющегося контейнера, например, как представлено в этом ответе.

Ответ 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;
}

Ответ 3

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; двухступенчатый, чтобы обрабатывать все стандартные контейнеры, необработанные массивы и любые контейнеры, предназначенные для использования/адаптированные.

Ответ 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.

Ответ 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";

Живой пример.

С++ 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.

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))

для работы.

Ответ 6

Вы можете использовать std:: find from < алгоритм > . Но это работает только для типов данных типа: std:: map, std::vector и т.д. Также обратите внимание, что это вернет итератор к первому элементу, который окажется равным значению, которое вы передаете, в отличие от оператора IN в python, который возвращает true/false.