拥有字符串映射如何将其与给定字符串进行比较

Question

我们有字符串对的映射，如 name:location （类似于 UNIX 的绝对位置，如 myfolder/）。我们得到了一些位置，例如myfolder/mysubfolder/myfile。如何找到哪个地图位置最适合给定的网址？

例如，我们有一个像这样的地图：

service1:myfolder/
service2:myfolder/mysubfolder/
service3:myfolder/myothersubfolder/
service4:myfolder/mysubfolder/myfile

我们被赋予值myfolder/mysubfolder/myfile/blablabla/（字符串）。 我们想要找出它与地图中的哪个项目最相关。 搜索结果应为 service4 作为具有最相关内容的地图项。

那么如何根据给定的字符串值找到与哪个映射元素最相关的呢？

请提供一些代码，因为我是 C++ nube，不知道如何实现这样的事情？

所以我稍微简化了一个问题 - 现在我需要的所有关系是给定路径的深度，在字符串情况下，只需迭代所有地图路径，查看长度，搜索给定路径中的出现并记住最长的地图项即可获得在给定路径中找到的路径。

Answer 1

有两个选项：

1. 如果您需要运行多个查询：
   1. 构建逆向地图或使用双向地图。
   2. 使用 upper_bound 和查找第一个较大的元素
      • 如果您需要具有最长公共前缀的元素，请检查此元素和上一个（最后一个较小的）元素，然后选择具有较长公共前缀的元素。
      • 如果您需要作为前缀的元素，请向后扫描，直到找到作为前缀的元素。
2. 如果您只需要一次查询，简单的线性搜索会更快（构建逆映射需要 O(n log(n))，而一次迭代只需 O(n) >)，而且更容易实现。只需迭代映射，为每个值计算前缀长度并记住迄今为止的最佳匹配（我想建议使用 std::max_element ，但它通过比较运算符实现最大值，而您需要最大值指标）。

Answer 2

如果您的地图定义如下：

typedef std::map<std::string,std::string> MyMap;
MyMap my_map;

...并且搜索词定义如下：

std::string my_key_to_find = "service4";

...那么您可以获得与此键关联的值，如下所示：

std::string found_val;
MyMap::const_iterator it = my_map.find(my_key_to_find);
if( it != my_map.end() )
  found_val = it->second;
else
  std::cout << "Key not found!\n";

Answer 3

如果我正确理解您的问题，您想按值（字符串）搜索键，其中匹配值是提供的搜索词的子字符串。我认为对于这个普遍问题（即任意字符串及其所有子字符串）没有一个简单的解决方案。

但是，示例中用作值的字符串具有特定的结构（即文件系统路径）。您可以利用这个结构来提出一个干净的解决方案。首先，制作一个双向地图。然后，执行以下查找过程：

1. 如果路径为空，则失败。
2. 根据请求路径在map中反向查找
3. 如果找到则返回关联值。
4. 将最后一个组件弹出路径。
5. 环形。

如果列表很短，您可能只想循环（键，值）对列表并选择值最相似的键（即最长的公共子字符串）。