STL: binary_search Verständnisproblem

robert.S

Hallo,

ich setze mich gerade mit der STL auseinander und scheitere am binary_search.

Ich habe folgende Klasse:

class data
{
        // nur wesentliche Bestandteile
    public:

        bool operator <(const data compare) const;

    protected:

        std::string str;

};

In ein multiset füge ich nun Objekte der Klasse data mit insert ein.

values.insert(data("Test"));

Soweit funktioniert das auch. Nun wollte ich auf mein multiset values binary_search anwenden:

std::binary_search( values.begin(), values.end(), "Test" )

Bekomme aber folgenden Fehler:

no match for 'operator<' in '(&__middle)->std::_Rb_tree_const_iterator<_Tp>::operator* [with _Tp = data]() < __val'
data.h:15: note: candidates are: bool data::operator<(data) const

Liegt ja offensichtlich an meinem < Operator. Aber ich habe bisher nicht rausfinden können was genau...

CStoll

Zeig doch mal die Konstruktoren der Data-Klasse. (btw, funktioniert es denn, wenn du binary_search(...,data("Test")) schreibst?)

PS: binary_search() auf den assiziativen Containern ist nicht unbedingt besonders schnell - da solltest du lieber die Methode find() verwenden.

Airdamn

if(std::binary_search(values.begin(), values.end(), data("Test")))
// gefunden

robert.S

CStoll schrieb:

(btw, funktioniert es denn, wenn du binary_search(...,data("Test")) schreibst?)

Airdamn schrieb:

if(std::binary_search(values.begin(), values.end(), data("Test")))
// gefunden

Danke euch. Damit klappt es.

CStoll schrieb:

PS: binary_search() auf den assiziativen Containern ist nicht unbedingt besonders schnell - da solltest du lieber die Methode find() verwenden.

Echt? Ich dachte bei sortierten Daten ist eine Binärsuche besonders schnell. Arbeitet find nicht sequentiell?

camper

Airdamn schrieb:

if(std::binary_search(values.begin(), values.end(), data("Test")))
// gefunden

Nutze lieber die Memberfunktion von multiset (std::binary_search ist zudem möglicherweise ineffizient):

if ( values.find( data("Test") ) != values.end() )
// ...

dein operator< sollte als zweiten Parameter eine Referenz auf const Data haben.

binary_search ist nur bei schnell hinsichtlich der Anzahl der Vergleiche bei random access Iteratoren, da dies logarithmisch von der Anzahl der Elemente abhängt. Bei nicht-random-access-Iteratoren ist die Komplexität dagegen linear - natürlich könnte eine Implementation u.U. sehr schlau sein, und beim Aufuruf erkennen, dass die Iteratoren aus einem set stammen und die entsprechende Memberfunktion aufrufen - darauf verlassen sollte man sich allerdings nicht (zumal das voraussetzt, dass die Iteratoren wissen, zu welchem Container sie gehören).

CStoll

robert.S schrieb:

CStoll schrieb:

PS: binary_search() auf den assiziativen Containern ist nicht unbedingt besonders schnell - da solltest du lieber die Methode find() verwenden.

Echt? Ich dachte bei sortierten Daten ist eine Binärsuche besonders schnell. Arbeitet find nicht sequentiell?

Binäre Suche ist - bezogen auf die Anzahl Vergleiche - auch recht schnell. Allerdings springt sie über große Distanzen durch den durchsuchten Bereich und benötigt deshalb Random-Access-Iteratoren, um diese Geschwindigkeit ausschöpfen zu können. Bei bidirektionalen Iteratoren mußt du per advance() die jeweils richtige Position anlaufen - und das bremst das gesamte Verfahren aus.
(set::find() kann sich dagegen durch die interne Baumstruktur durchhangeln)