Binary Suche auf dem Vektor von structs

Question

Ich habe einen Vektor von Strukturen, die Struktur mit dieser Architektur

struct Main{ 

    int mainID; 
    string mainDIV; 
    string mainNAME; 

} 

ist es möglich, zu verwenden, binäre Suche auf struct enthält? Ich weiß, sie leicht auf Wert verwenden

binary_search(vector.begin() , vector.end() , 5) 

Verwendung Aber ist es eine Möglichkeit, wie Rückruf passieren oder etwas tatsächlich Attribut Struktur zu finden? Ich finde nichts in Bezug auf dieses Thema.

Answer 1

Ja, es ist möglich. Die value, die std::binary_search nimmt, ist nur im Vergleich zu den Elementen des Containers sinnvoll. Im einfachen Fall (wenn Mainoperator< irgendwo unterstützt), würden Sie ein Element des Typs Main als Wert liefern:

// check if this specific Main exists 
bool yes = std::binary_search(v.begin(), v.end(), Main{0, "some", "strings"}); 

// does exactly the same thing as above 
bool yes = std::binary_search(v.begin(), v.end(), Main{0, "some", "strings"} 
    , std::less<Main>{}); 

Wenn es nicht unterstützt operator< (oder Containers wird durch etwas anderes bestellt, zB mainID), dann werden Sie einen Komparator selbst sorgen müssen, dass der Algorithmus verwenden:

// check if there is a Main with mainID 5 
bool yes = std::binary_search(v.begin(), v.end(), 5, 
    [](const Main& element, const int value) { 
     return element.mainID < value; 
    }); 

Answer 2

Sie haben Informationen zu binary_search() zur Verfügung zu stellen, es zu sagen, wie Ihre Objekte zu vergleichen. Die beiden gebräuchlichsten Methoden sind entweder das Hinzufügen eines operator<() zu dem struct, wenn das möglich ist, oder das Bereitstellen einer Hilfsfunktion, die zwei struct s miteinander vergleichen kann.

struct Main { 
    int mainID ; 
    string mainDIV ; 
    string mainNAME ; 
    bool operator<(const Main & other) const 
    { 
    return mainID < other.mainID ; 
    } 
} 

Dies vergleicht sich nur auf mainID, aber man kann es von dort erweitern:

Die erste Form etwa so aussehen würde.

Außerdem lehrt dies nur den Compiler, wie man zwei struct Main vergleicht, während @ Barry's obige Antwort einem int und einem struct Main entspricht. Aber machen wir weiter mit dieser Antwort.

nun den Rekord für 5 zu finden, müssen wir es in eine machen struct Main:

struct Main search_key = { 5 } ; 
bool yes = std::binary_search(v.begin(), v.end(), search_key) ; 

Nun, das ist nicht sehr elegant ist, und außerdem, wenn Sie einen Konstruktor für struct Main (und haven‘ t es in Ihrem Beispiel), das wird nicht einmal funktionieren. Also fügen wir einen weiteren Konstruktor nur für int hinzu.

struct Main 
{ 
    Main(int id, const string & a_div, const string & a_name) : id(id), div(a_div), name(a_name) { } 
    Main(int id) : id(id) { } 
    int id ; 
    string div, name ; 

    bool operator<(const Main &o) const { return id < o.id ; } 
} ; 

Jetzt können wir eine etwas kürzere Form tun:

bool has_3 = std::binary_search(v.begin(), v.end(), Main(3)) ; 

Historische Anmerkung: Bjarne seit geraumer Zeit versucht hat, Standardvergleichsoperatoren in den Standard zu bekommen, aber nicht alle waren darüber begeistert bei den Normentreffen. Ich habe zwar beim letzten Treffen Fortschritte gemacht, und vielleicht wird es irgendwann erscheinen, wenn C++ 17 eine Sache ist.