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

103

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?

Jabberwocky
źródło
7
Większość bibliotek standardowych współpracuje z iteratorami, więc normalnie można się spodziewać funkcji zwracających iteratory. Nie jest jednak trudno napisać funkcję, która to odciągnie. Najprawdopodobniej kompilator go wstawi, ponieważ powinien to być tylko wiersz lub dwie linie kodu, a uzyskasz taką samą wydajność.
NathanOliver
3
Innym (bardziej fundamentalnym) problemem związanym z tym count()podejściem jest to, że wykonuje ono więcej pracy, niż countains()byłoby to konieczne.
Leo Heinsaar
11
Fundamentalny powód za tym jest to, że projekt decyzji contains(), która 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 nie znaczy, że bool contains()nie jest to zbyt miłe w posiadaniu ani nawet konieczne).
Leo Heinsaar
3
Łatwo jest napisać contains(set, element)darmową funkcję, korzystając z publicznego interfejsu zestawu. Dlatego interfejs zestawu jest funkcjonalnie kompletny; dodanie wygodnej metody po prostu zwiększa interfejs bez włączania żadnej dodatkowej funkcji, co nie jest sposobem C ++.
Toby Speight
3
Czy w dzisiejszych czasach wszystko zamykamy? W jaki sposób to pytanie jest „oparte głównie na opiniach”?
Mr. Alien

Odpowiedzi:

148

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.

Martin Bonner wspiera Monikę
źródło
5
Nawiasem mówiąc, jest dokładnie tak samo z mapami i multimapami (co jest równie brzydkie, ale mniej brzydkie niż wszystkie te porównania .end()).
Matteo Italia
8
Alternatywnie, mogli nie widzieć potrzeby dodatkowego członka contains(), ponieważ byłby on zbędny, ponieważ dla każdego std::set<T> si T twynik s.contains(t)jest dokładnie identyczny z wynikiem static_cast<bool>(s.count(t)). Ponieważ użycie wartości w wyrażeniu warunkowym mogłoby niejawnie rzutować ją na to bool, mogli czuć, że count()służyło to celowi wystarczająco dobrze.
Justin Time - Przywróć Monikę
2
Błąd w pisowni? if (myset.ICanHaz(element)) ...: D
Stéphane Gourichon
3
@MartinBonner Nie ma znaczenia, czy powody pozostawienia go były głupie. Nie ma też znaczenia, czy rozmowa nie była w 100% ostatecznym uzasadnieniem. Twoja odpowiedź to tylko rozsądne przypuszczenie, jak Twoim zdaniem powinno być. Rozmowa i odpowiedź od kogoś, kto nie tylko jest w nią zaangażowany, ale ma za zadanie ją zaproponować (chociaż tego nie zrobił) jest bezsprzecznie bliższa prawdzie niż to przypuszczenie, bez względu na to, jak na to spojrzysz. Jako minimum powinieneś przynajmniej wspomnieć o tym w tej odpowiedzi, to byłaby wielka poprawa i byłaby odpowiedzialna rzecz do zrobienia.
Jason C
2
@JasonC: Czy możesz przejść dalej i edytować sekcję na dole? Naprawdę nie rozumiem, o co ci chodzi, a komentarze prawdopodobnie nie są najlepszym sposobem, aby to wyjaśnić. Dzięki!
Martin Bonner wspiera Monikę
44

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.

Leo Heinsaar
źródło
5
Warto zauważyć, że dyskusja ta zakończyła się niemal jednomyślnością co do tego, że jest to pożądane, i poproszono cię o napisanie propozycji.
PJTraill
@PJTraill True, a powodem, dla którego nie posunąłem się naprzód, jest contains()oczywiście silna interakcja z istniejącymi kontenerami i algorytmami, na które duży wpływ miałyby koncepcje i zakresy - w czasie oczekiwanym w C ++ 17 - i Byłem przekonany (w wyniku dyskusji, a także kilku prywatnych wymian e-mailowych), że lepiej jest zaczekać na nie. Oczywiście w 2015 roku nie było jasne, że ani pojęcia, ani zakresy nie trafią do C ++ 17 (w rzeczywistości były duże nadzieje, że tak się stanie). Nie jestem jednak pewien, czy warto teraz to robić.
Leo Heinsaar
1
Bo std::set(o co chodzi w pytaniu), nie widzę, jak countdziała więcej, niż containsbyłoby to konieczne. Implementacja countis (w przybliżeniu) w glibc return find(value) == end() ? 0 : 1;. Poza szczegółami dotyczącymi operatora trójskładnikowego w porównaniu z samym zwracaniem != end()(co spodziewałbym się, że optymalizator usunie), nie widzę więcej pracy.
Martin Bonner wspiera Monikę
4
„... zawiera (), która zwraca wartość bool, spowoduje utratę cennych informacji o tym, gdzie element znajduje się w kolekcji ” - jeśli użytkownik myset.contains()wywoła (jeśli istnieje), będzie to dość mocna wskazówka, że ​​ta informacja nie jest wartościowa ( do użytkownika w tym kontekście).
Keith Thompson
1
Dlaczego wykonuje count()więcej pracy, niż contains()musiałby zrobić std::set? Jest wyjątkowy, więc count()może być return contains(x) ? 1 : 0;dokładnie taki sam.
Timmmm
22

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.

