ワイルドカードエントリを効率的に見つける

Question

私はキーとして文字列を含むマップを持っています。それらの文字列はワイルドカードに似ています。

キーには最後に*を含めることができます。つまり、ルックアップを実行すると、このキーを接頭辞として持つ文字列がこのキーと一致することになります。

このようなマップで最も近い一致するエントリを効率的に取得するにはどうすればよいですか？

私はカスタムの方法でマップエントリをソートしてからlower_boundを使用してみましたが、そのソートが正しい結果を生成しません：

：

#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 it = map.lower_bound(key); 
    if (it != map.end()) { 
     std::cout << "found " << it->first << " for " << key << "; "; 
     std::cout << "expected: " << expected << " got: " << it->second << std::endl; 
    } 
    else { 
     std::cout << "did not find a match for " << 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); 
} 

をこれが間違ったルックアップを示し、次の出力を生成

sorted map 
------ 
b 
f 
b* 
f* 
bar 
bar1 
bar* 
foo1 
bar12 
bar1* 
foo12 
foo1* 
bar123 
bar12* 
------- 
found foo1 for foo1; expected: 3 got: 3 
did not find a match for foo123 
found bar1 for foo; expected: 12 got: 4 
did not find a match for bar1234 

live example

私はまた、必要に応じて他のデータ構造を使用することに開いています。

Answer 1

正確な検索とワイルドカード検索を分離すると、自然順序付けは文字列でうまく機能します。このコードは、望ましい結果を生み出すと思われます（私は思います）。別々のマップは、もちろん、より便利にラップすることができます。

#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 it = exact.find(key); 

    if (it == exact.end()) { // if not exact match 
     it = wilds.lower_bound(key); // do best match 
     it--; 
    } 

     std::cout << "found " << it->first << " for " << 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); 
}