地圖複雜的查找操作

我要做到以下幾點：
定義字符串和任何類型的對象之間的映射（可能是一個列表，整數 - 任何東西）。
到地圖中的鍵可以是如下（這些值，再次，並不重要）：
「AAA/123」 ==> 1
「AAA/」 ==> 2
「BBB/ 「==> 3
」CCC/*「 ==> 4
」CCC/123「 ==> 5
現在，問題是，我想找到給出以下字符串正確的價值觀：
」 AAA/123" 應該給1.
「AAA/111」應該給2.
「CCC/111」應該給4.
「CCC/123」應給予5
「BBB/AAA/123」應該給3地圖複雜的查找操作

任何想法，我該怎麼做，與C++和STL可能/提振？

來源

2009-02-17 Guy

我刪除了我的答案，因爲我不認爲足夠的:)我認爲特里將是理想的這個用例。只需沿着trie的路徑移動，直到找不到更多匹配項目。看看這裏：http://en.wikipedia.org/wiki/Trie。 – 2009-02-17 15:41:52

下面是其中可能的工作給予litb的答案（這是設法從答案列表中刪除）的一個變體的「*」被刪除：

template<typename Map> typename Map::const_iterator 
find_prefix(Map const& map, typename Map::key_type const& key) 
{ 
    typename Map::const_iterator it = map.upper_bound(key); 
    while (it != map.begin()) 
    { 
     --it; 
     if(key.substr(0, it->first.size()) == it->first) 
      return it; 
    } 

    return map.end(); // map contains no prefix 
}

我忘了補充一點，使用它的代碼：

std::map<std::string, int> smap; 
smap["AAA/"] = 1; 
smap["BBB/"] = 2; 
smap["AAA/AA"] = 3; 

find_prefix(smap, "AAA/AB")->second; // ==> 1 
find_prefix(smap, "AAA/AA")->second; // ==> 3 
find_prefix(smap, "BBB/AB")->second; // ==> 2 
find_prefix(smap, "CCC/AB"); // ==> smap.end()

任何評論（並感謝litb）？

來源

2009-02-17 15:37:32 Guy

是的，這是一個很好的解決方法，我認爲。如果地圖中有許多元素，則可能會先後調用find_prefix，並且搜索字符串的大小通常較小。那麼將根據地圖大小避免線性搜索，但現在取決於搜索字符串的大小。 – 2009-02-17 15:49:39

但我不知道這是否真的會更快。即時通訊有點差這樣的分析:)也許一些測試是爲了:) – 2009-02-17 15:51:21

從你的要求，看來你真的不希望地圖數據的結構，但可以設置或者很簡單的東西。

我認爲像這樣std :: map結構可能會幫助你。 Boost :: any將能夠存儲任何內容，但需要注意的是，您需要知道值類型是將其讀回來的。

鍵是字符串，因此它也可以是正則表達式。有了這個結構，你將需要兩個遍算法爲：

std::map<std::string, boost::any> _map; 
if (_map.find(key) != _map.end) 
{ 
    // exact match 
} 
else 
{ 
    // Have to do sequential regex (use boost::regex) matching 
}

由於在運行時正則表達式的評價可能是昂貴的，你可以使用std ::矢量>，使得對正則表達式模式您存儲已編譯的正則表達式到的領域之一。

這可能是給你想要完成更多的背景是有用的，因爲它可能有助於在適當的數據結構和搜索算法決定。

來源

2009-02-17 15:40:57 Ketan

使用兩張地圖怎麼樣？

std::map<std::string, std::map<int, object> >

如果你想查找AAA/*您做

a.find("aaa") => you get an iterator to the map with all "aaa" prefix

如果你想查找AAA/123你做

a.find("aaa")->find(123)

（當然你必須驗證你不「噸得到最終，這僅僅是例子）

來源

2009-02-17 15:42:17

地圖複雜的查找操作

回答

相關問題