How can I do a binary search on a part of the keys in a std::map?

Question

I have a map of data; the key is std::string. I want to perform a binary search on it, but I cannot just use std::map::find(), because I will provide only a part of the key.

Let's say I have a map with the following keys:

["abc"] -> ...
["efg"] -> ...
["ijk"] -> ...
["iik"] -> ...

I want to search through this with, let's say providing only "i", and the search should return:

["ijk"] -> ..., ["iik"] -> ...

Is this possible? I have tried to do this using iterators, but I failed, as I cannot treat them as indexes.

Note: I keep the data in a map, because of other reasons, so I don't want to change it into a different data structure.

As usual, show what you actually have tried n a small code sample! — πάντα ῥεῖ, Apr 16 '14 at 23:01

lccarrasco · Accepted Answer · 2014-04-16T23:13:35.070

5

It's possible, but you wouldn't need to actually binary-search through the data.

You can use lower_bound to find the first element and then advance the resulting iterator until your key no longer matches your criteria, storing them in a <vector> or similar container to return them all.

edited Apr 16 '14 at 23:13

answered Apr 16 '14 at 23:05

lccarrasco

2,031
1
17
20

`lower_bound` is a binary search :) – Billy ONeal Apr 16 '14 at 23:06
1

I'd like to think of that binary search as an implementation detail :) – lccarrasco Apr 16 '14 at 23:08
OK, technically speaking the words "binary search" aren't in the standard; I'll give you that. But given the requirements placed on that function it can't really be anything else. – Billy ONeal Apr 17 '14 at 00:02
2

While `std::map` commonly is implemented using a red-black (binary) tree, I don't see a strong reason why `map` must be a **binary** tree. – MSalters Apr 17 '14 at 07:15
May want to mention `is_transparent` which can make this more efficient and/or practical for some types. – Yakk - Adam Nevraumont Apr 17 '14 at 12:53

score 3 · Answer 2 · answered Apr 16 '14 at 23:03

3

map::lower_bound() will help you here.

answered Apr 16 '14 at 23:03

Michael Burr

333,147
50
533
760

honk · Answer 3 · 2019-09-12T08:44:41.923

I built a solution based on map::lower_bound() as suggested by lccarrasco and Michael Burr. This function provides an iterator to the first element in your map you are looking for. The function performs a binary search as its complexity is logarithmic in size.

Then you have to advance the provided iterator as long as the string you are looking for is a prefix of the values in your map. One way of doing this is using string::compare().

For the sake of clarity I have chosen int as value of your map. Please replace it with the type of your data. All in all the code looks as follows:

int main() {
    std::map <std::string, int> myMap{ {"abc", 1}, {"efg", 2}, {"ijk", 3}, {"iik", 4} };
    std::string prefix("i");

    for (auto it = myMap.lower_bound(prefix); it != std::end(myMap) && it->first.compare(0, prefix.size(), prefix) == 0; ++it)
        std::cout << it->first << " -> " << it->second << std::endl;

    return 0;
}

Output:

iik -> 4
ijk -> 3

Code on Ideone

How can I do a binary search on a part of the keys in a std::map?

3 Answers3