How to Find a Substring in a String in a Multimap

Question

How do you find the substring within a string in the key of a multimap? For example, if I enter "Louis," then Louisville, Louisberg, and StLouis are found?

Answer 1

Why bother with a multimap for that?

std::string search_term = "Louis";
std::unordered_set<std::string> data = { "Louisville", "Louisberg", "StLouis" };
for (std::string const& each : data) {
    if (std::find(each.begin(), each.end(), search_term) != std::string::npos) { 
        // contains it
    } 
}

That would be a good option I believe, if you really have to use a multimap then doing substrings of keys is kind of hard, since that's not what they're made for

Answer 2

For what you want to do you will have to search within each and every key, not just the prefix or suffix. I don't think there's any way round that and it cannot be optimised since the search term can occur anywhere within the key.

You can use std::find_if and supply a predicate function for matching elements and iterate your map. I am using std::map in the code below but this could apply for a std::multimap too.

#include <map>
#include <string>
#include <algorithm>
#include <iostream>

int main()
{
    std::map<std::string, std::string> myMap{
        {"Louis", "AA"}, {"Louisville", "BBB"}, {"Louisberg", "A"},
        {"StLouis ", "C"}, {"Huntsville", "D"} };

    std::string term("Louis");

    auto keyContains = [&term](const std::pair<std::string, std::string>& item)
    {
        return item.first.find(term) != std::string::npos;
    };

    auto iter = std::find_if(myMap.begin(), myMap.end(), keyContains);

    while (iter != myMap.end())
    {
        std::cout << iter->first << std::endl;
        iter = std::find_if(std::next(iter), myMap.end(), keyContains);
    }
}

keyContains is lambda function. If you're not familiar with lambda functions you can use a functor instead:

struct keyContains
{
    keyContains(const std::string& searchTerm) : mSearchTerm(searchTerm) {}

    bool operator() (const std::pair<std::string, string>& item) const
    {
        return item.first.find(mSearchTerm) != std::string::npos;
    }

    std::string mSearchTerm;
};

Then initialise it like this: keyContains comp("Louis") and pass comp as the predicate.

Hope this is helpful? It's effectively a for loop that walks the map. Working version here.

Update:

I just read your comment where you say your search should return 54049 results. That's a lot of records! To do that it is better to match against prefix or suffix. You can use std::map::lower_bound() and std::map::upper_bound().