Pourquoi std :: set n'a-t-il pas de fonction membre «contient»?

103

J'utilise beaucoup std::set<int> et je dois souvent simplement vérifier si un tel ensemble contient un nombre ou non.

Je trouverais naturel d'écrire:

if (myset.contains(number))
   ...

Mais à cause du manque de containsmembre, j'ai besoin d'écrire la lourde:

if (myset.find(number) != myset.end())
  ..

ou le pas aussi évident:

if (myset.count(element) > 0) 
  ..

Y a-t-il une raison à cette décision de conception?

Jabberwocky
la source
7
La plupart des bibliothèques standard fonctionnent avec des itérateurs, donc normalement les fonctions retournant des itérateurs sont ce que vous attendez. Pas trop difficile cependant d'écrire une fonction pour résumer cela. Très probablement, le compilateur le mettra en ligne car il ne devrait s'agir que d'une ou deux lignes de code et vous obtiendrez les mêmes performances.
NathanOliver
3
Un autre problème (plus fondamental) de l' count()approche est qu'elle fait plus de travail que ce countains()qu'elle aurait à faire.
Leo Heinsaar
11
La raison fondamentale derrière cette décision de conception est que contains()qui retourne un boolserait perdre de précieuses informations sur l' endroit où l'élément est dans la collection . find()préserve et renvoie ces informations sous la forme d'un itérateur, c'est donc un meilleur choix pour une bibliothèque générique comme STL. (Cela ne bool contains()veut pas dire que ce n'est pas très agréable ou même nécessaire.)
Leo Heinsaar
3
Il est facile d'écrire une contains(set, element)fonction gratuite en utilisant l'interface publique de l'ensemble. Par conséquent, l'interface de l'ensemble est fonctionnellement complète; l'ajout d'une méthode pratique augmente simplement l'interface sans activer de fonction supplémentaire, ce qui n'est pas la méthode C ++.
Toby Speight
3
Fermons-nous tout ces jours-ci? En quoi cette question est-elle «principalement basée sur l'opinion»?
M. Alien

Réponses:

148

Je pense que c'était probablement parce qu'ils essayaient de faire std::setet std::multisetaussi similaire que possible. (Et a évidemment countune signification parfaitement sensée pour std::multiset.)

Personnellement, je pense que c'était une erreur.

Cela n'a pas l'air si mal si vous prétendez que countc'est juste une faute d'orthographe containset écrivez le test comme:

if (myset.count(element)) 
   ...

C'est quand même dommage.

Martin Bonner soutient Monica
la source
5
Incidemment, c'est exactement la même chose avec les cartes et les multimaps (ce qui est tout aussi moche, mais moins moche que toutes ces comparaisons avec .end()).
Matteo Italia
8
Alternativement, ils n'ont peut-être vu aucun besoin d'un membre supplémentaire contains(), au motif qu'il serait redondant car pour tout std::set<T> set T t, le résultat de s.contains(t)est exactement identique au résultat de static_cast<bool>(s.count(t)). Comme l'utilisation de la valeur dans une expression conditionnelle la convertirait implicitement en bool, ils ont peut-être estimé que cela count()servait assez bien l'objectif.
Justin Time - Réintègre Monica
2
Faute d'orthographe? if (myset.ICanHaz(element)) ...: D
Stéphane Gourichon
3
@MartinBonner Cela n'a pas vraiment d'importance si les raisons de l'omettre étaient stupides. Cela n'a pas non plus vraiment d'importance si la conversation n'était pas la justification finale à 100%. Votre réponse ici n'est qu'une estimation raisonnable de ce que vous pensez que cela devrait être. La conversation et la réponse d'une personne non seulement impliquée, mais chargée de la proposer (même si ce n'est pas le cas) sont incontestablement plus proches de la vérité que cette supposition, peu importe comment vous la regardez. Au minimum, vous devriez au moins le mentionner dans cette réponse, ce serait une grande amélioration et ce serait la chose responsable à faire.
Jason C
2
@JasonC: Pourriez-vous continuer et éditer une section en bas s'il vous plaît? Je ne comprends pas vraiment ce que vous essayez de faire valoir, et les commentaires ne sont probablement pas la meilleure façon de clarifier cela. Merci!
Martin Bonner soutient Monica
44

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

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

Quant à la count() approche en général, bien que ce soit souvent une solution de contournement correcte, le problème est qu'elle fait plus de travail que ce contains() qu'elle aurait à 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 groupe Norme ISO C ++ - Propositions futures.

