Wie überprüfe ich, ob sich ein Element in einem std :: set befindet?

328

Wie überprüfen Sie, ob sich ein Element in einer Menge befindet?

Gibt es ein einfacheres Äquivalent zum folgenden Code:

myset.find(x) != myset.end()
Fulmicoton
quelle
4
Der einzige Weg, einfacher zu werden, wäre ein boolesches Prädikat: template <typename T> bool member (T const & item). Und das würde (unter dem Deckmantel) in Bezug auf die Zeile implementiert, nach der Sie fragen.
Don Wakefield

Antworten:

397

Der typische Weg für Existenz in vielen STL - Containern zu überprüfen , wie std::map, std::set... ist:

const bool is_in = container.find(element) != container.end();
entspannen
quelle
24
Dies ist spezifisch für Sets und Karten. Vektoren, Listen usw. haben keine Funktion zum Suchen von Elementen.
Wilhelmtell
8
IMO mit count () ist besser, weil es einfach kürzer ist und sich in bool umwandelt, wie in der Antwort von Pieter angegeben. Ich verstehe nicht, warum diese Antwort akzeptiert wurde und so viele Punkte ...
27гњен Шобајић
4
Der Vollständigkeit halber können Vektoren / Listen std :: find verwenden : std::find(container.begin(), container.end(), element) != container.end(); O (N) Problem bleibt natürlich ...
Aconcagua
10
@MichaelMathews Bei Ihrer Variante: if(container.find(foo) == container.end())muss zuerst eine Baumsuche durchgeführt werden, um das Element zu finden. Wenn es nicht gefunden wird, müssen Sie eine zweite Baumsuche durchführen, um die richtige Einfügeposition zu finden. Die ursprüngliche Variante if(container.insert(foo).second) {...}hat den Reiz, dass sie nur eine einzige Baumsuche benötigt ...
Aconcagua
23
Es gibt einen set.contains(x), der im C ++ 20-Standard einen Bool zurückgibt. Ich weiß nicht, warum wir bis 2020 gebraucht haben, um das zu erreichen.
Gremwell
213

Eine andere Möglichkeit, einfach festzustellen, ob ein Element vorhanden ist, besteht darin, das zu überprüfen count()

if (myset.count(x)) {
   // x is in the set, count is 1
} else {
   // count zero, i.e. x not in the set
}

Meistens benötige ich jedoch Zugriff auf das Element, wo immer ich es überprüfe.

Also müsste ich sowieso den Iterator finden. Dann ist es natürlich besser, es einfach zu vergleichen end.

set< X >::iterator it = myset.find(x);
if (it != myset.end()) {
   // do something with *it
}

C ++ 20

In C ++ 20 erhält set eine containsFunktion, sodass Folgendes möglich wird: https://stackoverflow.com/a/54197839/895245

if (myset.contains(x)) {
  // x is in the set
} else {
  // no x 
}
Pieter
quelle
101
Beachten Sie, dass die Verwendung von count()anstelle von find()niemals besser, aber möglicherweise schlechter ist. Dies liegt daran find(), dass nach der ersten Übereinstimmung count()immer alle Elemente durchlaufen werden.
Frerich Raabe
34
@Frerich das ist nur relevant für multisetund multimapich dachte? Immer noch gut darauf hinzuweisen :)
Pieter
83
std :: set wird normalerweise mit einer geordneten Baumstruktur implementiert, sodass count () und find () beide O (logn) haben. Weder wird über alle Elemente in der Menge iterieren.
Alan
14
@FrerichRaabe - Bist du sicher? Da es nur möglich ist set, ein übereinstimmendes Mitglied zu enthalten, würde die Funktion in diesem Fall nicht so implementiert, dass sie nach dem Auffinden des ersten Elements stoppt, wie Pieter betont? Nützliche Antwort auf jeden Fall!
Dan Nissenbaum
14
@DanNissenbaum Ja, Sie haben genau Recht (und + Peter und + Alan auch): Für std :: set sind die beiden Funktionen hinsichtlich der Leistung gleichwertig. Obwohl der erste Teil meines Kommentars (der count()niemals schneller ist als find()) immer noch gültig ist, gilt der zweite Teil in der Tat nicht für std::set. Ich denke jedoch, dass ein anderes Argument dafür find()angeführt werden kann : Es ist aussagekräftiger, dh es wird betont, dass Sie versuchen, ein Element zu finden, anstatt die Anzahl der Vorkommen zu zählen.
Frerich Raabe
42

