标题：关于vector的效率
出处：Felix021
时间：Sun, 14 Jun 2009 03:22:10 +0000
作者：felix021
地址：https://www.felix021.com/blog/read.php?1650

内容：
看过《STL之父访谈录》，了解了STL之父对效率的极度迷信，因而我对STL容器的效率也是很迷信的。

但是某一次和feli聊到vector的效率问题，他说，有时候在比赛的时候用vector会TLE，换成自己写的单链表就AC了。

可惜当时是在永和门口争论的，无法验证，后来某天想到这个问题，于是验证之：

1. vector和数组的效率对比：

对一个含有100,000,000个元素的int数组进行循环10遍的写入，测试结果(使用linux下的time命令统计)为：

Array: 
real  0m3.801s
user  0m3.136s
sys  0m0.568s

Vector: 
real  0m4.210s
user  0m3.548s
sys  0m0.520s

可以看出，vector和Array相比，至少在acm程序中，效率损失几乎是可以忽略的。
还需要声明一点，这里的vector是在运行时动态申请的空间，而array则是预分配的。

测试程序后附。


2. 单链表的效率和STL的list效率对比：

添加10,000,000个元素，测试结果为：

单链表:
real  0m0.836s
user  0m0.620s
sys  0m0.204s

list<int>:
real  0m1.202s
user  0m1.024s
sys  0m0.168s

可以看出来，完全没必要和vector对比的，接近两个数量级的差距阿。

单链表比STL的list快并不是因为STL效率损失，而是因为STL的list是一个双向链表，可能还有更多的底层细节（具体我就不了解了）。


---------------------

所以很显然的，vector比手写的单链表快。快很多。非常多。至于原因，我觉得主要有2：

1。链表是基于指针访问的，不仅需要更多的访存，而且cache命中率会比较低。
而vector的存储空间是连续的，在连续访问的情况下，命中率会高很多。

2。链表的内存是动态申请的，每一次都使用new/malloc从系统维护的堆中进行申请，效率很低。
当然，STL的list使用了优秀的allocator，但是效率仍然和vector无法比拟，所以说明第一条才是关键。

结论：在大多数情况下，我们可以迷信STL之父对效率的迷信。


--------------------

下附测试代码：

#include<iostream>
#include<vector>
using namespace std;

const int maxn = 100000000;

int d[maxn];
vector<int> e;

int main(){
    int i, j;
    if(1){ //  1是测试数组，0是测试vector
        printf("Array: \n");
        for(j = 0; j < 10; ++j){
            for (i = 0; i < maxn; ++i){
                d[i] = 0;
            }
        }
    }else{
        e.resize(maxn);
        printf("Vector: \n");
        vector<int>::iterator p;
        for(j = 0; j < 10; ++j){
            for(p = e.begin(); p != e.end(); ++p){
                *p = 2;
            }
        }
    }
    return 0;
}


#include <iostream>
#include <list>
using namespace std;

struct node_t{
    int data;
    node_t * next;
};
struct linklist{
    node_t *root;
    linklist(){ root = NULL; }
    void insert(int t){
        node_t *p = new node_t;
        p->data = t;
        p->next = root;
        root = p;
    }
    void iterate(){
        node_t *p = root;
        while(p != NULL){
            p->data = 2;
            p = p->next;
        }
    }
    /*  其实注释掉这一段是很挫的事情，但是因为只是测试使用一次，所以留给OS来做吧，这样程序会快点 :D
    ~linklist(){
        node_t *p = root;
        while(root != NULL){
            p = root;
            root = p->next;
            delete p;
        }
    }
    */
};

const int maxn = 10000000;

int main(){
    if(1){ // 1测试单链表，2测试list<int>
        linklist t;
        int i;
        for (i = 0; i < maxn; ++i){
            t.insert(i);
        }
        //t.iterate();  //如果遍历的话，还要慢些
    }else{
        list<int> t;
        int i;
        for (i = 0; i < maxn; ++i){
            t.push_back(i);
        }
        /* //如果遍历的话，还要慢些
        for (list<int>::iterator p = t.begin(); p != t.end(); ++p){
            *p = 2;
        }
        */
    }
    return 0;
}



Generated by Bo-blog 2.1.0