0

我创建了一个多图，因为我有重复键。但我想做一个有效的操作，这样我就可以生成一个新的多图，随后对齐更高的键。这就是我的意思：

这就是我所拥有的：

key        values
11          qwer
11          mfiri
21          iernr
21          ghfnfjf
43          dnvfrf

这就是我想要达到的

key        values
11          qwer,iernr
11          mfiri,iernr
21         iernr,dnvfrf
21          ghfnfjf,dnvfrf
43          dnvfrf

我有大约 1000 万个条目，所以我正在寻找一些有效的东西。

在上述值中，“qwer,iernr”是一个字符串。

4

4 回答 4

2

这是一个简单的方法：

auto cur = map.begin();
auto next = map.upper_bound(cur->first);

for(; next != map.end(); next = map.upper_bound(cur->first))
{
    for(; cur != next; ++cur)
    {
        cur->second += ", ";
        cur->second += next->second;
    }
}

...给定一个std::multimap<int, std::string> map;

但是，任何转换 10m+ 元素的操作都不会非常快。

于 2013-01-18T21:55:24.267 回答
0

看起来直接的方式可以正常工作。地图元素将按升序排列（假设比较运算符适合您）。因此，只需通过相等的范围并在范围之后使用元素的值修改它们就可以满足您的需求。

克隆地图（如果您需要原始地图），获取第一个元素，获取equal_range()其键，使用范围内第二个迭代器的值修改值（除非它是最后一个）。获取equal_range()第二个迭代器的键。重复。

于 2013-01-18T21:48:02.800 回答
0

同意尤金！另请参阅有关 equal_range() stl::multimap 的以下参考 - 我如何获取数据组？

于 2013-01-18T21:56:19.740 回答
0

为此，您需要简单地遍历地图，同时按顺序构建新地图。

您可以在两个级别上执行此操作：

for (auto it=map.cbegin(); it != map.cend(); ) 
{ 
    // The inner loop is over all entries having the same key
    auto next_key_it=find_next_key_after(it);
    for (; it != next_key_it; ++it) {
         new_map.emplace_hint(new_map.end(), it->first, new_value(it->second, next_key_it));
    }
}

new_value 函数（或 lambda）执行值转换（如果第二个参数是 map.end()，则不执行）。

find_next_key_after(it) 函数返回与 map.upper_bound(it->first) 相同的结果，但也可以实现为线性搜索具有不同键的第一个条目。

这取决于您的（预期的）密钥分布，使用哪个 - 如果密钥重复的次数很少，线性搜索更好；如果不同键的数量有限，并且键范围相等，那么upper_bound 可能会更好。

为了保证复杂度，线性搜索更好：整个算法具有 O(n) 复杂度。这是尽可能高效的。

于 2013-01-18T22:16:18.583 回答