Um dies zu verdeutlichen, liegt der Grund dafür, dass es contains()in diesen Containertypen kein Mitglied wie dieses gibt, darin, dass Sie dadurch ineffizienten Code schreiben können. Eine solche Methode würde wahrscheinlich nur this->find(key) != this->end()intern durchgeführt, aber überlegen Sie, was Sie tun, wenn der Schlüssel tatsächlich vorhanden ist. In den meisten Fällen möchten Sie dann das Element abrufen und etwas damit tun. Dies bedeutet, dass Sie eine Sekunde ausführen müssen find(), was ineffizient ist. Es ist besser, find direkt zu verwenden, damit Sie Ihr Ergebnis wie folgt zwischenspeichern können:

auto it = myContainer.find(key);
if (it != myContainer.end())
{
    // Do something with it, no more lookup needed.
}
else
{
    // Key was not present.
}

Wenn Sie sich nicht für Effizienz interessieren, können Sie natürlich immer Ihre eigenen rollen, aber in diesem Fall sollten Sie wahrscheinlich nicht C ++ verwenden ...;)

Tim
quelle
44
Was ist mit Sets? Normalerweise haben Sie das Element bereits, möchten aber nur überprüfen, ob es vorhanden ist.
Elazar Leibovich
8
Haben Sie einen Hinweis darauf, ob dies der eigentliche Grund ist, warum eine solche Methode / Funktion nicht in der stl enthalten ist, oder ist es nur Ihre fundierte Vermutung?
Fabio A.
3
@ FabioA. Es ist meine fundierte Vermutung.
Tim
1
@Adhemar, Konsistenz ist nicht gerade die starke Seite von STL ... ( list::remove, remove(makes_sense_only_for_vector, iterators)...)
Elazar Leibovich
3
Es macht für mich keinen Sinn, eine Funktion nicht einzuschließen, da jemand sie möglicherweise falsch verwendet, wenn er nicht weiß, was er tut. Programmierung ist für Leute, die für sich selbst denken können und für ihren Code und seine Leistung verantwortlich sind
slawekwin
13

In C ++ 20 bekommen wir endlich die std::set::containsMethode.

#include <iostream>
#include <string>
#include <set>

int main()
{
    std::set<std::string> example = {"Do", "not", "panic", "!!!"};

    if(example.contains("panic")) {
        std::cout << "Found\n";
    } else {
        std::cout << "Not found\n";
    }
}
Denis Sablukov
quelle
6

Wenn Sie eine containsFunktion hinzufügen möchten, sieht diese möglicherweise folgendermaßen aus:

#include <algorithm>
#include <iterator>

template<class TInputIterator, class T> inline
bool contains(TInputIterator first, TInputIterator last, const T& value)
{
    return std::find(first, last, value) != last;
}

template<class TContainer, class T> inline
bool contains(const TContainer& container, const T& value)
{
    // This works with more containers but requires std::begin and std::end
    // from C++0x, which you can get either:
    //  1. By using a C++0x compiler or
    //  2. Including the utility functions below.
    return contains(std::begin(container), std::end(container), value);

    // This works pre-C++0x (and without the utility functions below, but doesn't
    // work for fixed-length arrays.
    //return contains(container.begin(), container.end(), value);
}

template<class T> inline
bool contains(const std::set<T>& container, const T& value)
{
    return container.find(value) != container.end();
}

Dies funktioniert mit std::setanderen STL-Containern und sogar Arrays mit fester Länge:

void test()
{
    std::set<int> set;
    set.insert(1);
    set.insert(4);
    assert(!contains(set, 3));

    int set2[] = { 1, 2, 3 };
    assert(contains(set2, 3));
}

Bearbeiten:

Wie in den Kommentaren erwähnt, habe ich ungewollt eine neue Funktion in C ++ 0x ( std::beginund std::end) verwendet. Hier ist die nahezu triviale Implementierung von VS2010:

