0

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

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"），我想提取给定键的映射的所有值（它肯定存在于每个映射中）。

是否可以加快以下代码的速度？

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

请注意，这些值不一定int。由于分析确认大部分时间都花在了 find 函数上，我在考虑是否有一种（符合 GCC 和 MSVC 的 C++03）方法来避免再次根据每个地图的键在地图中定位元素，因为所有地图的结构都是相同的。

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

PS：我知道有一个std::map<std::string, std::vector<T> >会解决我的问题。但是，我无法更改数据结构（这实际上比我在这里展示的更复杂）。

4

1 回答 1

2

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

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

由于分析确认大部分时间都花在了查找功能上

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

于 2013-01-16T08:07:34.557 回答