c++ - finding wildcard entries efficiently -
i have map contains strings keys; string resemble wildcards.
a key can have * @ end, means when lookup performed, string has key prefix shall match key.
how can efficiently retrieve closest matching entry in such map?
i tried sorting map entries in custom way , using lower_bound, sorting not produce correct result:
#include <map> #include <string> #include <iostream> #include <algorithm> struct compare { bool operator()(const std::string& lhs, const std::string& rhs) const { if (lhs.size() < rhs.size()) { return true; } if (lhs.size() > rhs.size()) { return false; } bool iswildcardlhsatend = (!lhs.empty() && lhs.back() == '*'); bool iswildcardrhsatend = (!rhs.empty() && rhs.back() == '*'); if (iswildcardlhsatend && iswildcardrhsatend) { return lhs < rhs; } auto lhsubstring = lhs.substr(0, lhs.size() - 1); auto rhssubstring = rhs.substr(0, rhs.size() - 1); if (iswildcardlhsatend || iswildcardrhsatend) { if (lhsubstring == rhssubstring) { return !iswildcardlhsatend; } else { return lhsubstring < rhssubstring; } } return lhs < rhs; } }; template <typename map> void lookup(const map& map, const std::string& key, int expected) { auto = map.lower_bound(key); if (it != map.end()) { std::cout << "found " << it->first << " " << key << "; "; std::cout << "expected: " << expected << " got: " << it->second << std::endl; } else { std::cout << "did not find match " << key << std::endl; } } int main() { std::map<std::string, int, compare> map = { { "bar", 1 }, { "bar*", 2 }, { "foo1", 3 }, { "bar1", 4 }, { "bar1*", 5 }, { "foo1*", 6 }, { "bar12", 7 }, { "bar12*", 8 }, { "foo12", 9 }, { "bar123", 10 }, { "b*", 11 }, { "f*", 12 }, { "b", 13 }, { "f", 14 } }; std::cout << "sorted map \n------" << std::endl; std::for_each(map.begin(), map.end(), [](const auto& e) { std::cout << e.first << std::endl; }); std::cout << "-------" << std::endl; lookup(map, "foo1", 3); lookup(map, "foo123", 6); lookup(map, "foo", 12); lookup(map, "bar1234", 8); } this produces following output demonstrates incorrect lookup:
sorted map ------ b f b* f* bar bar1 bar* foo1 bar12 bar1* foo12 foo1* bar123 bar12* ------- found foo1 foo1; expected: 3 got: 3 did not find match foo123 found bar1 foo; expected: 12 got: 4 did not find match bar1234 i open using data structure if necessary.
if separate exact search , wildcard search, natural ordering works fine strings. code seems produce desired results (i think), , efficient. separate maps can wrapped more conveniently of course.
#include <map> #include <string> #include <iostream> #include <algorithm> template <typename map> void lookup(const map& exact ,const map& wilds, const std::string& key, int expected) { auto = exact.find(key); if (it == exact.end()) { // if not exact match = wilds.lower_bound(key); // best match it--; } std::cout << "found " << it->first << " " << key << "; "; std::cout << "expected: " << expected << " got: " << it->second << std::endl; } int main() { std::map<std::string, int> wilds = { { "bar*", 2 }, { "bar1*", 5 }, { "foo1*", 6 }, { "bar12*", 8 }, { "b*", 11 }, { "f*", 12 } }; std::map<std::string, int> exact = { { "bar", 1 }, { "foo1", 3 }, { "bar1", 4 }, { "bar12", 7 }, { "foo12", 9 }, { "bar123", 10 }, { "b", 13 }, { "f", 14 } }; lookup(exact , wilds, "foo1", 3); lookup(exact , wilds,"foo123", 6); lookup(exact , wilds,"foo", 12); lookup(exact , wilds,"bar1234", 8); } 
Comments
Post a Comment