Quelle est la méthode C ++ pour vérifier si un élément est contenu dans un tableau / une liste, comme ce que fait 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 à l'opérateur in de Python?
La complexité du temps de Python in opérateur varie en fonction de la structure de données il est en fait appelé avec. Lorsque vous l'utilisez avec une liste, la complexité est linéaire (que l'on pourrait attendre d'un tableau non-trié sans index). Lorsque vous l'utilisez pour rechercher l'appartenance ou de la présence d'une clé de dictionnaire complexité est constante en moyenne (que l'on pourrait attendre d'une table de hachage basée sur la mise en œuvre):
En C++, vous pouvez utiliser std::find afin de déterminer si un élément est contenu dans un std::vector. La complexité est dit linéaire (que l'on pourrait attendre d'un tableau non-trié sans index). Si vous assurez-vous que le vecteur est trié, vous pouvez également utiliser std::binary_search pour atteindre le même en temps logarithmique.
Les conteneurs associatifs fournis par la bibliothèque standard (std::set, std::unordered_set, std::map, ...) qui fournissent la fonction de membre find() pour ce, qui donneront de meilleurs résultats que la recherche linéaire, c'est à dire, logarithmiques ou de la constante de temps en fonction de si vous avez choisi la commande ou de la non-ordonnée alternative.
Si vous le souhaitez, vous pouvez utiliser un modèle de magie pour écrire un wrapper de la fonction qui récupère la bonne méthode pour le conteneur à portée de main, par exemple, tel que présenté dans cette réponse.
Vous pouvez aborder cela de deux manières:
Vous pouvez utiliser std::find de <algorithm> :
auto it = std::find(container.begin(), container.end(), value);
if (it != container.end())
return it;
ou vous pouvez parcourir tous les éléments de vos conteneurs avec des boucles à distance:
for(const auto& it : container)
{
if(it == value)
return it;
}
Python n'différentes choses pour in selon le type de conteneur, il est. En C++, vous voulez le même mécanisme. Règle de base pour les conteneurs standard, c'est que s'ils fournissent find(), ça va être un meilleur algorithme que std::find() (par exemple, find() pour std::unordered_map O(1), mais std::find() est toujours en O(N)).
Nous pouvons donc écrire quelque chose à faire que de vérifier nous-mêmes. Le plus pertinent serait de prendre avantage du C++17 if constexpr et d'utiliser quelque chose comme Yakk de l' 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, on peut tirer avantage de l'expression 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);
}
Notez que dans les deux cas, nous avons l' using std::begin; using std::end; en deux étapes afin de gérer tous les conteneurs standard, raw tableaux, et tout usage/adapté conteneurs.
Je suppose que l'on pourrait faire usage de ce thread et de créer une version personnalisée de in fonction.
L'idée principale est d'utiliser SFINAE (Substitution de l'Échec n'Est Pas Une Erreur) pour différencier les conteneurs associatifs (qui ont key_type membre) de la séquence des conteneurs (qui n'ont aucune key_type membre).
Voici une implémentation possible:
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);
}
Petit exemple d'utilisation sur WANDBOX.
Cela vous donne un infixe *in* opérateur:
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;
}
Sur un contenant plat, comme un tableau de vecteurs ou de chaîne, il est O(n).
Sur un cadre associatif triés contenant, comme un std::map, std::set, il est O(lg n)).
Sur un non-ordonnée conteneur associé, comme std::unordered_set, il est O(1).
Le code de Test:
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, mais surtout pour enable_if_t.
Donc ce qui se passe ici?
Eh bien, can_apply est un morceau 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'expédition de la recherche de code pour utiliser des etats-trouver, si elle existe. Si elle n'existe pas, un linéaire de recherche à l'aide de std::find est utilisé à la place.
Ce qui est un peu un mensonge. Si vous définissez une fonction libre find(c, t) en l'espace de noms de votre conteneur, il va l'utiliser plutôt que les deux ci-dessus. Mais c'est à moi d'être de fantaisie (et il vous permet d'étendre la 3e partie des récipients avec de l' *in* de soutien).
Que l'ADL (argument dépendante de recherche) extensibity (la 3ème partie de l'extension de la capacité), est pourquoi nous avons trois fonctions différentes nommé find, deux à une aide de l'espace de noms et un en notstd. Vous avez l'intention d'appeler notstd::find.
Ensuite, nous voulons un python-comme in, et ce qui est plus python que comme un opérateur infixe? Pour ce faire, en C++, vous devez emballer votre nom d'opérateur en d'autres opérateurs. J'ai choisi *, nous obtenons donc un infixe *in* nommé opérateur.
Vous n' using notstd::in; d'importer le nom de l'opérateur in.
Après, t *in* c vérifie d'abord si find(t,c) est valide. Si non, il vérifie si c.find(t) est valide. Si cela échoue, il fait une recherche linéaire de c l'aide std::begin std::end et std::find.
Cela vous donne de très bonnes performances sur une grande variété d' std des conteneurs.
La seule chose qu'il ne prend pas en charge est
if (7 *in* {1,2,3})
en tant qu'opérateurs (autres que =) ne peut pas déduire de l'initialiseur listes je crois. Vous pourriez obtenir
if (7 *in* il(1,2,3))
de travail.
Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.
