STL之list和vector

list 容器

list 简介

list是C++标准模版库(STL,Standard Template Library)中的部分内容。实际上,list容器就是一个双向链表,可以高效地进行插入删除元素。

使用list容器之前必须加上头文件：#include<list>;

list属于std命名域的内容，因此需要通过命名限定：using std::list;也可以直接使用全局的命名空间方式：using namespace std;

构造函数

   list<int> c0; //空链表
   list<int> c1(3); //建一个含三个默认值是0的元素的链表
   list<int> c2(5,2); //建一个含五个元素的链表，值都是2  
   list<int> c4(c2); //建一个c2的copy链表
   list<int> c5(c1.begin(),c1.end()); //c5含c1一个区域的元素[_First, _Last]。

成员函数

• c.begin() 返回指向链表第一个元素的迭代器。
• c.end() 返回指向链表最后一个元素之后的迭代器。

    list<int> a1{1,2,3,4,5};
    list<int>::iterator it;
    for(it = a1.begin();it!=a1.end();it++)
    {
        cout << *it << "\t";
    }
    cout << endl;

• c.rbegin() 返回逆向链表的第一个元素,即c链表的最后一个数据。
• c.rend() 返回逆向链表的最后一个元素的下一个位置,即c链表的第一个数据再往前的位置。
• operator= 重载赋值运算符。
• c.assign(n,num) 将n个num拷贝赋值给链表c。
• c.assign(beg,end) 将[beg,end]区间的元素拷贝赋值给链表c。

    int a[5] = {1,2,3,4,5};
    list<int> a1;
    list<int>::iterator it;
    a1.assign(2,10);
    for(it = a1.begin();it!=a1.end();it++){
        cout << *it << " ";
    }
    cout << endl;
    a1.assign(a,a+5);
    for(it = a1.begin();it!=a1.end();it++){
        cout << *it << " ";
    }
    cout << endl;

• c.front() 返回链表c的第一个元素。
• c.back() 返回链表c的最后一个元素。
• c.empty() 判断链表是否为空。
• c.size() 返回链表c中实际元素的个数。
• c.max_size() 返回链表c可能容纳的最大元素数量。
• c.clear() 清除链表c中的所有元素。
• c.insert(pos,num) 在pos位置插入元素num。
• c.insert(pos,n,num) 在pos位置插入n个元素num。
• c.insert(pos,beg,end) 在pos位置插入区间为[beg,end]的元素。
• c.erase(pos)　　　　删除pos位置的元素。
• c.push_back(num) 在末尾增加一个元素。
• c.pop_back() 删除末尾的元素。
• c.push_front(num) 在开始位置增加一个元素。
• c.pop_front() 删除第一个元素。
• resize(n) 重新定义链表的长度,超出原始长度部分用0代替,小于原始部分删除。
• resize(n,num) 重新定义链表的长度,超出原始长度部分用num代替。
• c1.swap(c2); 将c1和c2交换。
• swap(c1,c2); 同上。
• c1.merge(c2) 合并2个有序的链表并使之有序,从新放到c1里,释放c2。
• c1.merge(c2,comp) 合并2个有序的链表并使之按照自定义规则排序之后从新放到c1中,释放c2。
• c1.splice(c1.beg,c2) 将c2连接在c1的beg位置,释放c2
• c1.splice(c1.beg,c2,c2.beg) 将c2的beg位置的元素连接到c1的beg位置，并且在c2中施放掉beg位置的元素
• c1.splice(c1.beg,c2,c2.beg,c2.end) 将c2的[beg,end)位置的元素连接到c1的beg位置并且释放c2的[beg,end)位置的元素
• remove(num) 删除链表中匹配num的元素。
• remove_if(comp) 删除条件满足的元素,参数为自定义的回调函数。

    list<int> a1{1,2,3,4,5};
    a1.remove_if([](int n){return n<3;});
    list<int>::iterator it;
    cout << "remove_if():";
    for(it = a1.begin();it!=a1.end();it++){
        cout << *it << " ";
    }
    cout << endl;

