Beschreibung des Problems:
Betrachten Sie eine Struktur mit einer std::string name Mitglied. Nehmen wir zur Verdeutlichung an, dass es sich um ein struct Human die Informationen über Personen darstellen. Neben der name es kann auch viele andere Datenelemente haben.
Es soll ein Container vorhanden sein std::vector<Human> vec wobei die Objekte bereits sortiert sind nach name . Zur Verdeutlichung sei angenommen, dass alle Namen eindeutig sind.
Das Problem ist : mit einer Zeichenkette nameToFind herausfinden, ob ein Element mit diesem Namen im Array existiert.
Lösung und meine Fortschritte:
Die offensichtliche und natürliche Lösung scheint die Durchführung einer binären Suche unter Verwendung der std::binary_search Funktion. Es gibt jedoch ein Problem: Der Typ des gesuchten Elements ( std::string ) unterscheidet sich vom Typ der Elemente im Container ( Human ), und std::binary_search benötigt eine Regel zum Vergleich dieser Elemente. Ich habe versucht, dieses Problem auf drei Arten zu lösen, die im Folgenden beschrieben werden. Die ersten beiden dienen nur zur Veranschaulichung der Entwicklung meiner Lösung und der Probleme, auf die ich gestoßen bin. Meine Hauptfrage bezieht sich auf den dritten Weg.
Versuch 1: umwandeln std::string a Human .
Schreiben Sie eine Vergleichsfunktion:
bool compareHumansByNames( const Human& lhs, const Human& rhs )
{
return lhs.name < rhs.name;
}Fügen Sie dann einen Konstruktor hinzu, der eine Human Objekt aus std::string :
struct Human
{
Human( const std::string& s );
//... other methods
std::string name;
//... other members
};und verwenden Sie die binary_search in folgender Form:
std::binary_search( vec.begin(), vec.end(), nameToFind, compareHumansByNames );Scheint zu funktionieren, aber es gibt zwei große Probleme:
Erstens, wie man andere Datenelemente initialisiert, aber Human::name Das Setzen von magischen Werten kann zur Erzeugung eines Objekts führen, das semantisch illegal ist.
Zweitens müssen wir diesen Konstruktor als nicht explicit um implizite Konvertierungen während des Algorithmus zu ermöglichen. Die negativen Folgen dieser Vorgehensweise sind bekannt.
Außerdem ist eine solche vorübergehende Human Objekt wird bei jeder Iteration neu erstellt, was sich als recht teuer erweisen kann.
Versuch 2: umwandeln Human a std::string .
Wir können versuchen, eine operator string () zum Human Klasse, die ihre name und verwenden Sie dann den Vergleich für zwei std::string s. Dieser Ansatz ist jedoch auch aus folgenden Gründen ungünstig:
Erstens wird der Code wegen des besprochenen Problems nicht sofort kompiliert aquí . Wir müssen noch etwas mehr tun, damit der Compiler die entsprechenden operator < .
Zweitens, was bedeutet "einen Menschen in einen String umwandeln"? Das Vorhandensein einer solchen Konvertierung kann zu einer semantisch falschen Verwendung der Klasse führen Human was unerwünscht ist.
Versuch 3: Vergleich ohne Umrechnungen.
Die beste Lösung, die ich bisher gefunden habe, ist die Erstellung einer
struct Comparator
{
bool operator() ( const Human& lhs, const std::string& rhs )
{
return lhs.name < rhs;
}
bool operator() ( const std::string& lhs, const Human& rhs )
{
return lhs < rhs.name;
}
};und die binäre Suche als
binary_search( vec.begin(), vec.end(), nameToFind, Comparator() );Dies kompiliert und wird korrekt ausgeführt, alles scheint in Ordnung zu sein, aber hier beginnt der interessante Teil:
Werfen Sie einen Blick auf http://www.sgi.com/tech/stl/binary_search.html . Hier heißt es: " ForwardIterator ist der Werttyp denselben Typ wie T . ". Ziemlich verwirrende Einschränkung, und meine letzte Lösung bricht sie. Schauen wir mal, was der C++-Standard dazu sagt:
25.3.3.4 binäre_Suche
template<class ForwardIterator, class T>
bool binary_search(ForwardIterator first, ForwardIterator last,
const T& value);
template<class ForwardIterator, class T, class Compare>
bool binary_search(ForwardIterator first, ForwardIterator last,
const T& value, Compare comp);Erfordert: Der Typ T ist LessThanComparable (20.1.2).
Es wird nichts ausdrücklich gesagt über ForwardIterator Typs. Aber in der Definition von LessThanComparable gegeben in 20.1.2 es wird über den Vergleich von zwei Elementen von der gleichen Art . Und hier ist das, was ich nicht verstehe. Bedeutet es tatsächlich, dass die Typ des gesuchten Objekts とのことです。 Typ der Objekte des Containers doit gleich sein, und meine Lösung bricht diese Einschränkung ? Oder bezieht sie sich nicht auf den Fall, dass die comp Komparator verwendet wird, und zwar nur dann, wenn der Standard operator < zum Vergleich herangezogen wird? Im ersten Fall bin ich verwirrt, wie man std::binary_search um dies zu lösen, ohne auf die oben genannten Probleme zu stoßen.
Vielen Dank im Voraus für Ihre Hilfe und dass Sie sich die Zeit genommen haben, meine Frage zu lesen.
Nota: Ich verstehe, dass das Schreiben einer binären Suche von Hand keine Zeit in Anspruch nimmt und das Problem sofort lösen wird, aber um das Rad nicht neu zu erfinden, möchte ich std::binary_search verwenden. Außerdem ist es für mich sehr interessant, herauszufinden, ob es eine solche Einschränkung gemäß dem Standard gibt.
