Warum hat std :: set keine Member-Funktion "enthält"?

103

Ich benutze viel std::set<int>und oft muss ich einfach überprüfen, ob ein solches Set eine Nummer enthält oder nicht.

Ich würde es natürlich finden zu schreiben:

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

Aber wegen des Fehlens eines containsMitglieds muss ich das umständliche schreiben:

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

oder das nicht so offensichtlich:

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

Gibt es einen Grund für diese Entwurfsentscheidung?

Jabberwocky
quelle
7
Der Großteil der Standardbibliothek arbeitet mit Iteratoren, sodass normalerweise Funktionen zur Rückgabe von Iteratoren zu erwarten sind. Es ist jedoch nicht zu schwer, eine Funktion zu schreiben, um das zu abstrahieren. Höchstwahrscheinlich wird der Compiler es inline, da es nur eine oder zwei Codezeilen sein sollten und Sie die gleiche Leistung erhalten.
NathanOliver
3
Ein weiteres (grundlegenderes) Problem des count()Ansatzes besteht darin, dass er mehr Arbeit leistet als countains()nötig.
Leo Heinsaar
11
Der wesentliche Grund hinter dieser Design - Entscheidung ist , dass contains()der zurückkehrt eine boolwürde wertvolle Informationen über verlieren , wo das Element in der Sammlung . find()Bewahrt diese Informationen auf und gibt sie in Form eines Iterators zurück. Daher ist dies eine bessere Wahl für eine generische Bibliothek wie STL. (Das soll nicht heißen, dass a bool contains()nicht sehr schön zu haben oder sogar notwendig ist.)
Leo Heinsaar
3
Es ist einfach, eine contains(set, element)kostenlose Funktion über die öffentliche Oberfläche des Sets zu schreiben . Daher ist die Schnittstelle des Sets funktional vollständig. Durch Hinzufügen einer Convenience-Methode wird lediglich die Benutzeroberfläche vergrößert, ohne dass zusätzliche Funktionen aktiviert werden. Dies ist nicht die C ++ - Methode.
Toby Speight
3
Schließen wir heutzutage alles? Wie ist diese Frage in irgendeiner Weise "primär meinungsbasiert"?
Mr. Alien

Antworten:

148

Ich denke , es war wahrscheinlich , weil sie versuchen , zu machen std::setund std::multisetso ähnlich wie möglich. (Und hat offensichtlich counteine durchaus vernünftige Bedeutung für std::multiset.)

Persönlich denke ich, dass dies ein Fehler war.

Es sieht nicht ganz so schlecht aus, wenn Sie so tun, countals wäre dies nur eine Rechtschreibfehler, containsund den Test wie folgt schreiben:

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

Es ist immer noch eine Schande.

Martin Bonner unterstützt Monica
quelle
5
Übrigens ist es mit Karten und Multimaps genauso (was genauso hässlich ist, aber weniger hässlich als all diese Vergleiche mit .end()).
Matteo Italia
8
Alternativ haben sie möglicherweise keine Notwendigkeit für ein zusätzliches Mitglied gesehen contains(), da es überflüssig wäre, da für jedes std::set<T> sund T tdas Ergebnis von s.contains(t)genau mit dem Ergebnis von identisch ist static_cast<bool>(s.count(t)). Da die Verwendung des Werts in einem bedingten Ausdruck ihn implizit umwandeln würde bool, haben sie möglicherweise das Gefühl, dass dies count()dem Zweck gut genug diente.
Justin Time - Stellen Sie Monica am
2
Rechtschreibfehler? if (myset.ICanHaz(element)) ...: D
Stéphane Gourichon
3
@ MartinBonner Es ist nicht wirklich wichtig, ob die Gründe für das Auslassen dumm waren. Es ist auch nicht wirklich wichtig, ob das Gespräch nicht die 100% endgültige Begründung war. Ihre Antwort hier ist nur eine vernünftige Vermutung, wie Sie denken, dass es sein sollte. Das Gespräch und die Antwort von jemandem, der nicht nur daran beteiligt ist, sondern die Aufgabe hat, es vorzuschlagen (obwohl dies nicht der Fall war), ist der Wahrheit unbestreitbar näher als diese Vermutung, egal wie Sie es betrachten. Zumindest sollten Sie es in dieser Antwort zumindest erwähnen, das wäre eine große Verbesserung und die verantwortliche Sache.
Jason C
2
@JasonC: Könnten Sie bitte einen Abschnitt unten bearbeiten? Ich verstehe den Punkt, den Sie ansprechen möchten, nicht wirklich, und Kommentare sind wahrscheinlich nicht der beste Weg, dies zu klären. Vielen Dank!
Martin Bonner unterstützt Monica
44

