c++ - 如何有效地将 vector 对按第二个值分组？

我正在尝试按向量的第二个值对向量vector<pair<int,int>>进行分组。例如，如果该对是v0 : (0,1),(1,1),(3,2),(4,2),(5,1)。我想得到两个输出。第一个是第二个元素的唯一元素，即

vector<int> v2={1,2};

第二个是第一个元素的组，可以是

vector<vector<int>>v1;
v1[0]={0,1,5};
v1[1]={3,4};

如何有效地做到这一点？在v0处理之前，我是否首先需要按第二个元素对group进行排序？ std::map是更快的方法吗？不仅是方法，我还担心速度。因为我的v0是一个非常长且未排序的三角形网格顶点索引列表。任何建议将不胜感激。
更新后，我发现了一种类似于link的解决方案。它是未分类的。我不知道它的速度。

map<int, vector<int> > vpmap;
    for (auto it = v0.begin(); it != v0.end(); ++it) {
        vpmap[(*it).second].push_back((*it).first);
    };

其中，vpmap.first对应于v2； vpmap.second对应于v1。

最佳答案

您所拥有的是一种获取所需确切数据结构的合理性能方式。由于知道大小，因此请确保预先分配矢量，并使用移动迭代器避免不必要的复制：

std::vector<int> v0;
std::vector<std::vector<int>> v1;
v0.reserve(vpmap.size());
std::transform(vpmap.begin(), vpmap.end(), std::back_inserter(v0), [](auto p) { return p.first; });
v1.reserve(vpmap.size());
std::transform(make_move_iterator(vpmap.begin()), make_move_iterator(vpmap.end()), std::back_inserter(v1), [](auto p) { return p.second; });

如果您可以放宽约束，请考虑进行大图优化，例如“我是否需要转换所有这些数据？”

但是一旦有了合理的东西，就不必担心最快的技术或容器之类的东西，而开始使用分析器进行测量。有时，您担心的事情最终不是问题，并且由于问题域和输入数据以及代码积累而产生了非显而易见的成本

关于c++ - 如何有效地将 vector 对按第二个值分组？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/58786942/