c++ - 使用相同的 key boost 访问许多 std::maps

Question

假设您有一个 std::vector<std::map<std::string, T> > .你知道所有 map有相同的键。它们可能已被初始化为

typedef std::map<std::string, int> MapType;
std::vector<MapType> v;
const int n = 1000000;
v.reserve(n);
for (int i=0;i<n;i++)
{
    std::map<std::string, int> m;
    m["abc"] = rand();
    m["efg"] = rand();
    m["hij"] = rand();
    v.push_back(m);
}

给定一个键(例如 "efg" )，我想提取给定键(肯定存在于每个映射中)的映射的所有值。

是否可以 boost 以下代码？

std::vector<int> efgValues;
efgValues.reserve(v.size());
BOOST_FOREACH(MapType const& m, v)
{
    efgValues.push_back(m.find("efg")->second);
}

请注意，这些值不一定是 int .由于分析确认大部分时间花在查找函数上，我在考虑是否有一种(GCC 和 MSVC 兼容的 C++03)方法来避免再次根据每个映射的键在映射中定位元素，因为所有映射的结构都是相同的。

如果不是，是否可以使用 boost::unordered_map (上面的代码在我的机器上慢了 15%)？是否可以缓存字符串的哈希值？

P.S.:我知道有一个 std::map<std::string, std::vector<T> >会解决我的问题。但是，我无法更改数据结构(实际上比我在此处显示的更复杂)。

Answer 1

您可以使用有状态比较器缓存和回放比较结果序列。但这太讨厌了；解决办法是调整数据结构。没有“不能”。实际上，添加一个有状态的比较器就是在改变数据结构。该要求排除了几乎任何事情。

另一种可能性是创建一个跨越 T 类型对象的链表。这样您就可以从每张 map 转到下一张 map 而无需再次查找。如果您可能从任何 map 开始(请重构结构)，那么循环或双向链表就可以解决问题。

As profiling confirms that most time is spent in the find function

保持树状数据结构，优化比较，只能加快比较速度。除非时间花在了operator< (std::string const&, std::string const&) ，您需要更改它的链接方式。