为什么对 std::tuple 的 std::vector 进行排序比对 std::arrays 的向量排序更快？

Question

我vector <vector<int>>很想知道排序 a 是否比排序 a 慢vector <array <int, 3>>。的尺寸vector为 1000000 x 3，下面是我的驱动程序代码：

#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
    vector <vector<int>> v(1000000, vector <int> (3));

    srand(time(nullptr));
    for(int i = 0; i < 1000000; ++i){
        for(int j = 0; j < 3; ++j){
            v[i][j] = rand();
        }
    }

    double start = clock();
    sort(v.begin(), v.end());
    cout << (clock()-start)/(CLOCKS_PER_SEC/1000) << endl;

    return 0;
}

g++ -O3 sorting_test.cxx使用 gcc 7.5.0 进行编译，我得到大约 300 毫秒的运行时间。声明v为 avector <array <int, 3>>将运行时间减半至 149 毫秒左右。

但是，将上述两个选项声明v为vector <tuple<int, int, int>>击败，平均运行时间约为100 ms.

我在某种程度上可以理解为什么array选项比选项快vector（array大小是一个常量表达式，与 不同vector），但我不知道为什么tuple会击败他们两个。有人可以向我解释一下吗？

填充tuple <int, int, int>s的代码是

srand(time(nullptr));
for(int i = 0; i < 1000000; ++i){
    get <0> (v[i]) = rand();
    get <1> (v[i]) = rand();
    get <2> (v[i]) = rand();
}

Answer 1

虽然整个程序的反汇编过大，但这说明了operator<forarray和之间的核心区别tuple：https : //godbolt.org/z/h1Y33e

本质上，在元组版本中，您有 3 个元素的固定比较，而在数组版本中，您有一个循环。

虽然我很惊讶编译器没有展开循环。

编辑：看起来像 clang 确实将它们优化为两个，非循环代码：https : //godbolt.org/z/cMExTb（我没有完全阅读它，但我只看到向前跳跃）