C++ list.sort()与拷贝至vector排序后拷回性能分析

云上老周

2026-8-30

C++ Primer Plus 第16章排序性能测试习题

习题描述

与数组相比，链表的元素增删操作更便捷，但排序速度更慢。由此提出猜想：将list元素拷贝到vector中完成排序，再将排序结果拷回list，或许比直接使用list自带排序算法速度更快（但该方案会消耗更多内存）。请按以下方法测试该性能猜想：
a. 创建大型vector<int>对象vi0，使用rand()生成初始值；
b. 创建与vi0同等规模的第二个vector<int>对象vi、list<int>对象li，二者初始值与vi0完全一致；
c. 分别计时：使用STL sort()算法对vi排序的耗时，使用list的sort()成员方法对li排序的耗时；
d. 将li重置为vi0存储的未排序内容，计时组合操作总耗时：将li元素拷贝到vi、对vi排序、将排序结果拷回li。
计时可使用ctime库的clock()函数，操作开始前记录clock_t start = clock()，操作结束后记录clock_t end = clock()，通过(double)(end - start)/CLOCKS_PER_SEC计算秒级耗时。该测试结果受可用内存、系统多进程负载、数据规模等因素影响（通常数据量越大，数组相对链表的排序效率优势越明显），建议使用release版本编译，可分别测试100000、1000000、10000000等不同规模元素量得到有效结果。

测试实现代码

#include <iostream>
#include <vector>
#include <list>
#include <ctime>
#include <cstdlib>
#include <algorithm>

using namespace std;

const int MAX = 10'000'000;

int main()
{
    // 初始化随机数种子
    srand(time(0));

    vector<int> vi0(MAX);
    for( int i=0; i<MAX; ++i )
    {
        vi0[i] = rand();
    }


    vector<int> vi(MAX);
    list<int> li;

    for( int i=0; i<MAX; ++i )
    {
        int r = vi0[i];
        vi[i] = r;
        li.push_back(r);
    }

    clock_t start = clock();
    sort( vi.begin(), vi.end() );
    clock_t end = clock();
    cout << "Time to sort vector 'vi': '" << (double)(end-start)/CLOCKS_PER_SEC << "'\n";

    start = clock();
    li.sort();
    end = clock();
    cout << "Time to sort list 'li': '" << (double)(end-start)/CLOCKS_PER_SEC << "'\n";

    // 重置li为未排序状态
    li.clear();
    for( int i=0; i<MAX; ++i )
    {
        li.push_back(vi0[i]);
    }

    // 测试拷贝到vector排序再拷回的总耗时
    start = clock();
    auto x = vi.begin();
    auto i = li.begin();
    while( i != li.end() )
    {
        *x = *i;
        ++x;
        ++i;
    }
    sort( vi.begin(), vi.end() );

    x = vi.begin();
    i = li.begin();
    while( x != vi.end() )
    {
        *i = *x;
        ++i;
        ++x;
    }

    end = clock();
    cout << "Time to copy 'li' to 'vi'. Sort 'vi' and copy values to 'li': '" <<
            (double)(end-start)/CLOCKS_PER_SEC << "'\n";

    return 0;
}

编译命令与运行结果

编译命令：
g++ -O3 CompareListAndArraySorting.cc

运行输出：

Time to sort vector 'vi': '1.02916'
Time to sort list 'li': '7.87467'
Time to copy 'li' to 'vi'. Sort 'vi' and copy values to 'li': '3.73348'

疑问解答

该测试结果是否与特定机器的硬件处理特性相关？
高度相关。vector排序速度快的核心原因是其内存连续，CPU缓存的预取机制可以高效加载连续内存数据，缓存命中率极高；而list的节点是分散在堆内存中的，每次访问节点几乎都会触发缓存失效，需要等待主存读取数据。不同CPU的缓存容量、缓存层级设计、内存带宽都会直接影响测试结果，比如大缓存的桌面CPU上vector的性能优势会更突出，低带宽的老旧设备上list排序的耗时会进一步升高。除此之外，编译优化等级、系统当时的进程负载也会造成结果波动。
list.sort()的核心优势是否仅为节省拷贝到vector所需的额外内存？如果软件不存在额外内存分配压力，拷贝到vector排序后拷回的方案是否比直接调用list.sort()更优？
节省O(n)额外内存只是优势之一，不是全部。首先list.sort()是稳定排序，且排序过程中不需要移动、拷贝元素本身，只需要修改节点的前后指针：如果list中存储的是拷贝成本极高的大对象（比如存了几十上百字节的自定义结构体、长字符串），元素拷贝的开销会远高于排序本身的开销，这时候直接用list.sort()反而更快。
但如果存储的是int这类基础类型、小尺寸对象，且内存足够分配对应大小的vector，你测出来的结果是普遍成立的：拷到vector排序再拷回的速度是直接调用list.sort()的2倍左右，这种场景下拷贝排序的方案确实更优。另外list.sort()不需要额外大块连续内存的特性，在内存极度紧张的嵌入式场景下是不可替代的。
本次实现是否遗漏了该习题设计的核心考察点？
基本没有遗漏，核心逻辑完全符合习题要求，只有一个可以优化的小细节：手写的元素拷贝while循环可以直接替换成STL的copy算法，比如从li拷贝到vi可以写copy(li.begin(), li.end(), vi.begin())，拷回同理，STL的copy对迭代器类型有特化优化，针对连续内存的场景效率比手写循环更高。
这个习题的核心考察点就是让你直观体会不同存储结构的性能差异，打破“容器自带方法一定比通用算法快”的刻板印象，理解性能选择本质是场景下的权衡，而不是死记硬背容器的接口特性。

内容的提问来源于stack exchange，提问作者Skuch

C++ list.sort()与拷贝至vector排序后拷回性能分析

习题描述 #

测试实现代码 #

编译命令与运行结果 #

疑问解答 #

习题描述

测试实现代码

编译命令与运行结果

疑问解答