Dlaczego std :: set nie ma funkcji składowej „zawiera”?

Używam mocno std::set<int>i często po prostu muszę sprawdzić, czy taki zestaw zawiera liczbę, czy nie.

Uznałbym za naturalne napisanie:

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

Ale z powodu braku containsczłonka muszę napisać uciążliwe:

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

lub nie tak oczywiste:

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

Czy istnieje powód takiej decyzji projektowej?

Myślę, że to prawdopodobnie dlatego, że oni próbują zrobić std::seti std::multisetjak najbardziej podobne. (I oczywiście countma sensowne znaczenie std::multiset.)

Osobiście uważam, że to był błąd.

Nie wygląda to tak źle, jeśli udajesz, że countto tylko błąd ortograficzny containsi napiszesz test jako:

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

Jednak nadal jest to wstyd.

Aby móc pisać if (s.contains()), contains()musi zwrócić bool(lub typ do konwersji bool, co jest inną historią), jak binary_searchrobi.

Podstawowym powodem za projekt decyzji nie zrobić to w ten sposób jest to, contains()który zwraca boolbyłoby stracić cenne informacje o tym, gdzie element jest w zbiorze . find()zachowuje i zwraca te informacje w postaci iteratora, dlatego jest lepszym wyborem dla biblioteki ogólnej, takiej jak STL. To zawsze była naczelna zasada Alexa Stiepanowa, jak często wyjaśniał (na przykład tutaj ).

Jeśli chodzi o count()podejście ogólnie, chociaż często jest to dobre obejście, problem polega na tym, że wykonuje więcej pracy niż contains() musiałby zrobić .

Nie oznacza to, że bool contains()nie jest to zbyt przyjemne, a nawet konieczne. Jakiś czas temu prowadziliśmy długą dyskusję na ten sam temat w grupie ISO C ++ Standard - Future Propozycje.

Brakuje go, ponieważ nikt go nie dodał. Nikt go nie dodał, ponieważ kontenery z STL, które stdzawierała biblioteka, zostały zaprojektowane tak, aby były minimalne w interfejsie. (Zauważ, że std::stringnie pochodzi z STL w ten sam sposób).

Jeśli nie masz nic przeciwko dziwnej składni, możesz ją sfałszować:

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

posługiwać się:

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

Zasadniczo możesz pisać metody rozszerzające dla większości stdtypów C ++ przy użyciu tej techniki.

O wiele bardziej sensowne jest po prostu zrobienie tego:

if (some_set.count(some_element)) {
}

ale bawi mnie metoda metody rozszerzania.

Naprawdę smutne jest to, że pisanie efektywnego containsmoże być szybsze na jednym elemencie multimaplub multiset, ponieważ muszą tylko znaleźć jeden element, podczas gdy countmuszą znaleźć każdy z nich i policzyć .

Multiset zawierający 1 miliard kopii 7 (wiesz, na wypadek, gdybyś się skończył) może mieć naprawdę wolny .count(7), ale może mieć bardzo szybki contains(7).

Dzięki powyższej metodzie rozszerzenia możemy przyspieszyć to w tym przypadku, używając lower_bound, porównując end, a następnie porównując z elementem. Zrobienie tego dla nieuporządkowanego miauczenia, jak również zamówionego miauczenia, wymagałoby jednak fantazyjnych SFINAE lub przeciążeń specyficznych dla kontenera.

Patrzysz na konkretny przypadek i nie widzisz większego obrazu. Jak stwierdzono w dokumentacji, std::set spełnia wymagania koncepcji AssociativeContainer . W przypadku tej koncepcji nie ma sensu mieć containsmetody, ponieważ jest ona prawie bezużyteczna dla std::multiseti std::multimap, ale countdziała dobrze dla wszystkich. Choć metoda containsmoże być dodany jako alias countdla std::set, std::mapi ich zakodowane wersje (jak lengthna size()w std::string), ale wygląda jak twórców bibliotek nie widzi realnej potrzeby.

Chociaż nie wiem, dlaczego std::setnie ma, containsale countktóre tylko zwraca, 0lub 1, możesz napisać funkcję containspomocniczą opartą na szablonach w następujący sposób:

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

I użyj tego w ten sposób:

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

Prawdziwy powód setjest dla mnie tajemnicą, ale jednym z możliwych wyjaśnień tego samego projektu w programie mapmoże być zapobieganie przypadkowemu pisaniu nieefektywnego kodu:

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

Co spowodowałoby dwa mapwyszukiwania.

Zamiast tego jesteś zmuszony uzyskać iterator. To daje ci mentalną wskazówkę, że powinieneś ponownie użyć iteratora:

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

który zużywa tylko jedno mapwyszukiwanie.

Kiedy zdamy sobie z tego sprawę seti mapjesteśmy stworzeni z tego samego ciała, możemy zastosować tę zasadę również do set. Oznacza to, że jeśli chcemy działać na elemencie settylko wtedy, gdy jest obecny w set, ten projekt może uniemożliwić nam pisanie kodu w następujący sposób:

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

Oczywiście wszystko to jest zwykłą spekulacją.

Ponieważ c ++ 20,

bool contains( const Key& key ) const

jest dostępny.

A co z 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;

zawiera () musi zwrócić wartość bool. Używając kompilatora C ++ 20, otrzymuję następujące dane wyjściowe dla kodu:

#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
}

Innym powodem jest to, że dałoby to programiście fałszywe wrażenie, że std :: set jest zbiorem w sensie matematycznej teorii mnogości. Jeśli to zaimplementują, pojawi się wiele innych pytań: jeśli std :: set zawiera () dla wartości, dlaczego nie ma jej dla innego zestawu? Gdzie są union (), intersection () i inne operacje na zbiorach i predykaty?

Odpowiedź jest oczywiście taka, że ​​niektóre operacje na zbiorach są już zaimplementowane jako funkcje w (std :: set_union () itp.), A inne są tak trywialnie zaimplementowane, jak include (). Funkcje i obiekty funkcji działają lepiej z abstrakcjami matematycznymi niż składowymi obiektów i nie są ograniczone do określonego typu kontenera.

Jeśli ktoś potrzebuje zaimplementować pełną funkcjonalność zestawu matematycznego, ma nie tylko wybór podstawowego kontenera, ale także ma wybór szczegółów implementacji, np. Czy jego funkcja teorii_union () działałaby z niezmiennymi obiektami, lepiej przystosowaną do programowania funkcjonalnego , czy też zmodyfikowałby swoje operandy i oszczędziłby pamięć? Czy byłby zaimplementowany jako obiekt funkcji od samego początku, czy też lepiej byłoby zaimplementować funkcję C i użyć std :: function <> w razie potrzeby?

Tak jak jest teraz, std :: set jest tylko kontenerem, dobrze przystosowanym do implementacji zbioru w sensie matematycznym, ale jest prawie tak daleki od bycia zbiorem teoretycznym jak std :: vector od bycia wektorem teoretycznym.