STL之list容器

我不是女神ヾ 2023-10-11 02:42 52阅读 0赞

## 摘要：本文主要介绍了list容器的相关内容。 ##

## 1、基本概念 ##

### 1.1 链表的简单介绍 ###

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

相较于vector的连续线性空间，list就显得复杂许多，它的好处是每次插入或者删除一个元素，就是配置或者释放一个元素的空间。因此，list对于空间的运用有绝对的精准，一点也不浪费。而且，对于任何位置的元素插入或元素的移除，list都是可以做到的。

### 1.2 链表的特点 ###

![1510791-20190820164509684-1069112238.png][]

*  采用动态存储分配，不会造成内存浪费和溢出
 *  链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素
 *  链表灵活，但是空间和时间额外耗费较大

## 2、list容器的迭代器 ##

List容器不能像vector一样以普通指针作为迭代器，因为其节点不能保证在同一块连续的内存空间上。List迭代器必须有能力指向list的节点，并有能力进行正确的递增、递减、取值、成员存取操作。所谓”list正确的递增，递减、取值、成员取用”是指，递增时指向下一个节点，递减时指向上一个节点，取值时取的是节点的数据值，成员取用时取的是节点的成员。

由于list是一个双向链表，迭代器必须能够具备前移、后移的能力，所以list容器提供的是Bidirectional Iterators.

List有一个重要的性质，插入操作和删除操作都不会造成原有list迭代器的失效。这在vector是不成立的，因为vector的插入操作可能造成记忆体重新配置，导致原有的迭代器全部失效，甚至List元素的删除，也只有被删除的那个元素的迭代器失效，其他迭代器不受任何影响。

## 3、常用API ##

<table style="border-color:#30e31c;border-width:2px;border-style:solid;"> 
 <tbody> 
 <tr> 
 <td style="text-align:center;">&nbsp;</td> 
 <td style="text-align:center;">API</td> 
 <td style="text-align:center;">意义</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">构造函数&nbsp;&nbsp;&nbsp;</td> 
 <td style="text-align:center;">list&lt;T&gt; lstT</td> 
 <td style="text-align:center;">采用采用模板类实现,对象的默认构造形式</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; list(beg,end) </td> 
 <td style="text-align:center;">&nbsp;构造函数将[beg, end]区间中的元素拷贝给本身</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">&nbsp;list(n,elem)</td> 
 <td style="text-align:center;">&nbsp;构造函数将n个elem拷贝给本身</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">&nbsp;list(const list &amp;lst)</td> 
 <td style="text-align:center;">&nbsp;拷贝构造函数</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">数据元素插入和删除操作</td> 
 <td style="text-align:center;">&nbsp;push_back(elem)</td> 
 <td style="text-align:center;">&nbsp;在容器尾部加入一个元素</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">pop_back()</td> 
 <td style="text-align:center;">删除容器中最后一个元素</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">push_front(elem)</td> 
 <td style="text-align:center;">在容器开头插入一个元素</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">pop_front()</td> 
 <td style="text-align:center;">从容器开头移除第一个元素</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">insert(pos,elem)</td> 
 <td style="text-align:center;">在pos位置插elem元素的拷贝，返回新数据的位置</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">insert(pos,n,elem)</td> 
 <td style="text-align:center;">在pos位置插入n个elem数据，无返回值</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">insert(pos,beg,end)</td> 
 <td style="text-align:center;">在pos位置插入[beg,end)区间的数据，无返回值</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">clear()</td> 
 <td style="text-align:center;">移除容器的所有数据</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">erase(beg,end)</td> 
 <td style="text-align:center;">删除[beg,end)区间的数据，返回下一个数据的位置</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">erase(pos)</td> 
 <td style="text-align:center;">删除pos位置的数据，返回下一个数据的位置</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">remove(elem)</td> 
 <td style="text-align:center;">删除容器中所有与elem值匹配的元素</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">大小操作</td> 
 <td style="text-align:center;"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; size() </td> 
 <td style="text-align:center;">&nbsp;返回容器中元素的个数</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">empty()</td> 
 <td style="text-align:center;">判断容器是否为空</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">resize(num)</td> 
 <td style="text-align:center;"> 重新指定容器的长度为num，若容器变长，则以默认值填充新位置。 如果容器变短，则末尾超出容器长度的元素被删除 </td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">resize(num, elem)</td> 
 <td style="text-align:center;"> 重新指定容器的长度为num，若容器变长，则以elem值填充新位置。 如果容器变短，则末尾超出容器长度的元素被删除</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">赋值操作</td> 
 <td style="text-align:center;">&nbsp;assign(beg, end);</td> 
 <td style="text-align:center;">&nbsp;将[beg, end)区间中的数据拷贝赋值给本身</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">assign(n, elem)</td> 
 <td style="text-align:center;">将n个elem拷贝赋值给本身</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">list&amp; operator=(const list &amp;lst)</td> 
 <td style="text-align:center;">重载等号操作符</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">swap(lst)</td> 
 <td style="text-align:center;">将lst与本身的元素互换</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">数据的存取</td> 
 <td style="text-align:center;">&nbsp;front()</td> 
 <td style="text-align:center;">&nbsp;返回第一个元素</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">back()</td> 
 <td style="text-align:center;">返回最后一个元素</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">反转排序</td> 
 <td style="text-align:center;">&nbsp;reverse()</td> 
 <td style="text-align:center;">&nbsp;反转链表，比如lst包含1,3,5元素，运行此方法后，lst就包含5,3,1元素</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">sort()</td> 
 <td style="text-align:center;">list排序</td> 
 </tr> 
 </tbody> 
