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.

IIUC, /abc/y would be inserted between /abc/xyz/mno and /abc/zzz/mno, and that insertion point is the exact end of your range? — MSalters
– MSalters, Commented Jan 31 at 14:55
Question is extremely vague. Please try provide more details, describe a problem which your code should solve. For me using lower_bound looks like just 30% of problem solution. — Marek R
– Marek R, Commented Jan 31 at 14:55
Use lower_bound on /abc/x and /abc/x\xFF (this way you don't need to figure out what character alphabetically follows the last character of the string; which is easy with x but may be tricky with, say, z). — Igor Tandetnik
– Igor Tandetnik, Commented Jan 31 at 14:56
@IgorTandetnik: Depending on CHAR_MIN/CHAR_MAX, \xFF comes before or after x. If it's -1 (char is signed) that won't work. — MSalters
– MSalters, Commented Jan 31 at 15:50

Aykhan Hagverdili · Accepted Answer · 2025-01-31 16:30:57Z

6

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

edited Jan 31 at 16:30

answered Jan 31 at 14:56

Aykhan Hagverdili

30.5k6 gold badges53 silver badges108 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

j6t Jan 31 at 18:01

The second lower_bound with the appended CHAR_MAX will do the right thing only if no string with that prefix is present in the map.

Aykhan Hagverdili Jan 31 at 18:16

@j6t You can code it more carefully to take that into account, but that edge case is not important for OP's use case.

Collectives™ on Stack Overflow

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

1 Answer 1

2 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Related