2

我必须像这样转换 std::map ：

std::map<int, std::set<int> > t_contents;

在这样的地图中：

std::map<int, std::vector<int> > seq;

我正在以这种方式进行转换：

std::map<int, std::set<int> >::const_iterator it;
for(it = t_contents.begin(); it != t_contents.end(); ++it)
{    
    std::move((*it).second.begin(), (*it).second.end(), 
        std::back_inserter(seq[(*it).first])
    );   
}

考虑到地图包含多达 100 万个元素，每个集合也可以包含多达 10000 个元素。这是我在空间浪费和时间方面找到的最佳解决方案；有没有更好的方法来完成这项工作？

4

2 回答 2

3

如果您使用提示插入，性能会更好（每次插入的摊销常数）：

std::map<int, std::set<int> >::const_iterator it;
for (it = t_contents.begin(); it != t_contents.end(); ++it) {
    std::vector<int> &vec = seq.insert(seq.end(),
        std::make_pair(it->first, std::vector<int>()))->second;
    vec.reserve(it->second.size());
    vec.assign(it->second.begin(), it->second.end());
}

用于reserve防止重新分配，并vector::assign与迭代器参数一起使用；它比back_inserter.

另一种方法是将向量直接放置到地图中，仍然使用提示：

std::map<int, std::set<int> >::const_iterator it;
for (it = t_contents.begin(); it != t_contents.end(); ++it) {
    seq.emplace_hint(seq.end(), it->first,
        std::vector<int>(it->second.begin(), it->second.end());
}

请注意，不需要move设置元素；因为它们是原始的，所以移动与复制相同。

这可能更快或更慢，例如取决于是否insert检查迭代器参数之间的距离（在任何情况下它都是 O(n) 的集合大小）。

于 2013-02-08T10:41:09.400 回答
3

另一种选择是：

std::transform(t_contents.begin(), t_contents.end(), std::inserter(seq.begin()),
  [](const std::pair<const int, std::set<int>>& s) {
    std::vector<int> v;
    v.reserve(s.second.size());
    v.assign(s.second.begin(), s.second.end());
    return std::make_pair(s.first, std::move(v));
  }
);

移动ints 是没有意义的，并且std::set迭代器无论如何都是 const 的，所以你不能移出集合。

就像 ecatmur 的回答一样，这得益于插入提示，因为insert_iterator每次insert对与最后一个相邻。

于 2013-02-08T11:07:21.057 回答