Um schreiben zu können if (s.contains()), contains()muss ein bool(oder ein konvertierbarer Typ bool, der eine andere Geschichte ist) zurückgegeben werden, wie es der binary_searchFall ist.

Der wesentliche Grund hinter der Design - Entscheidung nicht es auf diese Art und Weise zu tun , ist , dass contains()der zurückgibt einer boolwürde wertvolle Informationen über verlieren , wo das Element in der Sammlung . find()Bewahrt diese Informationen auf und gibt sie in Form eines Iterators zurück. Daher ist dies eine bessere Wahl für eine generische Bibliothek wie STL. Dies war schon immer das Leitprinzip für Alex Stepanov, wie er oft erklärt hat (zum Beispiel hier ).

Was den count()Ansatz im Allgemeinen betrifft , so ist das Problem, obwohl er oft in Ordnung ist, dass er mehr Arbeit leistet, als ein contains() zu tun hätte .

Das heißt nicht, dass a bool contains()nicht sehr schön zu haben oder sogar notwendig ist. Vor einiger Zeit hatten wir in der Gruppe ISO C ++ Standard - Future Proposals eine lange Diskussion über dieses Problem.

Leo Heinsaar
quelle
5
Es ist interessant festzustellen, dass diese Diskussion mit einem nahezu übereinstimmenden Konsens darüber endete, dass dies wünschenswert ist, und dass Sie gebeten wurden, einen Vorschlag dafür zu schreiben.
PJTraill
@PJTraill True, und der Grund, warum ich nicht weitergearbeitet habe, ist, dass contains()dies offensichtlich stark mit vorhandenen Containern und Algorithmen interagieren würde, was stark von Konzepten und Bereichen beeinflusst würde - zu der Zeit, die voraussichtlich in C ++ 17 verfügbar sein wird - und Ich war überzeugt (als Ergebnis der Diskussion sowie einiger privater E-Mail-Austausche), dass es eine bessere Idee war, zuerst auf sie zu warten. Natürlich war 2015 nicht klar, dass weder Konzepte noch Bereiche es nicht in C ++ 17 schaffen würden (tatsächlich gab es große Hoffnungen, dass sie es schaffen würden). Ich bin mir jedoch nicht sicher, ob es sich lohnt, es jetzt zu verfolgen.
Leo Heinsaar
1
Denn std::set(worum es in der Frage geht), ich sehe nicht, wie countmehr funktioniert, als containsnötig wäre. Die glibc-Implementierung von countist (ungefähr) return find(value) == end() ? 0 : 1;. Abgesehen von Details über den ternären Operator und nicht nur über die Rückkehr != end()(von denen ich erwarten würde, dass sie vom Optimierer entfernt werden), kann ich nicht sehen, wie es noch mehr Arbeit gibt.
Martin Bonner unterstützt Monica
4
"... enthält (), das einen Bool zurückgibt, würde wertvolle Informationen darüber verlieren, wo sich das Element in der Sammlung befindet. " - Wenn der Benutzer aufruft myset.contains()(falls vorhanden), wäre dies ein ziemlich starker Hinweis darauf, dass diese Informationen nicht wertvoll sind ( an den Benutzer in diesem Zusammenhang).
Keith Thompson
1
Warum macht count()mehr Arbeit als contains()nötig std::set? Es ist einzigartig, count()könnte also return contains(x) ? 1 : 0;genau das gleiche sein.
Timmmm
22

Es fehlt es, weil niemand es hinzugefügt hat. Niemand hat es hinzugefügt, weil die Container aus der STL, die in der stdBibliothek enthalten waren, so konzipiert wurden, dass sie nur eine minimale Schnittstelle haben. (Beachten Sie, dass std::stringdies nicht auf die gleiche Weise von der STL kam).

Wenn Ihnen eine seltsame Syntax nichts ausmacht, können Sie sie vortäuschen:

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

verwenden:

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

Grundsätzlich können Sie stdmit dieser Technik Erweiterungsmethoden für die meisten C ++ - Typen schreiben .

Es ist viel sinnvoller, dies einfach zu tun:

