C++ std::map<std::string, AnyType> find a range of partially matching strings

Question

I have a std::map<std::string, AnyType> with following item keys:

/abc/def/ghi
/abc/def/jkl
/abc/def/mno
/abc/pqr/ghi
/abc/pqr/stw
/abc/xyz/ghi
/abc/xyz/jkl
/abc/xyz/mno
/abc/zzz/mno

is there efficient way to find two iterators that determines upper and lower bounds of the range of keys that partially match with a specified string? For example, the string /abc/x should correspond to two iterators pointing consecutively to: /abc/xyz/ghi and /abc/xyz/mno.

Answer 1

lower_bound with the next string alphabetically is an efficient way to achieve that:

#include <iostream>
#include <map>
#include <string>
#include <limits.h>

int main() {
    const std::map<std::string, int> map{
        {"/abc/def/ghi", 0}, {"/abc/def/jkl", 1}, {"/abc/def/mno", 2},
        {"/abc/pqr/ghi", 3}, {"/abc/pqr/stw", 4}, {"/abc/xyz/ghi", 5},
        {"/abc/xyz/jkl", 6}, {"/abc/xyz/mno", 7}, {"/abc/zzz/mno", 8}};

    std::string pref = "/abc/x";

    const auto beg = map.lower_bound(pref);
    const auto end = map.lower_bound(pref + (char)CHAR_MAX);
    for (auto it = beg; it != end; ++it) {
        std::cout << it->first << " = " << it->second << '\n';
    }
}

Output:

/abc/xyz/ghi = 5
/abc/xyz/jkl = 6
/abc/xyz/mno = 7