• reverse() 反转链表
• unique() 删除相邻的元素
• c.sort() 将链表排序，默认升序
• c.sort(comp) 自定义回调函数实现自定义排序

    list<int> a1{1,3,2,5,4};
    a1.sort();
    list<int>::iterator it;
    cout << "sort():";
    for(it = a1.begin();it!=a1.end();it++){
        cout << *it << " ";
    }
    cout << endl;
    
    a1.sort([](int n1,int n2){return n1>n2;});
    cout << "sort(function point):";
    for(it = a1.begin();it!=a1.end();it++){
        cout << *it << " ";
    }
    cout << endl;

• operator==
• operator!=
• operator<
• operator<=
• operator>
• operator>=

vector容器

vector简介

vector是C++标准模版库(STL,Standard Template Library)中的部分内容。之所以认为是一个容器，是因为它能够像容器一样存放各种类型的对象，简单的说：vector是一个能够存放任意类型的动态数组，能够增加和压缩数据。

使用vector容器之前必须加上<vector>头文件：#include<vector>;

vector属于std命名域的内容，因此需要通过命名限定：using std::vector;也可以直接使用全局的命名空间方式：using namespace std;

vector构造函数

• vector<type>c;创建一个空的vector容器。
• vector<type> c1(c2);复制一个vector。
• vector<type> c(n);创建一个vector,含有n个数据，数据均以缺省构造产生,即全0；
• vector<type> c(n,elem)创建一个vector,含有n个elem的拷贝数据。
• vector<type> c(beg,end)创建一个以[beg,end)区间的vector。
• ~vector<type>() 销毁所有数据,施放内存。

vector成员函数

• c.push_back(elem)在尾部插入一个elem数据。

vector<int> v;
v.push_back(1);

• c.pop_back()删除末尾的数据。
• c.assign(beg,end)将[beg,end)一个左闭右开区间的数据赋值给c。
• c.assign (n,elem)将n个elem的拷贝赋值给c。
• c.at(int index)传回索引为index的数据,如果index越界,抛出out_of_range异常。
• c.begin()返回指向第一个数据的迭代器。
• c.end()返回指向最后一个数据之后的迭代器。
• c.rbegin()返回逆向队列的第一个数据,即c容器的最后一个数据。
• c.rend()返回逆向队列的最后一个数据的下一个位置,即c容器的第一个数据再往前的一个位置。
• c.capacity()返回容器中数据个数,翻倍增长。

vector<int> v;
v.push_back(1);
cout << v.capacity() << endl;  // 1
v.push_back(2);
cout << v.capacity() << endl;  // 2
v.push_back(3);
cout << v.capacity() << endl; // 4

• c.clear()移除容器中的所有数据。
• c.empty()判断容器是否为空。
• c.erase(pos)删除pos位置的数据,传回下一个数据的位置。
• c.erase(beg,end)删除[beg,end)区间的数据，传回下一个数据的位置。
• c.front()返回第一个数据。
• c.back()传回最后一个数据，不检查这个数据是否存在。
• c.insert(pos,elem) 在pos位置插入一个elem的拷贝,返回插入的值的迭代器。
• c.insert(pos,n,elem)在pos位置插入n个elem的数据,无返回值。
• c.insert(pos,beg,end)在pos位置插入在[beg,end)区间的数据,无返回值。
• c.size()返回容器中实际数据的个数。
• c.resize(num)重新指定队列的长度。（往往用来增加vector的长度,小->大 ok 大->小 没用！）
• c.reserve()保留适当的容量。

