获取给定向量的置换索引列表的最佳方法是什么

Question

在我的应用程序中，我解决了给定点列表上的几何问题。

0 x0 y0
1 x1 y1
...

解决方案文件应包含以索引列表表示的点的特定排序。

1
0
...

解决问题后，我有一个按特定顺序排列的点对象的 result = std::vector<Point>() 向量，以及作为 original = std::vector<Point>() 向量的原始点列表。两个向量自然具有相同的大小。为了生成输出文件，我遍历 result 向量并在 original 向量中搜索点的索引。这是非常低效的，因为它确实需要 O(n^2) 时间。作为一个小小的改进，我做了以下事情：

std::ofstream out(filename);

std::vector<int> indices(instance.size);
std::iota(indices.begin(), indices.end(), 0);

for(auto &point : instance.result.points)
{
    for(std::size_t i=0; i<indices.size(); i++)
    {
        int id = indices[i];
        if(point == instance.points[id])
        {
            out << id << std::endl;
            indices.erase(indices.begin()+i);
            break;
        }
    }
}

out.close();

这让我不再重温之前已经发现的点。可悲的是，对于一个 100 万点的实例，这个过程超出了我的时间限制，我不希望导出我的解决方案比解决问题本身花费更多的时间。有没有一种方法可以有效地获取 C++ 中某个向量的预突变索引？如果需要，该解决方案可以使用大量内存。

Answer 1

您可以扩展 Point 结构以包含除位置之外的原始 ID。

Answer 2

一种易于实施且非常有效的解决方案是创建一个临时 std::unordered_map<Point,size_t>，其中键是点，值是 original 内的位置，然后在该地图中进行查找。有关如何使用您的（或库提供的）数据类型作为 std::unordered_map 中的键的详细信息，提供 here

获取给定向量的置换索引列表的最佳方法是什么

What is the best way to get a permutation index list of a given vector

c++

std

stdvector