Leo Heinsaar
la source
5
Et il est intéressant de noter que cette discussion s'est terminée par un quasi-consensus sur le fait qu'elle était souhaitable et qu'on vous a demandé de rédiger une proposition à ce sujet.
PJTraill
@PJTraill True, et la raison pour laquelle je ne suis pas allé de l'avant est que contains(), de toute évidence, interagirait fortement avec les conteneurs et les algorithmes existants, ce qui serait fortement impacté par les concepts et les plages - au moment prévu pour entrer dans C ++ 17 - et J'étais convaincu (à la suite de la discussion et de quelques échanges de courriels privés) que c'était une meilleure idée de les attendre en premier. Bien sûr, en 2015, il n'était pas clair que ni les concepts ni les plages ne parviendraient à C ++ 17 (en fait, il y avait de grands espoirs). Je ne suis pas sûr que cela vaille la peine de le poursuivre maintenant.
Leo Heinsaar
1
Car std::set(c'est ce que la question pose), je ne vois pas comment countça marche plus qu'il n'en containsfaudrait. L'implémentation glibc de countest (en gros) return find(value) == end() ? 0 : 1;. Mis à part les détails sur l'opérateur ternaire par rapport au retour juste != end()(que je m'attendrais à ce que l'optimiseur supprime), je ne vois pas comment il y a plus de travail.
Martin Bonner soutient Monica
4
"... contains () qui renvoie un booléen perdrait des informations précieuses sur l'emplacement de l'élément dans la collection " - Si l'utilisateur appelle myset.contains()(s'il existait), ce serait une indication assez forte que cette information n'est pas précieuse ( à l'utilisateur dans ce contexte).
Keith Thompson
1
Pourquoi count()faire plus de travail qu'il n'en contains()faudrait std::set? C'est unique et count()pourrait donc être return contains(x) ? 1 : 0;exactement la même chose.
Timmmm
22

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

Si une syntaxe étrange ne vous dérange pas, 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 stdtypes C ++ en utilisant cette technique.

Il est beaucoup plus logique de simplement faire ceci:

if (some_set.count(some_element)) {
}

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

Ce qui est vraiment triste, c'est que l'écriture d'un efficace containspourrait être plus rapide sur un multimapou multiset, car ils n'ont qu'à trouver un élément, alors qu'il countfaut trouver chacun d'eux et les compter .

Un multiset contenant 1 milliard d'exemplaires sur 7 (vous savez, au cas où vous en auriez épuisé) peut avoir un très lent .count(7), mais pourrait avoir un très rapidecontains(7) .

Avec la méthode d'extension ci-dessus, nous pourrions accélérer les choses dans ce cas en utilisant lower_bound, en comparant end, puis en comparant à l'élément. Faire cela pour un miaulement non ordonné ainsi qu'un miaulement ordonné nécessiterait cependant des surcharges sophistiquées de SFINAE ou spécifiques au conteneur.

Yakk - Adam Nevraumont
la source
2
1 milliard d'exemplaires sur 7? Et ici, je pensais std::setne peut pas contenir de doublons et std::set::countreviendra donc toujours 0ou 1.
nwp
5
@nwp std::multiset::countcan
milleniumbug
2
@nwp Mon manque backticksautour du mot «ensemble» est parce que je ne fais pas référence std::setspécifiquement. Pour que vous vous sentiez mieux, je vais ajouter plusieurs
Yakk - Adam Nevraumont
3
Il me semble manquer la blague pour tout ce à quoi "miaulement" était censé être une référence.
user2357112 prend en charge Monica
2
@ user2357112 meow est un espace réservé pour "set or map". Demandez pourquoi à la STL .
Yakk - Adam Nevraumont
12

Vous examinez un cas particulier et ne voyez pas une image plus grande. Comme indiqué dans la documentation, std::set répond aux exigences du concept AssociativeContainer . Pour ce concept, cela n'a aucun sens d'avoir une containsméthode, car elle est pratiquement inutile pour std::multisetet std::multimap, mais countfonctionne bien pour tous. Bien que la méthode containspuisse être ajoutée en tant qu'alias pour countfor std::set, std::mapet leurs versions hachées (comme lengthpour size()in std::string), mais il semble que les créateurs de bibliothèques n'en ont pas vu le besoin réel.

Slava
la source
8
Notez que stringc'est un monstre: il existait avant la STL, où il existait lengthet toutes ces méthodes qui sont basées sur des index, puis a été «conteneurisé» pour s'adapter au modèle STL ... sans supprimer les méthodes existantes pour des raisons de compatibilité descendante . Voir GotW # 84: Monoliths Unstrung => stringenfreint vraiment le principe de conception "quantité minimale de fonctions membres".
Matthieu M.
5
Mais alors la question devient "Pourquoi vaut-il la peine d'avoir un concept AssociativeContainer comme ça?" - et je ne suis pas sûr que ce soit avec le recul.
Martin Bonner soutient Monica
24
Demander si un multiset, une multi-carte ou une carte contient quelque chose me semble parfaitement logique. En fait, l' containseffort est égal sur un ensemble / carte, mais peut être fait plus rapidement que countsur un multi-ensemble / multi-carte.
Yakk - Adam Nevraumont
5
AssociativeContainer ne nécessite pas que les classes n'aient pas decontains méthode.
user2357112 prend en charge Monica
6
@Slava C'est comme dire size()et empty()sont des doublons, mais de nombreux conteneurs ont les deux.
Barry
10

