Quel est l’équivalent C ++ de l’opérateur «in» de Python?

Quel est le moyen C ++ de vérifier si un élément est contenu dans un tableau / liste, de la même manière que l’opérateur in en Python?

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

Comment la complexité temporelle de l’équivalent C ++ se compare-t-elle à celle de l’opérateur in Python?

La complexité temporelle de l’opérateur in de Python varie en fonction de la structure de données avec laquelle il est appelé. Lorsque vous l’utilisez avec une liste, la complexité est linéaire (comme on peut s’y attendre d’un tableau non sortingé sans index). Lorsque vous l’utilisez pour rechercher l’appartenance à un ensemble ou la présence d’une clé de dictionnaire, la complexité est en moyenne constante (comme on peut s’y attendre d’une implémentation basée sur une table de hachage):

En C ++, vous pouvez utiliser std::find pour déterminer si un élément est contenu dans un std::vector . La complexité est dite linéaire (comme on peut s’attendre à un tableau non sortingé sans index). Si vous vous assurez que le vecteur est sortingé, vous pouvez également utiliser std::binary_search .

Les conteneurs associatifs fournis par la bibliothèque standard ( std::set , std::unordered_set , std::map , …) fournissent la fonction membre find() qui fonctionnera mieux que la recherche linéaire, c.-à-d. Logarithmique ou temps constant selon que vous avez choisi l’alternative commandée ou non.

Si vous le souhaitez, vous pouvez utiliser un modèle magique pour écrire une fonction wrapper qui sélectionne la méthode correcte pour le conteneur en question, par exemple, comme présenté dans cette réponse .

Vous pouvez aborder cela de deux manières:

Vous pouvez utiliser std::find partir de :

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

ou vous pouvez parcourir chaque élément de vos conteneurs avec des boucles à distance:

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

Python fait différentes choses in fonction du type de conteneur. En C ++, vous voudriez le même mécanisme. La règle de base pour les conteneurs standard est que si ils fournissent un find() , ce sera un meilleur algorithme que std::find() (par exemple, find() pour std::unordered_map est O (1), mais std::find() est toujours O (N)).