namespace std {

template<class _Container> inline
    typename _Container::iterator begin(_Container& _Cont)
    { // get beginning of sequence
    return (_Cont.begin());
    }

template<class _Container> inline
    typename _Container::const_iterator begin(const _Container& _Cont)
    { // get beginning of sequence
    return (_Cont.begin());
    }

template<class _Container> inline
    typename _Container::iterator end(_Container& _Cont)
    { // get end of sequence
    return (_Cont.end());
    }

template<class _Container> inline
    typename _Container::const_iterator end(const _Container& _Cont)
    { // get end of sequence
    return (_Cont.end());
    }

template<class _Ty,
    size_t _Size> inline
    _Ty *begin(_Ty (&_Array)[_Size])
    { // get beginning of array
    return (&_Array[0]);
    }

template<class _Ty,
    size_t _Size> inline
    _Ty *end(_Ty (&_Array)[_Size])
    { // get end of array
    return (&_Array[0] + _Size);
    }

}
Sam Harwell
quelle
1
@Adhemar, es tatsächlich war ineffizient, aber überhaupt nicht aus dem Grund , die Sie erwähnt.
Sam Harwell
@Paul: Stellen Sie sicher, dass Sie die Spezialisierung für angeben std::set, und denken Sie daran, dass dies nur dann angemessen ist, wenn das einzige, was Sie wissen müssen, die Existenz ist.
Sam Harwell
@ 280Z28: std :: begin (Container)? Welcher STL-Standard ist das? Es kompiliert nicht auf meinem gcc.
Stefaanv
@stefannv: heh, es ist neu für C ++ 0x. Ich habe die Implementierung von meinem Compiler oben hinzugefügt.
Sam Harwell
2
@Adhemar: Wenn Sie wissen, dass die Menge einen Wert enthält, dann haben Sie bereits den Wert. Der einzige Grund, warum Sie den Iterator benötigen, besteht darin, das Element aus der Menge zu löschen. Wenn alles was Sie brauchen , ist zu wissen , ob eine Sammlung einen Wert enthält, dann ist diese Lösung nicht weniger effizient als jede andere Lösung.
Sam Harwell
4

Sie können beim Einfügen des Elements auch überprüfen, ob ein Element festgelegt ist oder nicht. Die Einzelelementversion gibt ein Paar zurück, wobei das Element pair :: first auf einen Iterator gesetzt ist, der entweder auf das neu eingefügte Element oder auf das entsprechende Element zeigt, das bereits in der Menge enthalten ist. Das pair :: second-Element im Paar wird auf true gesetzt, wenn ein neues Element eingefügt wurde, oder auf false, wenn bereits ein gleichwertiges Element vorhanden war.

Zum Beispiel: Angenommen, die Menge hat bereits 20 als Element.

 std::set<int> myset;
 std::set<int>::iterator it;
 std::pair<std::set<int>::iterator,bool> ret;

 ret=myset.insert(20);
 if(ret.second==false)
 {
     //do nothing

 }
 else
 {
    //do something
 }

 it=ret.first //points to element 20 already in set.

Wenn das Element neu eingefügt wird, zeigt pair :: first auf die Position des neuen Elements in set.

Prashant Shubham
quelle
2

Schreibe dein Eigenes:

