地图复杂的查找操作

我要做到以下几点：
定义字符串和任何类型的对象之间的映射（可能是一个列表，整数 - 任何东西）。
到地图中的键可以是如下（这些值，再次，并不重要）：
“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

地图复杂的查找操作

回答

相关问题