</table>

## 4、代码示例 ##

1 #define _CRT_SECURE_NO_WARNINGS
 2 #include<iostream>
 3 #include<list>
 4 #include <algorithm>
 5 #include <string>
 6 
 7 using namespace std;
 8 
 9 void printList(list<int>&L) {
 10 for (list<int>::iterator it = L.begin(); it != L.end();it++) {
 11 cout << *it << " ";
 12 }
 13 cout << endl;
 14 }
 15 
 16 void test01() { //初始化，打印
 17 list<int>L1(10,10);
 18 list<int>L2(L1.begin(),L1.end());
 19 printList(L1);
 20 printList(L2);
 21 L2.push_back(100);
 22 printList(L2);
 23 
 24 //逆序打印
 25 for (list<int>::reverse_iterator it=L2.rbegin();it!=L2.rend();it++)
 26 {
 27 cout << *it <<" ";
 28 }
 29 cout << endl;
 30 
 31 list<int>L3; //首尾插入元素
 32 L3.push_back(10);
 33 L3.push_back(20);
 34 L3.push_back(30);
 35 L3.push_front(100);
 36 L3.push_front(200);
 37 L3.push_front(300);
 38 
 39 printList(L3);
 40 L3.pop_front(); //删除头部和尾部
 41 L3.pop_back();
 42 printList(L3);
 43 
 44 L3.insert(L3.begin(), 1000); //指定位置插入
 45 printList(L3);
 46 
 47 L3.remove(10); //去除10这个元素
 48 printList(L3);
 49 }
 50 
 51 void test02() { //容量大小的改变
 52 list<int>L4;
 53 L4.push_back(10);
 54 L4.push_back(20);
 55 L4.push_back(30);
 56 L4.push_front(100);
 57 L4.push_front(200);
 58 L4.push_front(300);
 59 cout << L4.size() << endl; //输出大小
 60 if (L4.empty())
 61 {
 62 cout << "链表为空" << endl;
 63 }
 64 else {
 65 cout << "链表不为空" << endl;
 66 }
 67 
 68 L4.resize(10); //扩充补0
 69 printList(L4);
 70 
 71 L4.resize(3); //只留3个
 72 printList(L4);
 73 
 74 list<int>L5;
 75 L5.assign(L4.begin(), L4.end());
 76 printList(L5);
 77 
 78 cout << L5.front() << endl;
 79 cout << L5.back() << endl;
 80 }
 81 
 82 bool mycompare(int v1,int v2) {
 83 return v1 > v2;
 84 }
 85 
 86 void test03() { //反转、排序
 87 list<int>L;
 88 L.push_back(10);
 89 L.push_back(50);
 90 L.push_back(20);
 91 L.push_back(60);
 92 
 93 L.reverse(); //进行了反转
 94 printList(L);
 95 
 96 L.sort(); //进行了从小到大的排列
 97 printList(L);
 98 
 99 L.sort(mycompare); //进行了从大到小的排列
 100 printList(L);
 101 }
 102 
 103 class Person {
 104 public:
 105 string m_name;
 106 int m_age;
 107 int m_height;
 108 Person(string name,int age,int height):m_name(name),m_age(age),m_height(height) {}
 109 
 110 //重载 == 让remove 可以删除自定义的person类型
 111 bool operator==(const Person & p)
 112 {
 113 if (this->m_name == p.m_name && this->m_age == p.m_age && this->m_height == p.m_height)
 114 {
 115 return true;
 116 }
 117 return false;
 118 }
 119 };
 120 
 121 bool mycompareperson(Person &p1,Person &p2) {
 122 if (p1.m_age==p2.m_age)
 123 {
 124 return p1.m_height < p2.m_height;
 125 }
 126 else {
 127 return p1.m_age > p2.m_age;
 128 }
 129 }
 130 
 131 void test04(){
 132 list<Person>L;
 133 Person p1("火男",20,165);
 134 Person p2("亚瑟", 26, 170);
 135 Person p3("诸葛亮", 29, 175);
 136 Person p4("周瑜", 26, 176);
 137 Person p5("李典", 35, 180);
 138 Person p6("不知火舞", 19, 172);
 139 Person p7("后羿", 39, 188);
 140 
 141 L.push_back(p1);
 142 L.push_back(p2);
 143 L.push_back(p3);
 144 L.push_back(p4);
 145 L.push_back(p5);
 146 L.push_back(p6);
 147 L.push_back(p7);
 148 
 149 L.sort(mycompareperson);
 150 for (list<Person>::iterator it=L.begin();it!=L.end();it++)
 151 {
 152 cout << "姓名: "<< it->m_name <<"年龄： "<<(*it).m_age<<"身高： "<<it->m_height<< endl;
 153 }
 154 
 155 L.remove(p6);
 156 for (list<Person>::iterator it = L.begin(); it != L.end(); it++)
 157 {
 158 cout << "姓名: " << it->m_name << "年龄： " << (*it).m_age << "身高： " << it->m_height << endl;
 159 }
 160 }
 161 
 162 int main() {
 163 //test01();
 164 //test02();
 165 //test03();
 166 test04();
 167 system("pause");
 168 return 0;
 169 }

转载于:https://www.cnblogs.com/lzy820260594/p/11385749.html

[1510791-20190820164509684-1069112238.png]: https://img2018.cnblogs.com/blog/1510791/201908/1510791-20190820164509684-1069112238.png