Pourquoi ne std::set pas une "contient" fonction membre?

Pour pouvoir écrire if (s.contains()), contains() doit retourner un bool (ou un type convertible en bool, qui est une autre histoire), comme le fait binary_search.

Le raison fondamentale derrière la conception de décision pas pour faire de cette façon est que contains() qui retourne bool serait perdre de précieuses informations sur l'endroit où l'élément est dans la collection. find() conserve et renvoie cette information sous la forme d'un itérateur, c'est donc un meilleur choix pour une bibliothèque Générique comme la STL. Cela a toujours été le principe Alex Stepanov, comme il l'a souvent expliqué (par exemple, ici).

En ce qui concerne l'approche count() en général, bien que ce soit souvent une solution de contournement correcte, le problème est que Il fait plus de travail qu'un contains() devrait faire .

Cela ne veut pas dire qu'un bool contains() n'est pas très agréable à avoir ou même nécessaire. Il y a quelque temps, nous avons eu une longue discussion sur cette même question dans le Standard ISO C++ - les Futures Propositions du groupe.

Il lui manque parce que personne ne l'a ajouté. Personne ne l'a ajouté car les conteneurs de la STL que la bibliothèque std a incorporés étaient conçus pour être minimes dans l'interface. (Notez que std::string ne vient pas de la STL de la même manière).

Si cela ne vous dérange pas une syntaxe étrange, vous pouvez la simuler:

template<class K>
struct contains_t {
  K&& k;
  template<class C>
  friend bool operator->*( C&& c, contains_t&& ) {
    auto range = std::forward<C>(c).equal_range(std::forward<K>(k));
    return range.first != range.second;
    // faster than:
    // return std::forward<C>(c).count( std::forward<K>(k) ) != 0;
    // for multi-meows with lots of duplicates
  }
};
template<class K>
containts_t<K> contains( K&& k ) {
  return {std::forward<K>(k)};
}

Utilisation:

if (some_set->*contains(some_element)) {
}

Fondamentalement, vous pouvez écrire des méthodes d'extension pour la plupart des types C++ std en utilisant cette technique.

Il est beaucoup plus logique de simplement faire ce:

if (some_set.count(some_element)) {
}

Mais je suis amusé par la méthode de la méthode d'extension.

Vraiment triste, c'est que l'écriture d'un efficace contains pourrait être plus rapide sur un multimap ou multiset, comme ils ont juste à trouver un élément, tandis que count a trouver chacun d'eux et de les compter.

Un multiset contenant 1 milliard de copies de 7 (vous savez, au cas où vous manqueriez) peut avoir un .count(7) très lent, mais pourrait avoir un contains(7) très rapide.

Avec la méthode d'extension ci-dessus, nous pourrions faire il est plus rapide pour ce cas en utilisant lower_bound, en comparant à end, puis en comparant à l'élément. Faire cela pour un Miaou non ordonné ainsi qu'un Miaou ordonné nécessiterait des surcharges SFINAE ou spécifiques au conteneur.

Vous regardez dans un cas particulier et ne voyez pas une image plus grande. Comme indiqué dans la documentation std::set répond à l'exigence de AssociativeContainer concept. Pour cette notion n'a aucun sens d'avoir contains méthode, comme il est assez inutile pour les std::multiset et std::multimap, mais count fonctionne très bien pour tous. Bien que la méthode contains puisse être ajoutée en tant qu'alias pour count pour std::set, std::map et leurs versions hachées (comme length pour size() dans std::string), mais ressemble à une bibliothèque les créateurs n'en voyaient pas le besoin réel.

Bien que je ne sache pas pourquoi std::set n'a pas contains mais count qui ne renvoie que 0 ou 1, vous pouvez écrire une fonction d'aide contains template comme ceci:

template<class Container, class T>
auto contains(const Container& v, const T& x)
-> decltype(v.find(x) != v.end())
{
    return v.find(x) != v.end();
}

Et utilisez-le comme ceci:

    if (contains(myset, element)) ...

La vraie raison de set est un mystère pour moi, mais une explication possible pour cette même conception dans map pourrait être d'empêcher les gens d'écrire du code inefficace par accident:

if (myMap.contains("Meaning of universe"))
{
    myMap["Meaning of universe"] = 42;
}

Ce qui entraînerait deux recherches map.

Au lieu de cela, vous êtes obligé d'obtenir un itérateur. Cela vous donne un indice mental que vous devriez réutiliser l'itérateur:

auto position = myMap.find("Meaning of universe");
if (position != myMap.cend())
{
    position->second = 42;
}

Qui ne consomme qu'une seule recherche map.

Lorsque nous réalisons que set et map sont fabriqués à partir du même chair, nous pouvons appliquer ce principe aussi à set. C'est, si nous voulons agir sur un élément de la set seulement si elle est présente dans le set, cette conception peut nous empêcher d'écrire du code comme ceci:

struct Dog
{
    std::string name;
    void bark();
}

operator <(Dog left, Dog right)
{
    return left.name < right.name;
}

std::set<Dog> dogs;
...
if (dogs.contain("Husky"))
{
    dogs.find("Husky")->bark();
}

Bien sûr, tout cela est une simple spéculation.

Une autre raison est que cela donnerait à un programmeur la fausse impression que std:: set est un ensemble dans le sens de la théorie des ensembles mathématiques. S'ils implémentent cela, alors beaucoup d'autres questions suivraient: si un std::set a contains() pour une valeur, pourquoi ne l'a-t-il pas pour un autre ensemble? Où sont union (), intersection () et d'autres opérations et prédicats?

La réponse est, bien sûr, que certaines des opérations set sont déjà implémentées en tant que fonctions dans (std::set_union() etc.) et d'autres sont aussi trivialement implémentés que contains(). Les fonctions et les objets de fonction fonctionnent mieux avec les abstractions mathématiques que les membres d'objet, et ils ne sont pas limités au type de conteneur particulier.

Si l'on a besoin d'implémenter une fonctionnalité complète de math-set, il a non seulement le choix du conteneur sous-jacent, mais il a aussi le choix des détails d'implémentation, par exemple, sa fonction theory_union() fonctionnerait-elle avec des objets immuables, mieux adaptés à la programmation fonctionnelle, ou modifierait-elle sa fonction? opérandes et économiser de la mémoire? Serait-il implémenté en tant qu'objet de fonction dès le début ou il serait préférable d'implémenter une fonction C et d'utiliser std::function si nécessaire?

Comme il est maintenant, std::set est juste un conteneur, bien adapté pour la mise en œuvre de l'ensemble en maths sens, mais il est presque aussi loin d'être théorique défini comme std::vector d'être théorique vecteur.