template<class T>
bool checkElementIsInSet(const T& elem, const std::set<T>& container)
{
  return container.find(elem) != container.end();
}
stefaanv
quelle
4
gerade getan: Vorlage <Klasse T> statisches Inline-Bool enthält (const std :: set <T> & S, T x) {return (S.find (x)! = S.end ()); }
Fulmicoton
4
@paul erstellt keine statischen globalen Funktionen. Platzieren Sie Ihre Funktion stattdessen in einem anonymen Namespace: Auf diese Weise können Sie in C ++ Funktionen erstellen, die nicht mit anderen Kompilierungseinheiten verknüpft werden. Außerdem sollte Ihr T-Parameter eine Konstantenreferenz sein, um die Konstantenkorrektheit und die Effizienz zu gewährleisten.
Wilhelmtell
-1: nicht als Templat und nicht überhaupt in STL - Stil. Dies ist in Ordnung, wenn Sie STL nicht verwenden. Wenn Sie jedoch STL verwenden, sollten Sie zumindest versuchen, die Standards zu befolgen.
Sam Harwell
1
@ 280Z28: Es tut mir leid, dass mein Code nicht Ihren Standards entspricht. Ich habe nur gezeigt, dass Sie Ihren eigenen schreiben können, wenn Ihnen die STL-Oberfläche nicht gefällt. Herrgott, nicht als Vorlage? Wie viel Vorlage muss es sein? Dein Beispiel sieht gut aus, das heißt nicht, dass meins schlecht ist. Es konzentriert sich nur mehr auf das Set, wie es vom OP gefordert wurde.
Stefaanv
1
@ 280Z28: Ich habe nur einen Punkt gemacht. Ich dachte, die Leute wären intelligent genug, um sich ein Bild zu machen.
Stefaanv
2

ich benutze

if(!my_set.count(that_element)) //Element is present...
;

Aber es ist nicht so effizient wie

if(my_set.find(that_element)!=my_set.end()) ....;

Meine Version spart nur Zeit beim Schreiben des Codes. Ich bevorzuge es auf diese Weise für wettbewerbsfähige Codierung.

Manas Bondale
quelle
Ja count(). Jeder, der nicht verstehen kann, dass eine in einem Booleschen Ausdruck verwendete Ganzzahl-Rückgabefunktion auf Nicht-Null prüft, wird im großen Meer der C / C ++ - Redewendungen viele, viele andere Probleme haben. Und wie oben erwähnt, sollte es für Sets wirklich genauso effizient sein, was die Frage war.
Ron Burk
0

Ich konnte eine allgemeine containsFunktion für std::listund schreiben std::vector,

template<typename T>
bool contains( const list<T>& container, const T& elt )
{
  return find( container.begin(), container.end(), elt ) != container.end() ;
}

template<typename T>
bool contains( const vector<T>& container, const T& elt )
{
  return find( container.begin(), container.end(), elt ) != container.end() ;
}

// use:
if( contains( yourList, itemInList ) ) // then do something

Dies bereinigt die Syntax ein wenig.

Aber ich konnte nicht Template Template Parameter Magic verwenden , um diese Arbeit beliebige STL-Container zu machen.

// NOT WORKING:
template<template<class> class STLContainer, class T>
bool contains( STLContainer<T> container, T elt )
{
  return find( container.begin(), container.end(), elt ) != container.end() ;
}

Alle Kommentare zur Verbesserung der letzten Antwort wären nett.

Bobobobo
quelle
Entschuldigung, ich kann nicht wirklich Blockcode in Kommentar schreiben, aber was ist mit template<typename CONTAINER, typename CONTAINEE> bool contains(const CONTAINER& container, const CONTAINEE& needle) { return find(container.begin(), container.end(), needle) != container.end();
Fulmicoton
Es funktioniert nicht, da std :: vector einen zusätzlichen Allokator als Vorlagenargument benötigt und std :: set einen Allokator und ein weniger Vorlagenargument benötigt. Diese Zeilen funktionieren wie folgt: template <template <class, class> Klasse STLContainer, Klasse T, Klasse A> bool enthält (STLContainer <T, A> Container, T elt) {return find (container.begin (), container.end ( ), elt)! = container.end (); } template <template <Klasse, Klasse, Klasse> Klasse STLContainer, Klasse T, Klasse L, Klasse A> Bool enthält (STLContainer <T, A, L> Container, T elt) {return find (container.begin (), Container .end (), elt)! = container.end (); }
tgmath
0

// allgemeine Syntax

       set<int>::iterator ii = find(set1.begin(),set1.end(),"element to be searched");

/ * im folgenden Code versuche ich, Element 4 in und int set zu finden, ob es vorhanden ist oder nicht * /

set<int>::iterator ii = find(set1.begin(),set1.end(),4);
 if(ii!=set1.end())
 {
    cout<<"element found";
    set1.erase(ii);// in case you want to erase that element from set.
 }
Sanjeev
quelle