stl vector与list详细对比

vector是stl中常用的容器之一。vector与数组array比较类似，可以看成是array功能更强大的升级版。与array的不同在于，array是静态数组，容量大小在数组初始化的时候就是固定的。而vector是一个动态数组，即vector可以动态调整数组大小而无须用户进行手动干预。

因为vector的底层实现是数组，所以其优势是在尾部插入删除数据很快，随机访问也很快，时间复杂度只有O(1)。而当其在头部或者其他位置插入删除数据时，因为需要对元素进行移动复制，所以效率会很低。

vector的初始化有如下几种方式
1.vector first first为空，size为0， 此时first中没有元素，capacity也为0，说明此时 还没有具体分配内存空间。这种情况适合元素个数未知需要动态添加元素的场景。
2

vector second(first)
vector second = first

上面两种方式都可以实现初始化，其中second是first拷贝，且类型必须相同，second中元素个数与类型与first中保持一致。

3 vector third = {1, 2, 3, 4, 5}
4 vector fourth(third.begin(), third.begin()+4) 使用两个迭代器范围内元素进行拷贝，范围中的元素类型与新容器中的元素类型须保持一致。这种方法对于获得一个序列的子序列比较方便。

5.vector fifth(3)
上面的方式使用默认值初始化，每个元素的值使用缺省默认值。对于int类型，默认值为0.

6.vector sixth(3, -1);
与第五种方式的区别在于，该方式指定了初始化的值。

void print_vec(vector &v, const char *p) {
    cout<
        cout<
    vector first;
    vector second(first);
    second = {1, 2, 3};
    print_vec(first, "first");
    print_vec(second, "second");

    vector third = {1, 2, 3, 4, 5};
    vector fourth(third.begin(), third.begin()+4);
    print_vec(fourth, "fourth");

    vector fifth(3);
    vector sixth(3, -1);
    print_vec(fifth, "fifth");
    print_vec(sixth, "sixth");
}

上述代码在main方法中跑起来，最后输出结果如下

first is: 
second is: 1 2 3 
fourth is: 1 2 3 4 
fifth is: 0 0 0 
sixth is: -1 -1 -1 

前面我们讲到vector与数组类似，而数组是具有一段连续的内存空间的，并且起始的地址不变。正因为这个特性，其才能高效地进行随机访问，并高效在尾部进行追加，时间复杂度均为O(1)。
而stl中的list是由双向链表实现，因此其内存空间并不连续。因为内存空间不连续，只能通过指针去访问数据，因此list不能随机读取，追加数据效率也没有vector效率高。但因为其是指针结果，随机插入数据与删除数据就特别方便，并且可以在两端进行pop与push操作。

void print_list(list ll, const char *p) {
    cout< first;
    list second(4, -1);
    list third(second.begin(), second.end());
    list fourth(third);

    int nums[] = {1, 2, 3, 4, 5};
    list fifth(nums, nums + sizeof(nums) / sizeof(nums[0]));

    print_list(third, "third");
    print_list(fourth, "fourth");
    print_list(fifth, "fifth");
}

list初始化的方式与vector类似。上面方法在main方法中跑起来，最后结果为

third is: -1 -1 -1 -1 
fourth is: -1 -1 -1 -1 
fifth is: 1 2 3 4 5 

前面我们提到vector与list的区别：
vector方便尾部追加与随机访问，但是随机插入与删除比较耗时。
list擅长随机插入与删除，但是随机访问与尾部追加没有vector快。
下面我们就用代码来进行实测，看看是不是确实我们所说。

#include
#include
#include
#include
using namespace std;

void vec_list_compare() {
    clock_t start, end, start2, end2, start3, end3, start4, end4, start5, end5, start6, end6;
    int n = 100000;
    vector vec;
    list ll;

    //  尾部添加元素，vector可以高效随机读取
    start = clock();
    for(int i=0; i::iterator it=vec.begin(); it!=vec.end();it++) {
        vec.erase(it);
    }
    end3 = clock();
    cout<<"vec delete cost time is: "< 0) {
        ll.pop_back();
    }
    end4 = clock();
    cout<<"list delete cost time is: "<::iterator it = find(vec.begin(), vec.end(), n/2);

        vec.insert(it, n);
    }
    end5 = clock();
    cout<<"vec insert cost time is: "< 
上述代码运行起来，输出结果为
 
vec add data cost time is: 0.006538
list add data cost time is: 0.027703

vec delete cost time is: 0.51943
list delete cost time is: 0.015977

vec insert cost time is: 7.70983
list insert cost time is: 0.002979
 
可以看到，在尾部追加数据，vector类型完胜。
 而对于随机删除数据与随机插入数据，list则碾压vector。