时间戳

首页 > 解决方案 > 在其他地图值中查找元素的最佳方法是什么？

c++ - 在其他地图值中查找元素的最佳方法是什么？

问题描述

我尝试在地图值中找到也出现在其他值中的元素。

{
  1: ["a", "b", "c", "d"],
  2: ["a", "c"],
  3: ["c", "d"],
  4: ["a", "c"]
}

=>

{
  "a": [ 1, 2, 4 ], // a occurs in the map which key are 1/2/4
  "b": [ 1 ],
  "c": [ 1, 2, 3, 4],
  "d": [ 1, 3 ]
}

我的实现是：

map<int, set<string>> map1 = {
  { 1, set<string>{"a", "b", "c", "d"} },
  { 2, set<string>{"a", "c"} },
  { 3, set<string>{"c", "d"} },
  { 4, set<string>{"a", "c"} },
};

map<string, set<int>> map2;

for (const auto& [id, str_set] : map1) {
  for (const auto& s : str_set) {
    if (map2.count(s) == 0) {
      map2[s] = std::set<int>{id};
    } else {
      map2[s].emplace(id);
    }
  }
}

看起来效率不高。那么有没有其他方法可以加快速度呢？或者是否有任何适当的数据结构/算法来处理我想要的这些数据？

标签： c++algorithmdata-structures

解决方案

如果您有权访问 Boost 库，则可以使用boost::bimap来组合您的两个地图。

boost::bimap<boost::bimaps::multiset_of<int>, boost::bimaps::multiset_of<std::string>> map;
map.insert(1, "a");
...
map.insert(4, "c");

然后，您可以使用数字map.left和字符串查找map.right

推荐阅读