c++ - 在 C++ 中对数据结构进行排序的最快方法

Question

我有一个数据结构，它由三个表示坐标的 int 值和一个表示该坐标处的值的 double 组成。我想将它们存储在一起，并按值(value)对它们进行排序。值不是唯一的。现在，我将它们放在 struct 中，并使用 lambda 对它们进行排序，如下面的代码所示。由于这是一段对性能至关重要的代码，因此我正在寻找一种能够提供最快排序的实现。该列表将包含 10^6 到 10^7 个元素。

解决这个问题最优雅的方法是什么？我并没有尝试使用 std::sort，但我主要想问的是将数据存储在 struct 中是否是最佳解决方案，还是有更好的选择？

#include <vector>
#include <algorithm>
#include <iostream>

struct Data
{
    int i;
    int j;
    int k;
    double d;
};

int main()
{
    std::vector<Data> v;

    v.push_back({1,2,3,0.6});
    v.push_back({1,2,3,0.2});
    v.push_back({1,2,3,0.5});
    v.push_back({1,2,3,0.1});
    v.push_back({1,2,3,0.4});

    std::sort(v.begin(), v.end(), [](const Data& a, const Data& b)
            { return a.d < b.d; });

    for (auto d : v)
        std::cout << d.i << ", " << d.j << ", "
                  << d.k << ", " << d.d << std::endl;

    return 0;
}

Answer 1

对它们进行排序的最快方法是不必对它们进行排序。

以插入速度稍慢为代价，您可以将整个容器分类存储，并仅插入正确的位置。 std::set可以在这里帮助你，或者你可以自己动手。

编辑 A std::multiset如果您需要允许比较相等的值，将提供相同的优势。