** 针对resize()和reserver()做一点分析:**
　　reserve是容器预留空间，但并不真正创建元素对象，在创建对象之前，不能引用容器内的元素，因此当加入新的元素时，需要用push_back()/insert()函数。
　　resize是改变容器的大小，并且创建对象，因此，调用这个函数之后，就可以引用容器内的对象了，因此当加入新的元素时，用operator[]操作符，或者用迭代器来引用元素对象。
　　再者，两个函数的形式是有区别的，reserve函数之后一个参数，即需要预留的容器的空间；resize函数可以有两个参数，第一个参数是容器新的大小，第二个参数是要加入容器中的新元素，如果这个参数被省略，那么就调用元素对象的默认构造函数。
　　reserve只是保证vector的空间大小(capacity)最少达到它的参数所指定的大小n。在区间[0, n)范围内，如果下标是index，vector[index]这种访问有可能是合法的，也有可能是非法的，视具体情况而定。
resize和reserve接口的共同点是它们都保证了vector的空间大小(capacity)最少达到它的参数所指定的大小。

c.max_size()返回容器能容量的最大数量。
c1.swap(c2)将c1和c2交换。
swap(c1,c2)同上。

压缩一个臃肿的vector

很多时候大量的删除数据，或者通过使用reserver(),结果vector的空间远远大于实际的需要。所以需要压缩vector到它的实际大小。resize()能增加vector的大小。clear()仅仅移除容器内的数据,不能改变capacity()的大小,所以对vector进行压缩非常重要。

C++11中已经提供了shrink_to_fit()函数实现vector的压缩。

#include <iostream>
#include <vector>
int main()
{
    std::vector<int> v;
    std::cout << "Default-constructed capacity is " << v.capacity() << '\n';
    v.resize(100);
    std::cout << "Capacity of a 100-element vector is " << v.capacity() << '\n';
    v.clear();
    std::cout << "Capacity after clear() is " << v.capacity() << '\n';
    v.shrink_to_fit();
    std::cout << "Capacity after shrink_to_fit() is " << v.capacity() << '\n';
}

结果

Default-constructed capacity is 0
Capacity of a 100-element vector is 100
Capacity after clear() is 100
Capacity after shrink_to_fit() is 0

vector和list区别

stl提供了三个最基本的容器：vector,list,deque。

vector和built-in数组类似，它拥有一段连续的内存空间，并且起始地址不变，因此它能非常好的支持随即存取，即[]操作符，但由于它的内存空间是连续的，所以在中间进行插入和删除会造成内存块的拷贝，另外，当该数组后的内存空间不够时，需要重新申请一块足够大的内存并进行内存的拷贝。这些都大大影响了vector的效率。

list就是双向链表(根据sgi stl源代码)，因此它的内存空间可以是不连续的，通过指针来进行数据的访问，这个特点使得它的随即存取变的非常没有效率，因此它没有提供[]操作符的重载。但由于链表的特点，它可以以很好的效率支持任意地方的删除和插入。

deque是一个double-ended queue，它的具体实现不太清楚，但知道它具有以下两个特点：它支持[]操作符，也就是支持随即存取，并且和vector的效率相差无几，它支持在两端的操作：push_back,push_front,pop_back,pop_front等，并且在两端操作上与list的效率也差不多。

因此在实际使用时，如何选择这三个容器中哪一个，应根据你的需要而定，一般应遵循下面的原则：

1. 如果你需要高效的随即存取，而不在乎插入和删除的效率，使用vector
2. 如果你需要大量的插入和删除，而不关心随即存取，则应使用list
3. 如果你需要随即存取，而且关心两端数据的插入和删除，则应使用deque。

vector为存储的对象分配一块连续的地址空间，因此对vector中的元素随机访问效率很高。在vecotor中插入或者删除某个元素，需要将现有元素进行复制，移动。如果vector中存储的对象很大，或者构造函数复杂，则在对现有元素进行拷贝时开销较大，因为拷贝对象要调用拷贝构造函数。对于简单的小对象，vector的效率优于list。vector在每次扩张容量的时候，将容量扩展2倍，这样对于小对象来说，效率是很高的。

list中的对象是离散存储的，随机访问某个元素需要遍历list。在list中插入元素，尤其是在首尾插入元素，效率很高，只需要改变元素的指针。

综上所述：

vector适用：对象数量变化少，简单对象，随机访问元素频繁；

list适用：对象数量变化大，对象复杂，插入和删除频繁。

参考文献：

• STL之list容器详解
• vector和list区别