对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不同。具体来说，您只比较第一个成员，而不是两者。显然，这可能会导致一些速度增加（但可能不足以在任何真实程序中注意到）。

Answer 2

我估计这两种解决方案之间没有太大差异。

但是像所有与性能相关的查询，而不是依赖互联网上的某个人告诉他们是相同的，或者一个比另一个更好，进行自己的测量。有时，实施中的细微差别会对实际结果产生很大影响。

话虽如此，std::pair的实现是一个结构（或类），有两个成员，first和second，所以我很难想象这里有任何真正的区别 - 你只是用你自己的比较函数实现你自己的对这与现有的一对完全相同...无论是在类中的内部函数还是作为独立函数都不太可能产生太大的影响。

编辑：我做了以下“将代码混合在一起”：

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstdlib>

using namespace std;

const int size=100000000;

pair <int,int> clients1[size];

struct cl1{
    int first,second;
};


cl1 clients2[size];

struct cl2{
      int first,second;

      bool operator<(const cl2 x) const {
            return first < x.first;
      }
};
cl2 clients3[size];




template<typename T>
void fill(T& t)
{
    srand(471117);   // Use same random number each time/ 
    for(size_t i = 0; i < sizeof(t) / sizeof(t[0]); i++)
    {
    t[i].first = rand();
    t[i].second = -t[i].first;
    }
}



void func1()
{
    sort(clients1,clients1+size);
}


bool cmp(cl1 x, cl1 y){
      return x.first < y.first;
}

void func2()
{
    sort(clients2,clients2+size,cmp);
}


void func3()
{
    sort(clients3,clients3+size);
}

void benchmark(void (*f)(), const char *name)
{
    cout << "running " << name << endl;
    clock_t time = clock();
    f();
    time = clock() - time;
    cout << "Time taken = " << (double)time / CLOCKS_PER_SEC << endl;
}

#define bm(x) benchmark(x, #x)

int main()
{
    fill(clients1);
    fill(clients2);
    fill(clients3);

    bm(func1);
    bm(func2);
    bm(func3);
}

结果如下：

running func1
Time taken = 10.39
running func2
Time taken = 14.09
running func3
Time taken = 10.06

我运行基准测试三次，它们都在上述结果的~0.1s内。

编辑2：看看生成的代码，很明显“中间”函数需要更长的时间，因为比较是针对pair和struct cl2内联进行的，但是不能为struct cl1内联 - 所以每个比较字面上都会产生一个函数调用，而不是函数内部的一些指令。这是一个很大的开销。