if (some_set.count(some_element)) {
}

aber ich bin amüsiert von der Methode der Erweiterungsmethode.

Das wirklich Traurige ist, dass das Schreiben eines effizienten containsauf einem multimapoder schneller sein kann multiset, da sie nur ein Element finden müssen, während countsie jedes von ihnen finden und zählen müssen .

Ein Multiset mit 1 Milliarde Kopien von 7 (Sie wissen, falls Sie keine mehr haben) kann sehr langsam sein .count(7), aber sehr schnell contains(7).

Mit der obigen Erweiterungsmethode könnten wir es für diesen Fall schneller machen lower_bound, indem wir enddas Element verwenden , mit ihm vergleichen und dann mit ihm vergleichen. Dies sowohl für einen ungeordneten als auch für einen geordneten Miau zu tun, würde jedoch ausgefallene SFINAE- oder container-spezifische Überladungen erfordern.

Yakk - Adam Nevraumont
quelle
2
1 Milliarde Exemplare von 7? Und hier dachte ich, std::setkann keine Duplikate enthalten und werde daher std::set::countimmer zurückkehren 0oder 1.
nwp
5
@nwp std::multiset::countcan
Milleniumbug
2
@nwp Mein Mangel an backticksum das Wort "set" ist, weil ich mich nicht std::setspeziell beziehe . Damit Sie sich besser fühlen, füge ich Multi
Yakk - Adam Nevraumont
3
Mir scheint der Witz für das zu fehlen, worauf "Miau" eigentlich Bezug nehmen sollte.
user2357112 unterstützt Monica
2
@ user2357112 meow ist ein Platzhalter für "set or map". Fragen Sie die STL warum.
Yakk - Adam Nevraumont
12

Sie untersuchen einen bestimmten Fall und sehen kein größeres Bild. Wie in der Dokumentation angegeben, std::set erfüllt es die Anforderungen des AssociativeContainer- Konzepts. Für dieses Konzept macht es keinen Sinn, eine containsMethode zu haben , da sie für std::multisetund so gut wie nutzlos ist std::multimap, aber countfür alle gut funktioniert. Obwohl Verfahren containsals Alias hinzugefügt werden könnten für countfür std::set, std::mapund deren Hash - Versionen (wie lengthfür size()in std::string), aber sieht aus wie Bibliothek Schöpfer nicht wirkliche Notwendigkeit dafür sehen.

Slava
quelle
8
Beachten Sie, dass dies stringein Monster ist: Es existierte vor der STL, wo es hatte lengthund all jene Methoden, die indexbasiert sind, und wurde dann "containerisiert", um in das STL-Modell zu passen ... ohne die vorhandenen Methoden aus Gründen der Abwärtskompatibilität zu entfernen . Siehe GotW # 84: Monoliths Unstrung => stringverstößt wirklich gegen das Entwurfsprinzip "Mindestanzahl an Elementfunktionen ".
Matthieu M.
5
Aber dann lautet die Frage: "Warum lohnt es sich, ein solches AssociativeContainer-Konzept zu haben?" - und ich bin mir nicht sicher, ob es im Nachhinein so war.
Martin Bonner unterstützt Monica
24
Die Frage, ob ein Multiset, eine Multimap oder eine Karte etwas enthält, ist für mich absolut sinnvoll. Tatsächlich containsist der Aufwand für einen Satz / eine Karte gleich, kann jedoch schneller als countfür einen Multiset / eine Multimap erfolgen.
Yakk - Adam Nevraumont
5
AssociativeContainer keine Klassen erfordern nicht eine haben containsMethode.
user2357112 unterstützt Monica
6
@Slava Das ist wie gesagt size()und empty()sind Duplikate, aber viele Container haben beides.
Barry
10

Obwohl ich nicht weiß, warum std::setnein, containsaber countwas immer nur zurückkehrt 0oder 1, können Sie eine Vorlagen- containsHilfsfunktion wie diese schreiben :

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

Und benutze es so:

    if (contains(myset, element)) ...
