c++ - 为什么对 std::tuple 的 std::vector 进行排序比对 std::arrays 的 vector 排序更快？

Question

我很好奇是否对 vector <vector<int>> 进行排序会比排序 vector <array <int, 3>> 慢. vector的尺寸是 1000000 乘 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作为 vector <array <int, 3>>将运行时间减半至 149 毫秒左右。
但是，声明 v作为 vector <tuple<int, int, int>>击败上述两个选项，平均运行时间约为 100 ms .
我有点理解为什么 array选项比 vector 更快选项( array 大小是一个常量表达式，与 vector 不同)，但我不知道为什么 tuple会打败他们两个。有人可以向我解释一下吗？
填写 tuple <int, int, int>的代码是

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<之间的核心区别。为 array和 tuple :https://godbolt.org/z/h1Y33e
本质上，在元组版本中，您有 3 个元素的固定比较，而在数组版本中，您有一个循环。
虽然我很惊讶编译器没有展开循环。
编辑:看起来像 clang 确实优化了它们，非循环代码:https://godbolt.org/z/cMExTb (我没有完全阅读它，但我只看到向前跳跃)