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

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?

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.

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.

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.

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.

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)) ...

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.

Seit c ++ 20,

bool contains( const Key& key ) const

ist verfügbar.

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;

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
}

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.