Bien que je ne sache pas pourquoi std::seta no containsmais countqui ne retourne que jamais 0ou 1, vous pouvez écrire une containsfonction d'assistance basée sur un modèle comme celle-ci:

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)) ...
rustyx
la source
3
-1, parce que cela est carrément contredit par le fait qu'en fait la containsméthode existe, elle est juste nommée d'une manière stupide.
Matteo Italia
4
"La STL s'efforce d'offrir une interface minimale" chough std::string toux
bolov
6
@bolov: votre point? std.::stringne fait PAS partie de la STL! Il fait partie de la bibliothèque standard et a été modélisé rétroactivement ...
MFH
3
@MatteoItalia countpeut être plus lent car il a effectivement besoin de faire deux finds pour obtenir le début et la fin de la plage si le code est partagé avec multiset.
Mark Ransom
2
L'OP sait déjà qu'il est redondant, mais souhaite apparemment que le code soit lu explicitement contains. Je ne vois rien de mal à cela. @MarkRansom le petit SFINAE est d'empêcher ce modèle de se lier à des choses qu'il ne devrait pas.
rustyx
7

La vraie raison setest un mystère pour moi, mais une explication possible pour cette même conception mappourrait ê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 donnerait deux map recherches.

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

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

qui consomme une seule maprecherche.

Lorsque nous réalisons cela setet que nous mapsommes faits de la même chair, nous pouvons également appliquer ce principe à set. Autrement dit, si nous voulons agir sur un élément dans le setuniquement s'il est présent 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 n'est qu'une simple spéculation.

Martin Drozdik
la source
1
Oui, mais cela ne s'applique pas aux ensembles d'entiers.
Jabberwocky
7
Sauf que les gens peuvent très bien écrire if (myMap.count("Meaning of universe")), alors ...?
Barry
@MichaelWalz Oups, vous avez raison. J'ai modifié ma réponse pour inclure également l'exemple d'ensemble. Cependant, le raisonnement pour un ensemble d'entiers est un mystère pour moi.
Martin Drozdik
2
Cela ne peut pas être vrai. Ils peuvent aussi facilement écrire votre code inefficace avec containsqu'avec count.
Martin Bonner soutient Monica
2

Depuis c ++ 20,

bool contains( const Key& key ) const

est disponible.

Andy
la source
0

Et binary_search?

 set <int> set1;
 set1.insert(10);
 set1.insert(40);
 set1.insert(30);
 if(std::binary_search(set1.begin(),set1.end(),30))
     bool found=true;
Massimiliano Di Cavio
la source
Cela ne fonctionnerait pas pour std::unordered_set, mais pour std::setcela.
Jabberwocky
C'est normal, binary_search ne fonctionne que pour les arbres binaires.
Massimiliano Di Cavio
0

contains () doit renvoyer un booléen. En utilisant le compilateur C ++ 20, j'obtiens la sortie suivante pour le code:

#include<iostream>
#include<map>
using namespace std;

int main()
{
    multimap<char,int>mulmap;
    mulmap.insert(make_pair('a', 1)); //multiple similar key
    mulmap.insert(make_pair('a', 2)); //multiple similar key
    mulmap.insert(make_pair('a', 3)); //multiple similar key
    mulmap.insert(make_pair('b', 3));
    mulmap.insert({'a',4});
    mulmap.insert(pair<char,int>('a', 4));
    
    cout<<mulmap.contains('c')<<endl;  //Output:0 as it doesn't exist
    cout<<mulmap.contains('b')<<endl;  //Output:1 as it exist
}
Bashar
la source
-1

Une autre raison est que cela donnerait au programmeur la fausse impression que std :: set est un ensemble au sens de la théorie mathématique des ensembles. S'ils implémentent cela, alors de nombreuses autres questions suivront: 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 autres opérations et prédicats d'ensemble?

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ées que contains (). Les fonctions et objets fonctionnels 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é d'ensemble mathématique complète, il a non seulement le choix du conteneur sous-jacent, mais aussi le choix des détails d'implémentation, par exemple, sa fonction théorie_union () fonctionnerait-elle avec des objets immuables, mieux adaptés à la programmation fonctionnelle , ou modifierait-il ses opérandes et économiserait-il de la mémoire? Serait-il implémenté en tant qu'objet 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?

Dans l'état actuel des choses, std :: set n'est qu'un conteneur, bien adapté pour l'implémentation de set au sens mathématique, mais il est presque aussi loin d'être un ensemble théorique que std :: vector d'être un vecteur théorique.

Mike Tyukanov
la source