【C++】list（上）

个人主页~

list这一篇章格式以及调试方式都类似于vector和string，学完前面的两个再学这个就很简单了，接口也都大差不差，有了数据结构链表的基础就很好理解

list

一、list的介绍和使用

1、list的介绍

list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代

list的底层是双向链表结构，双向链表中每个元素存储在互不相关的节点中，在节点中通过指针与前一个和后一个元素建立联系

list的优点是在任意位置进行插入和移除元素执行效率高，缺点就是不能支持随机访问

2、list的使用

（1）list的构造

构造函数接口说明list(size_type n,const value_type& val = value_type())构造的list中包含n个值为val的元素list()构造空listlist(const list& x)拷贝构造函数list(InputIterator first,InputIterator last)用迭代器区间中的元素构造list

voidtest1(){
    list<int>lt1(10,1);
    list<int> lt2;
    list<int>lt3(lt1);
    list<int>lt4(lt1.begin(), lt1.end());for(auto e : lt1){
        cout << e <<" ";}
    cout << endl;for(auto e : lt3){
        cout << e <<" ";}
    cout << endl;for(auto e : lt4){
        cout << e <<" ";}
    cout << endl;}

构造函数、拷贝构造函数正常

这里的lt2还有原始视图是空构造

（2）list 迭代器的使用

函数声明接口说明begin和end返回第一个元素的迭代器为begin和返回最后一个元素下一个位置的迭代器为endrbegin和rend返回第一个元素的迭代器为end和返回最后一个元素下一个位置的迭代器为begin
值得注意的是，rbegin和rend为反向迭代器，对迭代器执行++操作，迭代器向前移动，也就是说forward_list也就是单链表是没有rbegin和rend迭代器的

voidtest2(){
    list<int>lt1(10,0);auto it = lt1.begin();int i =1;for(auto& e : lt1){
        e += i;
        i++;}for(auto e : lt1){
        cout << e <<" ";}
    cout << endl;}

（3）list 容量的使用

函数声明接口说明empty检测list是否为空size返回list中节点的有效个数

voidtest3(){
    list<int>lt1(10,0);
    list<int> lt2;
    cout << lt1.empty()<<" ";
    cout << lt1.size()<< endl;
    cout << lt2.empty()<<" ";
    cout << lt2.size()<< endl;}

（4）list元素访问

函数声明接口说明front返回list第一个节点值的引用back返回list最后一个节点值的引用

voidtest4(){
    list<int>lt1(10,0);
    lt1.front()=1;
    lt1.back()=2;for(auto e : lt1){
        cout << e <<" ";}
    cout << endl;}

（5）list修改

函数声明接口说明push_front在list第一个元素之前插入一个元素pop_front删除list第一个元素push_back在list最后一个元素之后插入一个元素pop_back删除list最后一个元素insert在pos位置插入一个元素erase删除pos位置的元素swap交换两个list中的元素clear清空list中的有效元素

voidtest5(){
    list<int>lt1(10,0);//插入
    lt1.push_front(1);
    lt1.push_back(2);for(auto e : lt1){
        cout << e <<" ";}
    cout << endl;//删除
    lt1.pop_front();
    lt1.pop_back();for(auto e : lt1){
        cout << e <<" ";}
    cout << endl;int i =1;for(auto& e : lt1){
        e += i;
        i++;}//insert/eraseauto it =find(lt1.begin(), lt1.end(),5);
    lt1.insert(it,11);
    lt1.erase(it);for(auto e : lt1){
        cout << e <<" ";}
    cout << endl;//swap
    list<int>lt2(10,1);
    lt1.swap(lt2);for(auto e : lt2){
        cout << e <<" ";}
    cout << endl;//clear
    lt1.clear();
    cout << lt1.empty()<< endl;}

使用方面都挺简单的，不再叙述了，参数直接查cplusplus就行

（6）list迭代器失效

因为list的底层结构为带头节点的双向循环链表，所以在list中进行插入是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他的迭代器不受影响

二、list与vector的对比

list和vector都是STL中重要的序列式容器，二者在接口上基本相同，但在底层实现上有巨大的差异，我们来对比一下
对比vectorlist底层结构动态顺序表，一段连续空间带头节点的双向循环列表随机访问支持随机访问，访问某个元素效率O(1)不支持随机访问，访问某个元素效率O(N)插入和删除任意位置插入和删除效率低，需要移动元素，时间复杂度为O(N)，插入时有可能需要增容，开辟新空间，拷贝元素，释放旧空间，导致效率更低任意位置插入和删除效率高，不需要移动元素，时间复杂度为O(1)空间利用率底层为连续空间，不容易造成内存碎片，空间利用率高，缓存利用率高底层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低迭代器原生态指针对原生态指针进行封装迭代器失效在插入元素时，要给所有的迭代器重新赋值，因为插入元素有可能会导致重新扩容，致使原来迭代器失效，删除时，当前迭代器需要重新赋值否则会失效插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响使用场景需要高效存储，支持随机访问，不关心插入删除效率大量的插入和删除操作，不关心随机访问
两者使用场景不同，各有千秋，在使用的时候合理搭配，就可以发挥最大价值

三、list其他接口

在图中可以看到，list除了常用的几种接口以外，还有其他的功能的接口，这里简单介绍一下，学习还需要到cplusplus网站上详细参考参数返回值以及一系列的内容

1、splice

将某个list移动到另一个容器当中，有三种方式：一是将list中的所有元素都传输到容器中，二是仅将迭代器指向的元素从list传输到另一个容器当中，第三个就是迭代器范围传输，从first迭代器到last迭代器的元素传输到另一个容器当中

voidtest6(){
    list<int>lt1(10,0);
    list<int>lt2(10,1);
    lt1.splice(lt1.begin(),lt2);for(auto e : lt1){
        cout << e <<" ";}}

2、remove

与erase可以相比较，它们都是删除接口，而erase的参数是一个迭代器，而remove的参数是一个值，它的作用是删除所有等于某个值的元素，然后调整容器大小

voidtest7(){
    list<int>lt1(10,0);int i =1;for(auto& e : lt1){
        e += i;
        i++;}for(auto e : lt1){
        cout << e <<" ";}
    cout << endl;
    lt1.remove(5);for(auto e : lt1){
        cout << e <<" ";}}

3、unique

删除连续相等的除了一个以外的元素

voidtest8(){
    list<int>lt1(10,0);
    list<int>lt2(10,1);
    lt1.splice(lt1.begin(), lt2);for(auto e : lt1){
        cout << e <<" ";}
    cout << endl;
    lt1.unique();for(auto e : lt1){
        cout << e <<" ";}}

4、sort

voidtest9(){
    list<int>lt1(10,0);int i =10;for(auto& e : lt1){
        e += i;
        i--;}for(auto e : lt1){
        cout << e <<" ";}
    cout << endl;
    lt1.sort();for(auto e : lt1){
        cout << e <<" ";}}

今日分享就到这了~