4

我想做以下事情：
在字符串和任何类型的对象（可能是列表、整数 - 任何东西）之间定义映射。
映射的键可以如下（同样，这些值并不重要）：
“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/boost 来做到这一点吗？

4

3 回答 3

3

这是 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-17T15:37:32.683 回答
1

根据您的要求，您似乎并不真正想要地图数据结构，但可以设置或非常简单。

我认为像这样的结构 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::vector>，这样对于正则表达式模式，您可以将已编译的正则表达式存储到其中一个字段中。

提供更多您想要完成的背景可能会很有用，因为它可能有助于确定正确的数据结构和搜索算法。

于 2009-02-17T15:40:57.993 回答
0

使用两张地图怎么样？

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-17T15:42:17.443 回答