Nous pouvons donc écrire quelque chose pour faire cette vérification nous-mêmes. Le plus concis serait de tirer parti des if constexpr de C ++ 17 et d’utiliser quelque chose comme can_apply de can_apply :

 template  using find_t = decltype(std::declval().find(std::declval())); template  bool in(Container const& c, Key const& key) { if constexpr (can_apply{}) { // 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, nous pouvons tirer parti de l’expression SFINAE:

 namespace details { // the specialized case template  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  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  bool in(Container const& c, Key const& key) { return details::in_impl(c, key, 0); } 

Notez que dans les deux cas, nous using std::begin; using std::end; using std::begin; using std::end; deux étapes pour gérer tous les conteneurs standard, les tableaux bruts et tous les conteneurs fournis / adaptés à l’utilisation.

Je suppose que l’on pourrait utiliser ce thread et créer une version personnalisée de la fonction in .

L’idée principale est d’utiliser SFINAE (Échec de substitution n’est pas une erreur) pour différencier les conteneurs associatifs (qui ont un membre key_type ) des conteneurs de séquence (qui n’ont pas de membre key_type ).

Voici une implémentation possible:

 namespace detail { template struct is_associative : std::false_type {}; template struct is_associative> : std::true_type {}; template auto in(const C& container, const T& value) -> std::enable_if_t::value, bool> { using std::cend; return container.find(value) != cend(container); } template auto in(const C& container, const T& value) -> std::enable_if_t::value, bool> { using std::cbegin; using std::cend; return std::find(cbegin(container), cend(container), value) != cend(container); } } template auto in(const C& container, const T& value) { return detail::in(container, value); } 

Petit exemple d’utilisation sur WANDBOX .

Cela vous donne un opérateur infix *in* :

 namespace notstd { namespace ca_helper { templateclass, class, class...> struct can_apply:std::false_type{}; templatestruct voider{using type=void;}; templateusing void_t=typename voider::type; templateclass Z, class...Ts> struct can_apply>, Ts...>:std::true_type{}; } templateclass Z, class...Ts> using can_apply = ca_helper::can_apply; namespace find_helper { template using dot_find_r = decltype(std::declval().find(std::declval())); template using can_dot_find = can_apply< dot_find_r, C, T >; template constexpr std::enable_if_t{},bool> find( C&& c, T&& t ) { using std::end; return c.find(std::forward(t)) != end(c); } template constexpr std::enable_if_t{},bool> find( C&& c, T&& t ) { using std::begin; using std::end; return std::find(begin(c), end(c), std::forward(t)) != end(c); } template constexpr bool finder( C&& c, T&& t ) { return find( std::forward(c), std::forward(t) ); } } template constexpr bool find( C&& c, T&& t ) { return find_helper::finder( std::forward(c), std::forward(t) ); } struct finder_t { template constexpr bool operator()(C&& c, T&& t)const { return find( std::forward(c), std::forward(t) ); } constexpr finder_t() {} }; constexpr finder_t finder{}; namespace named_operator { templatestruct make_operator{make_operator(){}}; template struct half_apply { T&& lhs; }; template half_apply operator*( Lhs&& lhs, make_operator ) { return {std::forward(lhs)}; } template auto operator*( half_apply&& lhs, Rhs&& rhs ) -> decltype( named_invoke( std::forward(lhs.lhs), Op{}, std::forward(rhs) ) ) { return named_invoke( std::forward(lhs.lhs), Op{}, std::forward(rhs) ); } } namespace in_helper { struct in_t:notstd::named_operator::make_operator {}; template bool named_invoke( T&& t, in_t, C&& c ) { return ::notstd::find(std::forward(c), std::forward(t)); } } in_helper::in_t in; } 

Sur un conteneur plat, comme un tableau vectoriel ou une chaîne, il s’agit de O (n).

Sur un conteneur sortingé associatif, comme un std::map , std::set , c’est O (lg (n)).

Sur un conteneur associé non ordonné, comme std::unordered_set , il s’agit de O (1).

Code de test:

 std::vector v{1,2,3}; if (1 *in* v) std::cout << "yes\n"; if (7 *in* v) std::cout << "no\n"; std::map> m{ {"hello", "world"} }; if ("hello" *in* m) std::cout << "hello world\n"; 

Exemple en direct .

C ++ 14, mais principalement pour enable_if_t .

Que se passe-t-il?

Eh bien, can_apply est un bit de code qui me permet d'écrire can_dot_find , qui détecte (au moment de la compilation) si container.find(x) est une expression valide.

Cela me permet d'envoyer le code de recherche pour utiliser la recherche de membre si elle existe. S'il n'existe pas, une recherche linéaire utilisant std::find est utilisée à la place.

Ce qui est un peu un mensonge. Si vous définissez une fonction libre find(c, t) dans l'espace de noms de votre conteneur, elle l'utilisera plutôt que l'une des deux précédentes. Mais c'est moi qui suis fantaisie (et cela vous permet d'étendre les conteneurs tiers avec *in* support).

Cette extensibilité ADL (dépendante des arguments) (la capacité d'extension tierce) est la raison pour laquelle nous avons trois fonctions différentes nommées find , deux dans un espace de noms helper et une dans notstd . Vous êtes censé appeler notstd::find .

Ensuite, nous voulons un python-like, et qu'est-ce qui est plus python qu'un opérateur infixe? Pour ce faire en C ++, vous devez envelopper le nom de votre opérateur dans d'autres opérateurs. J'ai choisi * , nous obtenons donc un opérateur nommé infix *in* .


TL; DR

Vous using notstd::in; pour importer l'opérateur nommé in .

Après cela, t *in* c vérifie d'abord si find(t,c) est valide. Sinon, il vérifie si c.find(t) est valide. Si cela échoue, il effectue une recherche linéaire de c utilisant std::begin std::end et std::find .

Cela vous donne de très bonnes performances sur une grande variété de contenants std .

La seule chose qu'il ne supporte pas est

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

comme les opérateurs (autres que = ) ne peuvent pas déduire les listes d’initialisation je crois. Vous pourriez obtenir

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

travailler.

Vous pouvez utiliser std :: find à partir de . Mais cela ne fonctionne que pour les types de données comme, std :: map, std :: vector etc. Notez également que cela retournera l’iterator au premier élément trouvé égal à la valeur que vous passez, contrairement à l’opérateur IN en python qui renvoie true / faux.