c++ - 对 std::pair 与 struct 的数组进行排序:哪个更快？

Question

我想知道是否对 std::pair 的数组进行排序更快，或者 struct 的数组？

这是我的代码段:

代码 #1: 排序 std::pair数组(按第一个元素):

#include <algorithm>

pair <int,int> client[100000];

sort(client,client+100000);

代码 #2: 排序 struct (来自 A ):

#include <algorithm>

struct cl{
      int A,B;
}

bool cmp(cl x,cl y){
      return x.A < y.A;
}

cl clients[100000];

sort(clients,clients+100000,cmp);

代码 #3: 排序 struct (通过 A 和内部运营商 < ):

#include <algorithm>

struct cl{
      int A,B;

      bool operator<(cl x){
            return A < x.A;
      }
}

cl clients[100000];

sort(clients,clients+100000);

更新:我使用这些代码解决了在线裁判中的一个问题。我的代码 #1 的时间限制为 2 秒，代码 #2 和 #3 的接受(运行时间为 62 毫秒)。与其他代码相比，为什么代码 #1 花费这么多时间？哪里不一样了？

Answer 1

你知道吗 std::pair是？它是一个结构(或类，对于我们的目的而言，这与 C++ 中的相同)。所以如果你想知道什么更快，通常的建议适用:你必须测试它并在你的平台上自己找出答案。但最好的选择是，如果您实现与 std::pair 等效的排序逻辑，您将获得相同的性能，因为编译器不关心您的数据类型名称是否为 std::pair或其他东西。

但请注意，您发布的代码在功能上不等同于 operator <为 std::pair 提供.具体来说，您只比较第一个成员，而不是两者。显然，这可能会带来一些速度提升(但可能不足以在任何实际程序中引起注意)。