转换 map<int C++，请将<int>>设置为 map<int， 矢量<int>>

Question

我必须转换一个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万个元素，每个集合也可以包含多达1万个元素。这是我在浪费空间和时间方面找到的最佳解决方案；有更好的方法做这项工作吗？

Answer 1

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

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与迭代器参数一起使用；它比CCD_ 3更可读（如果不是更有效的话）。

另一种选择是将矢量直接放置到地图中，仍然使用提示：

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））。

Answer 2

另一个选项是：

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));
  }
);

移动int是毫无意义的，而且std::set迭代器无论如何都是常量，所以不能移出集合。

与ecatmur的答案一样，这得益于使用提示进行插入，因为每次对insert_iterator的赋值都会以前一个插入点作为提示执行insert，这是一个巨大的性能优势，因为输入范围已经按照相同的顺序排序，因此每次连续插入都与最后一个相邻。