pointer - string array c++

¿Cuál es el equivalente en C++ del operador "en" de Python?

Question

¿Cuál es la forma C ++ de verificar si un elemento está contenido en una matriz / lista, similar a lo que hace el operador in en Python?

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

¿Cómo se compara la complejidad de tiempo del equivalente de C ++ con el operador de Python?

Answer 1

Creo que uno podría hacer uso de this hilo y crear una versión personalizada de in función.

La idea principal es usar SFINAE (la falla de sustitución no es un error) para diferenciar los contenedores asociativos (que tienen miembro key_type ) de los contenedores de secuencia (que no tienen ningún miembro key_type ).

Aquí hay una posible implementación:

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

Pequeño ejemplo de uso en WANDBOX .

Answer 2

Esto le da un operador infix *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;
}

En un contenedor plano, como una matriz de vectores o cadena, es O (n).

En un contenedor ordenado asociativo, como un std::map , std::set , es O (lg (n)).

En un contenedor asociado no ordenado, como std::unordered_set , es O (1).

Código de prueba:

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

Ejemplo en vivo

C ++ 14, pero principalmente para enable_if_t .

Entonces, ¿qué está pasando aquí?

Bueno, can_apply es un código que me permite escribir can_dot_find , que detecta (en tiempo de compilación) si container.find(x) es una expresión válida.

Esto me permite enviar el código de búsqueda para usar member-find, si existe. Si no existe, se utiliza una búsqueda lineal usando std::find su lugar.

Lo cual es un poco mentira. Si define una función gratuita find(c, t) en el espacio de nombres de su contenedor, usará eso en lugar de cualquiera de los anteriores. Pero ese soy yo el que está de moda (y te permite extender contenedores de terceros con soporte *in* ).

Esa extensibilidad de ADL (búsqueda dependiente de argumentos) (la capacidad de extensión de terceros) es la razón por la cual tenemos tres funciones diferentes llamadas find , dos en un espacio de nombres de ayuda y uno en notstd . Tiene la intención de llamar a notstd::find .

A continuación, queremos un estilo python, y ¿qué es más python que un operador infijo? Para hacer esto en C ++, debe ajustar el nombre de su operador en otros operadores. Elegí * , por lo que obtenemos un infijo *in* operador nombrado.

TL; DR

Lo haces using notstd::in; para importar el operador nombrado in .

Después de eso, t *in* c primero verifica si find(t,c) es válido. Si no, verifica si c.find(t) es válido. Si eso falla, realiza una búsqueda lineal de c usando std::begin std::end y std::find .

Esto le da muy buen rendimiento en una amplia variedad de contenedores std .

Lo único que no admite es

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

ya que los operadores (que no sean = ) no pueden deducir listas de inicializadores, creo. Puedes obtener

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

trabajar.

Answer 3

La complejidad de tiempo del operador de Python varía en función de la estructura de datos con la que realmente se llama. Cuando lo utiliza con una lista, la complejidad es lineal (como cabría esperar de una matriz sin clasificar sin índice). Cuando lo usa para buscar la membresía establecida o la presencia de una complejidad de clave de diccionario, es constante en promedio (como se esperaría de una implementación basada en una tabla hash):

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

En C ++ puede usar std::find para determinar si un artículo está o no en un std::vector . Se dice que la complejidad es lineal (como cabría esperar de una matriz sin clasificar sin índice). Si se asegura de que el vector esté ordenado, también puede usar std::binary_search .

• en.cppreference.com/w/cpp/algorithm/find
• Verificar si el elemento está en la lista (contiene)
• Compruebe si el elemento encontrado en la matriz c + +
• http://en.cppreference.com/w/cpp/algorithm/binary_search

Los contenedores asociativos proporcionados por la biblioteca estándar ( std::set , std::unordered_set , std::map , ...) proporcionan la función miembro find() para esto, que funcionará mejor que la búsqueda lineal, es decir, logarítmica o tiempo constante dependiendo de si ha elegido la alternativa ordenada o desordenada.

• ¿Cómo verificar que un elemento está en un std :: set?
• ¿Cómo comprobar si std :: map contiene una clave sin insertar?
• https://en.wikipedia.org/wiki/Associative_containers
• http://en.cppreference.com/w/cpp/container

Si lo desea, puede usar magia de plantilla para escribir una función de envoltura que elija el método correcto para el contenedor en cuestión, por ejemplo, tal como se presenta en esta respuesta .

Answer 4

Puede usar std :: find de <algorithm>. Pero esto solo funciona para tipos de datos como, std :: map, std :: vector, etc. También tenga en cuenta que esto devolverá iterador al primer elemento que se encuentre igual al valor que pase, a diferencia del operador IN en python que devuelve true / falso.

Answer 5

Puedes acercarte a esto de dos maneras:

Puede usar en.cppreference.com/w/cpp/algorithm/find de <algorithm> :

auto it = std::find(container.begin(), container.end(), value);
if (it != container.end())
    return it;  

o puede iterar a través de cada elemento en sus contenedores con bucles a distancia:

for(const auto& it : container)
{
    if(it == value)
        return it;
} 

Answer 6

Python hace diferentes cosas dependiendo del tipo de contenedor que sea. En C ++, querrías el mismo mecanismo. La regla general para los contenedores estándar es que si proporcionan un find() , será un mejor algoritmo que std::find() (por ejemplo, find() para std::unordered_map es O (1), pero std::find() siempre es O (N)).

Entonces, podemos escribir algo para que lo hagamos nosotros mismos. El más conciso sería tomar ventaja de C ++ 17 if constexpr y usar algo como Yakk''s 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);
    }
}

En C ++ 11, podemos aprovechar la expresión 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);
}

Tenga en cuenta que en ambos casos tenemos el using std::begin; using std::end; using std::begin; using std::end; de dos pasos para manejar todos los contenedores estándar, matrices en bruto y cualquier contenedor provisto / provisto por el usuario.