【C++】list（上）

个人主页~

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

---

list

一、list的介绍和使用1、list的介绍2、list的使用（1）list的构造（2）list 迭代器的使用（3）list 容量的使用（4）list元素访问（5）list修改（6）list迭代器失效 二、list与vector的对比三、list其他接口1、splice2、remove3、unique4、sort

一、list的介绍和使用

1、list的介绍

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

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

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

2、list的使用

（1）list的构造

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

void test1(){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和返回最后一个元素下一个位置的迭代器为end
rbegin和rend	返回第一个元素的迭代器为end和返回最后一个元素下一个位置的迭代器为begin

值得注意的是，rbegin和rend为反向迭代器，对迭代器执行++操作，迭代器向前移动，也就是说forward_list也就是单链表是没有rbegin和rend迭代器的

void test2(){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中节点的有效个数

void test3(){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最后一个节点值的引用

void test4(){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中的有效元素

void test5(){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;//swaplist<int> lt2(10, 1);lt1.swap(lt2);for (auto e : lt2){cout << e << " ";}cout << endl;//clearlt1.clear();cout << lt1.empty() << endl;}

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

（6）list迭代器失效

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

二、list与vector的对比

list和vector都是STL中重要的序列式容器，二者在接口上基本相同，但在底层实现上有巨大的差异，我们来对比一下

对比	vector	list
底层结构	动态顺序表，一段连续空间	带头节点的双向循环列表
随机访问	支持随机访问，访问某个元素效率O(1)	不支持随机访问，访问某个元素效率O(N)
插入和删除	任意位置插入和删除效率低，需要移动元素，时间复杂度为O(N)，插入时有可能需要增容，开辟新空间，拷贝元素，释放旧空间，导致效率更低	任意位置插入和删除效率高，不需要移动元素，时间复杂度为O(1)
空间利用率	底层为连续空间，不容易造成内存碎片，空间利用率高，缓存利用率高	底层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低
迭代器	原生态指针	对原生态指针进行封装
迭代器失效	在插入元素时，要给所有的迭代器重新赋值，因为插入元素有可能会导致重新扩容，致使原来迭代器失效，删除时，当前迭代器需要重新赋值否则会失效	插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响
使用场景	需要高效存储，支持随机访问，不关心插入删除效率	大量的插入和删除操作，不关心随机访问

两者使用场景不同，各有千秋，在使用的时候合理搭配，就可以发挥最大价值

三、list其他接口

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

1、splice

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

void test6(){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的参数是一个值，它的作用是删除所有等于某个值的元素，然后调整容器大小

void test7(){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

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

void test8(){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

void test9(){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 << " ";}}

---

今日分享就到这了~