Yakk - Adam Nevraumont
źródło
2
1 miliard kopii 7? I tutaj pomyślałem, że std::setnie może zawierać duplikatów i dlatego std::set::countzawsze wrócę 0lub 1.
nwp
5
@nwp std::multiset::countcan
milleniumbug
2
@nwp Mój brak backtickswokół słowa „zestaw” wynika z tego, że nie odnoszę się do niego std::setkonkretnie. Żeby poczuć się lepiej, dodam multi
Yakk - Adam Nevraumont
3
Wydaje mi się, że brakuje mi żartu z powodu tego, do czego miało być nawiązaniem miauczenie.
user2357112 obsługuje Monikę
2
@ user2357112 meow to symbol zastępczy dla „set or map”. Zapytaj STL, dlaczego.
Yakk - Adam Nevraumont
12

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.

Slava
źródło
8
Zauważ, że stringto potwór: istniał przed STL, gdzie istniał lengthi wszystkie te metody, które są oparte na indeksach, a następnie został „skonteneryzowany” w celu dopasowania do modelu STL ... bez usuwania istniejących metod ze względu na kompatybilność wsteczną . Zobacz GotW # 84: Monoliths Unstrung => stringnaprawdę narusza zasadę projektowania „minimalnej liczby funkcji składowych ”.
Matthieu M.
5
Ale wtedy pojawia się pytanie: „Dlaczego warto mieć taką koncepcję AssociativeContainer?” - i nie jestem pewien, czy z perspektywy czasu to było.
Martin Bonner wspiera Monikę
24
Pytanie, czy multiset, multimapa lub mapa zawiera coś, ma dla mnie sens. W rzeczywistości containsma taki sam wysiłek na zestawie / mapie, ale można to zrobić szybciej niż countna multiset / multimap.
Yakk - Adam Nevraumont
5
AssociativeContainer nie wymaga, aby klasy nie miały containsmetody.
user2357112 obsługuje Monikę
6
@Slava To tak jakby powiedzieć size()i empty()są duplikatami, ale wiele kontenerów ma jedno i drugie.
Barry
10

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)) ...
rustyx
źródło
3
-1, ponieważ jest containsto po prostu sprzeczne z faktem, że w rzeczywistości metoda istnieje, po prostu została nazwana w głupi sposób.
Matteo Italia
4
"The dą y STL zaoferować minimalny interfejs" Chough std::string kaszel
bolov
6
@bolov: twój punkt widzenia? std.::stringNIE jest częścią STL! Jest częścią standardowej biblioteki i został utworzony z mocą wsteczną ...
MFH
3
@MatteoItalia countmoże działać wolniej, ponieważ efektywnie potrzebuje dwóch sekund, findaby uzyskać początek i koniec zakresu, jeśli kod jest współdzielony multiset.
Mark Ransom
2
OP już wie, że jest zbędny, ale najwyraźniej chce, aby kod został wyraźnie odczytany contains. Nie widzę w tym nic złego. @MarkRansom mała SFINAE ma zapobiec wiązaniu tego szablonu z rzeczami, których nie powinien.
rustyx
7

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

Martin Drozdik
źródło
1
Tak, ale nie dotyczy to zestawów int.
Jabberwocky
7
Tylko że ludzie potrafią po if (myMap.count("Meaning of universe"))prostu dobrze pisać , więc ...?
Barry
@MichaelWalz Ups, masz rację. Zmodyfikowałem odpowiedź tak, aby zawierała również ustawiony przykład. Jednak uzasadnienie dla zestawu int jest dla mnie tajemnicą.
Martin Drozdik
2
To nie może być prawda. Mogą równie łatwo napisać Twój nieefektywny kod containsza pomocą programu count.
Martin Bonner wspiera Monikę
2

Ponieważ c ++ 20,

bool contains( const Key& key ) const

jest dostępny.

Andy
źródło
0

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;
Massimiliano Di Cavio
źródło
To nie zadziała std::unordered_set, ale na std::setto zadziała .
Jabberwocky
To normalne, binary_search działa tylko dla drzew binarnych.
Massimiliano Di Cavio,
0

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
}
bashar
źródło
-1

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.

Mike Tyukanov
źródło