Rustyx
quelle
3
-1, da dies direkt durch die Tatsache widerlegt wird, dass die containsMethode tatsächlich existiert, wird sie nur auf dumme Weise benannt.
Matteo Italia
4
"Die STL bemüht sich um eine minimale Schnittstelle" Chough std::string Husten
Bolov
6
@ Bolov: Dein Punkt? std.::stringist NICHT Teil der STL! Es ist Teil der Standardbibliothek und wurde rückwirkend als Vorlage verwendet ...
MFH
3
@MatteoItalia countkann langsamer sein, da effektiv zwei Sekunden benötigt werden, findum den Anfang und das Ende des Bereichs zu erhalten, wenn der Code gemeinsam genutzt wird multiset.
Mark Ransom
2
Das OP weiß bereits, dass es redundant ist, möchte aber anscheinend, dass der Code explizit gelesen wird contains. Daran sehe ich nichts auszusetzen. @MarkRansom Die kleine SFINAE soll verhindern, dass diese Vorlage an Dinge gebunden wird, die sie nicht sollte.
Rustyx
7

Der wahre Grund dafür setist für mich ein Rätsel, aber eine mögliche Erklärung für dasselbe Design mapkönnte darin bestehen, zu verhindern, dass Leute versehentlich ineffizienten Code schreiben:

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

Was zu zwei mapSuchvorgängen führen würde.

Stattdessen müssen Sie einen Iterator erhalten. Dies gibt Ihnen einen mentalen Hinweis, dass Sie den Iterator wiederverwenden sollten:

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

das verbraucht nur eine mapSuche.

Wenn wir das erkennen setund mapaus demselben Fleisch bestehen, können wir dieses Prinzip auch auf anwenden set. Das heißt, wenn wir setnur dann auf ein Element einwirken möchten, wenn es in der vorhanden ist set, kann dieses Design uns daran hindern, Code wie folgt zu schreiben:

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

Natürlich ist das alles nur eine Spekulation.

Martin Drozdik
quelle
1
Ja, aber für Intsätze gilt dies nicht.
Jabberwocky
7
Außer die Leute können einfach gut schreiben if (myMap.count("Meaning of universe")), also ...?
Barry
@ MichaelWalz Ups, du hast recht. Ich habe meine Antwort so geändert, dass sie auch das festgelegte Beispiel enthält. Die Begründung für eine Reihe von Ints ist mir jedoch ein Rätsel.
Martin Drozdik
2
Das kann nicht richtig sein. Sie können Ihren ineffizienten Code genauso einfach mit containswie mit schreiben count.
Martin Bonner unterstützt Monica
2

Seit c ++ 20,

bool contains( const Key& key ) const

ist verfügbar.

Andy
quelle
0

Was ist mit 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 D.
quelle
Es würde nicht funktionieren std::unordered_set, aber dafür std::setwürde es funktionieren .
Jabberwocky
Es ist normal, binary_search funktioniert nur für binäre Bäume.
Massimiliano D
0

enthält () muss einen Bool zurückgeben. Mit dem C ++ 20 Compiler erhalte ich folgende Ausgabe für den 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
quelle
-1

Ein weiterer Grund ist, dass es einem Programmierer den falschen Eindruck vermitteln würde, dass std :: set eine Menge im Sinne der mathematischen Mengenlehre ist. Wenn sie das implementieren, würden viele andere Fragen folgen: Wenn ein std :: set () für einen Wert enthält, warum hat es ihn nicht für einen anderen Satz? Wo sind Union (), Intersection () und andere Mengenoperationen und Prädikate?

Die Antwort ist natürlich, dass einige der Mengenoperationen bereits als Funktionen in (std :: set_union () usw.) implementiert sind und andere ebenso trivial implementiert sind wie enthält (). Funktionen und Funktionsobjekte funktionieren mit mathematischen Abstraktionen besser als Objektelemente und sind nicht auf den jeweiligen Containertyp beschränkt.

Wenn eine vollständige Mathe-Set-Funktionalität implementiert werden muss, hat er nicht nur die Wahl des zugrunde liegenden Containers, sondern auch die Wahl der Implementierungsdetails, z. B. würde seine Funktion Theory_union () mit unveränderlichen Objekten funktionieren, die besser für die funktionale Programmierung geeignet sind , oder würde es seine Operanden ändern und Speicher sparen? Wäre es von Anfang an als Funktionsobjekt implementiert oder wäre es besser, eine C-Funktion zu implementieren und bei Bedarf std :: function <> zu verwenden?

So wie es jetzt ist, ist std :: set nur ein Container, der sich gut für die Implementierung von set im mathematischen Sinne eignet, aber es ist fast so weit von einer theoretischen Menge entfernt wie std :: vector von einem theoretischen Vektor.

Mike Tyukanov
quelle