最近在重构公司的一个C++模块，逻辑里有排序、过滤等操作。开发过程中，遇到下面的一些问题：

问题和猜想

• 单链表的归并排序和线性表的快速排序的时间复杂度都是 O(nlog(n))，但在实际情况中哪个更快呢？需要测试一下。
• 猜想的发散，stl vector 和 list（双向链表）的迭代器遍历、顺序插入、clear操作， 时间复杂度好像都是相同的，但谁更快呢？
• 看stl代码去研究vector和list的实现，并不能得到我们最终想要的结果，测试数据会更直观。

测试总结

先写测试总结，测试方法、测试结果都在下面。

• 迭代器遍历，list 比vector 稍块，使用for_each 比使用for更快。
• 顺序插入， vector比list 约快3倍
• clear操作，vector 几乎不耗时，list 要耗费好多时间，vector比list至少快1千倍以上
• 排序， vector 大约比list 快2倍。

结合项目，对比vector和list的性能

• 在我重构前，模块使用的是vector存储数据，排序使用的是快排（大于16小于堆），过滤则是用临时数据vector转存。
• 在我重构后，使用list存储，排序使用list的归并排序，过滤则是直接使用list的erase操作。
• 重构前，耗时4000微秒，重构后1500微秒，时间减少60%。
• list除了删除操作和遍历操作，排序和插入都比vector慢，但是我使用list后，却提升了性能。原因可能有2个： 1.单个元素数据结构大，vector移动这些元素代价较大，而list移动这些元素反而代价很小；2.去掉了中间临时存储，数据的转存代价也比较大。
• 使用list后，模块的可扩展性也变得更好了。

这次项目最大的收获就是，如果有过滤操作，优选使用list。vector的缺点如下，1.vector快速排序需要移动元素，如果元素占据空间大，移动代价也非常大。2.vector过滤需要借助中间临时存储，直接erase的代价更大。

测试方法

• 随机生成10万数据量，由vector和list结构的变量分别存储
• 对vector 和 list 的数据分别做如下， 1）迭代器遍历 2）顺序插入 3） clear操作 4）排序
• 记录每种操作消耗的时间
• 多次测试，记录典型的数据结果

测试结果

直接列出测试结果，单位是微秒

(附)测试程序

Github 托管地址，保持更新：https://github.com/zuocheng-liu/code-samples/blob/master/linux-c/stl/vector_list_performance_test.cpp

#include<stdio.h>
#include<stdlib.h>
#include<sys/time.h>
#include <list>
#include <vector>
#include <iostream>

#define MAX_NUM 100000

using namespace std;

timeval tv;
uint64_t timer;


bool NumCmp(uint32_t a, uint32_t b) { return (a > b); }

void startTimer() {
    gettimeofday(&tv,NULL);
    timer = 1000000 * tv.tv_sec + tv.tv_usec;
}

uint64_t stopTimer() {
    gettimeofday(&tv,NULL);
    timer = 1000000 * tv.tv_sec + tv.tv_usec - timer;
    return timer;
}

int main() {
    vector<uint32_t> v;
    vector<uint32_t> v2;
    list<uint32_t> l;
    list<uint32_t> l2;
    for (int i = 0; i< MAX_NUM; ++i) {
        srand((int)time(0)  * i * i + 1);
        int num = rand();
        v.push_back(num);
        l.push_back(num);
    }

    // compare oper traverse
    startTimer();   
    for (vector<uint32_t>::iterator iter = v.begin(); iter != v.end(); ++ iter) {
        *iter;
    }
    cout<<"vector\t traverse\t :\t"<< stopTimer() << endl;  

    startTimer();   
    for (int i = 0 ; i < MAX_NUM; ++ i) {
        //v[i];
    }
    cout<<"vector\t num traverse\t :\t"<< stopTimer() << endl;  


    startTimer();   
    for (list<uint32_t>::iterator iter = l.begin(); iter != l.end(); ++ iter) {
    }
    cout<<"list\t traverse\t :\t"<< stopTimer() << endl;  


    // compare oper push_back   
    startTimer();   
    for (vector<uint32_t>::iterator iter = v.begin(); iter != v.end(); ++ iter) {
        v2.push_back(*iter);
    }
    cout<<"vector\t push_back\t :\t"<< stopTimer() << endl;  

    startTimer();   
    for (list<uint32_t>::iterator iter = l.begin(); iter != l.end(); ++ iter) {
        l2.push_back(*iter);
    }
    cout<<"list\t push_back\t :\t"<< stopTimer() << endl;  

    // compare oper delete
    startTimer();
    v2.clear();
    for (vector<uint32_t>::iterator iter = v2.begin(); iter != v2.end(); ++ iter) {
    //    v2.erase(iter);
    }
    //cout<<"vector\t delete\t :\t"<< stopTimer() << endl;  

    startTimer();   
    for (list<uint32_t>::iterator iter = l2.begin(); iter != l2.end(); ++ iter) {
        iter = l2.erase(iter);
    }
    cout<<"list\t delete\t :\t"<< stopTimer() << endl;  

    // compare oper push_back   
    startTimer();   
    for (vector<uint32_t>::iterator iter = v.begin(); iter != v.end(); ++ iter) {
        v2.push_back(*iter);
    }
    cout<<"vector\t push_back\t :\t"<< stopTimer() << endl;  

    startTimer();   
    for (list<uint32_t>::iterator iter = l.begin(); iter != l.end(); ++ iter) {
        l2.push_back(*iter);
    }
    cout<<"list\t push_back\t :\t"<< stopTimer() << endl;  


    // compare oper clear
    startTimer();   
    v2.clear();
    cout<<"vector\t clear      \t:\t"<< stopTimer() << endl;  

    startTimer();   
    l2.clear();
    cout<<"list\t clear     \t :\t"<< stopTimer() << endl;  

    // compare oper sort
    startTimer();   
    std::sort(v.begin(), v.end(), NumCmp);
    cout<<"vector\t sort    \t :\t"<< stopTimer() << endl;  

    startTimer();   
    l.sort(NumCmp);
    cout<<"list\t sort    \t :\t"<< stopTimer() << endl;  

    return 0;
}