binary_search() mit eigener Vergleichsroutine

Hallo

Ich habe einen vector<string> und möchte diesen mittels binary_search() und einer eingenen Vergleichsroutine durchsuchen lassen, also eigentlich sollen bei den Strings jeweils nur die ersten 32 Zeichen verglichen werden.

Ich weiß, dass ich es so aufrufen muss:

binary_search(svec.begin(), svec.end(), str, MeineVergleichsRoutine);

Nur leider weiß ich nicht, wie "MeineVergleichsRoutine" genau aussehen muss und wie ich diese am besten implementiere könnte.

Ich danke schonmal

Nexus

Du hast dazu zwei Möglichkeiten zur Verfügung:

1. Funktionszeiger
Du definierst eine Funktion mit zwei Parametern, die zwei Elemente vergleicht.

bool CompareFunction(const std::string& Left, const std::string& Right)
{
    return Left.size() < Right.size(); // halt dein Kriterium
}

Du rufst binary_search() mit einer der folgenden Zeilen auf:

std::binary_search(svec.begin(), svec.end(), str, CompareFunction);
std::binary_search(svec.begin(), svec.end(), str, &CompareFunction);

2. Funktor
Du schreibst eine Klasse, die den operator() überlädt. Damit bist du generell flexibler, da du auch noch Argumente an den Konstruktor übergeben kannst. Man nennt Objekte dieser Klasse Funktoren oder Funktionsobjekte, da sie sich wie Funktionen verhalten.

struct CompareFunctor
{
    // Überladener ()-Operator; ist gleich wie obige Funktion definiert
    bool operator() (const std::string& Left, const std::string& Right);
};

Der Aufruf sieht dann so aus:

std::binary_search(svec.begin(), svec.end(), str, CompareFunctor());

Wie gesagt kann man in der Klasse noch Membervariablen haben, die für zusätzliche Spezifizierung des Kriteriums vorhanden sind. Beispielsweise kann man einen CompareFunctor -Konstruktor mit einem int als Parameter definieren und diesen int im operator() verwenden. Dann würde der Aufruf folgendermassen aussehen:

std::binary_search(svec.begin(), svec.end(), str, CompareFunctor(42));

super, Vielen Dank für die Antwort.

Habe jetzt mal so einen Funktionszeiger geschrieben.
Um es testen zu können, müsste ich jetzt wissen, welches Element genau gefunden wurde.
Also nicht den String, sondern den Index des Elements.

Kann man da irgendwie rankommen?

Nexus

mettis schrieb:

Kann man da irgendwie rankommen?

Mit std::binary_search() wird das schwierig, da nur ein Wahrheitswert zurückgegeben wird (ob das gesuchte Element vorkommt oder nicht).

Vielleicht kann dir std::find() helfen, das liefert einen Iterator. Dann kannst du mit std::distance() den Abstand vom Anfang des Vektors messen und erhältst dann den Index:

std::vector<int> Vec;
// Vec füllen
std::vector<int>::iterator Iter = std::find(Vec.begin(), Vec.end(), Elem);
int Index = std::distance(Vec.begin(), Iter);

Statt std::distance() kannst du bei Random-Access-Iteratoren auch operator- verwenden:

int Index = Iter - Vec.begin();

Dravere

Wenn die Liste sortiert ist, kannst du statt std::binary_search , ein std::lower_bound anwenden:
http://www.cplusplus.com/reference/algorithm/lower_bound.html

Grüssli

Dravere schrieb:

Wenn die Liste sortiert ist, kannst du statt std::binary_search , ein std::lower_bound anwenden:
http://www.cplusplus.com/reference/algorithm/lower_bound.html

Grüssli

Das wäre klasse, hast du vll. ein kleines Beispiel dafür, verstehe diese Funktion jetzt irgendwie nicht ganz, die liefert bei mir nur komische Werte.

Ich meine ein Beispiel womit ich die ersten 32 Zeichen vergleichen kann und dann den Index des Elements bekomme, das Beispiel auf der Seite hilft mir nicht so weiter.

Nexus

Werde ein bisschen genauer. Die ersten 32 Zeichen entsprechen der Iterator-Range [begin(), begin()+32] , geht das nicht?

Also der (sortierte) Vector enhält Strings, die folgendermaßen aufgebaut sind:
<String mit 32 Zeichen>:<String mit beliebig vielen Zeichen>

Jetzt gibt der Benutzer einen 32 stelligen String ein und der Vector soll danach durchsucht werden (und beim durchsuchen sollen natürlich nur jeweils die ersten 32 Zeichen verglichen werden, da sonst ja niemals etwas gefunden wird) und wenn er etwas gefunden hat, soll entweder der String nach dem Doppelpunkt oder eben beides ausgegeben werden, das ist egal.

Und das ganze soll möglichst schnell gehen, weshalb ich auch gerne auf find() verzichten möchte, da die Liste ja eh sortiert ist.

Ich hoffe, jemand hat das verstanden und kann mir helfen.

pumuckl

schau dir mal die string-methoden an, man kann sehr wohl vergleiche mit substrings etc. machen

pumuckl schrieb:

schau dir mal die string-methoden an, man kann sehr wohl vergleiche mit substrings etc. machen

Ja, das weiß ich, aber das Problem ist ja, dass ich, wenn ich mit binary_search() den 32 -stelligen String gefunden haben, ja nicht mehr an den Index des Elements bzw. an den String komme, der nach dem Doppelpunkt steht.