STL Map - efficiently search for Prefix

03 May, 2013 - 1 min read

For prefix searching, you can use lower_bound to search for "Marl".

    map&lt;string,string&gt;::const_iterator m = tMap.lower_bound("Marl");
    cerr &lt;&lt; (*m).second &lt;&lt; endl;

This does not work for non-prefix substrings: in the general case, searching a map is not much different from searching other containers.

#include &lt;iostream&gt;
#include &lt;map&gt;
#include &lt;string&gt;
#include &lt;algorithm&gt;
using namespace std;

typedef map&lt;string, string&gt; TStrStrMap;
typedef pair&lt;string, string&gt; TStrStrPair;

TStrStrMap::const_iterator FindPrefix(const TStrStrMap&amp; map, const string&amp; search_for) {
    TStrStrMap::const_iterator i = map.lower_bound(search_for);
    if (i != map.end()) {
        const string&amp; key = i-&gt;first;
        if (key.compare(0, search_for.size(), search_for) == 0) // Really a prefix?
            return i;
    }
    return map.end();
}

void Test(const TStrStrMap&amp; map, const string&amp; search_for) {
    cout &lt;&lt; search_for;
    auto i = FindPrefix(map, search_for);
    if (i != map.end())
        cout &lt;&lt; '\t' &lt;&lt; i-&gt;first &lt;&lt; ", " &lt;&lt; i-&gt;second;
    cout &lt;&lt; endl;
}

int main(int argc, char *argv[])
{
    TStrStrMap tMap;

    tMap.insert(TStrStrPair("John", "AA"));
    tMap.insert(TStrStrPair("Mary", "BBB"));
    tMap.insert(TStrStrPair("Mother", "A"));
    tMap.insert(TStrStrPair("Marlon", "C"));

    Test(tMap, "Marl");
    Test(tMap, "Mo");
    Test(tMap, "ther");
    Test(tMap, "Mad");
    Test(tMap, "Mom");
    Test(tMap, "Perr");
    Test(tMap, "Jo");

    return 0;
}

This prints:

Marl    Marlon, C
Mo      Mother, A
ther
Mad
Mom
Perr
Jo      John, AA

End