CODEWITHSUNDEEP
c++c++11dictionarycontainersbinary-search
khajvah
khajvah

Reputation: 5090

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

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.

Upvotes: 1

Views: 2556

Answers (3)

honk
honk

Reputation: 9743

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

Upvotes: 0

lccarrasco
lccarrasco

Reputation: 2051

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.

Upvotes: 5

Michael Burr
Michael Burr

Reputation: 340198

map::lower_bound() will help you here.

Upvotes: 3

Related Questions