std::equal_range Beispiel

C++ Algorithmen

Dieses Beispiel zeigt ein Template, das in einer sortierten Range von Strings die Elemente sucht, die mit den geforderten Anfangsbuchstaben bzw. Anfangsstrings beginnen. Die Klasse benutzt dazu die STL Funktion equal_range aus dem Header <algorithm>. Damit lassen sich bspw. Eingabehilfen realisieren, wie man sie z.B. von bekannten Suchmaschinen kennt:

Für den Vergleich mit Teilstrings wird equal_range ein spezieller Vergleichs Funktor übergeben. Dieser enthält einen mehrfach überladenen () Operator, der "normale" Strings untereinander und Strings mit Teilstrings vergleichen kann. Um Teilstrings von Strings unterscheiden zu können, ist ein struct partial_string definiert. Wichtig für die Funktionsweise von equal_range ist, dass der Container, der die Suchwörter enthält sortiert ist.

#include <array>
#include <algorithm>
#include <iterator>
#include <string>
#include <iostream>


template<typename Iter, typename charT>
class string_match
{
    typedef std::basic_string<charT> string_type;
    typedef const string_type& string_ref;

    // Hilfstyp für Teilstrings
    struct partial_string {
        partial_string(string_ref s) : str(s){}
        string_type str;
    };
    typedef const partial_string& partial_ref;

    // Vergleichs-Funktor
    struct partial_str_less {
        bool operator()(string_ref lhs, string_ref rhs) const
        { return lhs < rhs; }

        bool operator()(string_ref lhs, partial_ref rhs) const
        { return lhs.substr(0,rhs.str.size()) < rhs.str; }

        bool operator()(partial_ref lhs, string_ref rhs) const
        { return lhs.str < rhs.substr(0,lhs.str.size()); }
    };

    Iter m_first;
    Iter m_last;
	
public:
    typedef Iter iterator;

    string_match(Iter first, Iter last)
        :     m_first(first), m_last(last)
    {    }

    std::pair<Iter, Iter> match(string_ref match) const
    {
        return std::equal_range(m_first, m_last,
            partial_string(match), partial_str_less());
    }
 };



int main()
{
    using namespace std;
    typedef tr1::array<string, 8> arr;
    typedef arr::const_iterator Iter;
    typedef string_match<Iter, char> match;

    arr namen = {
        "bjarne", 
        "scott", 
        "herb", 
        "andrei",
        "dave", 
        "andrew", 
        "stan", 
        "steven"};

    // Für equal_range sortieren
    sort(namen.begin(), namen.end());
    
    // Eine string_match Instanz
    match matcher(namen.begin(), namen.end());
	
    cout << "C++ Guru Search Engine 1.0\n"; 
    for(;;){
        string s;
        cout << "\neingabe:";
        cin >> s;
        if (s == "q") break;

        // Suche:
        pair<match::iterator, match::iterator> result =
            matcher.match(s);
            
        // Ausgabe:
        copy(result.first, result.second,
            ostream_iterator<string>(cout,"\n"));
    }

    return 0;
}

Die Ausgabe des Programms könnte z.B. folgendermaßen aussehen:

eingabe:s
scott
stan
steven

eingabe:st
stan
steven

eingabe:ste
steven

Diskussion

Sende ein Kommentar, Frage, Korrekturen, Beschimpfungen...

Name:

Nachricht:

doxapp c++
Zur Übersicht
home