一. list的介绍
list即带头双向循环链表，支持在任意位置O(1)的插入和删除
二. list的构造函数
方法一：无参构造
list<int> lt1; //构造int类型的空容器
方法二：n个val值构造
list<int> lt2(10,2)//构造10个值为2的int容器
方法三：拷贝构造
list<int> lt3(lt2)//lt2拷贝构造给lt3
方法四：迭代器区间构造
string s ("hello world") list<int> lt4(s.begin(), s.end());
三. list的插入 & 删除
🎨push_front和pop_front
头插 头删
int main() { list<int> lt; lt.push_front(0); lt.push_front(1); lt.push_front(2); for (auto e : lt) { cout << e << " "; } cout << endl; lt.pop_front(); for (auto e : lt) { cout << e << " "; } cout << endl; }
🎨push_back和pop_back
尾插尾删
int main() { list<int> lt; lt.push_back(0); lt.push_back(1); lt.push_back(2); for (auto e : lt) { cout << e << " "; } cout << endl; lt.pop_back(); lt.pop_back(); for (auto e : lt) { cout << e << " "; } cout << endl; }
🎨insert
list当中的insert函数支持三种插入方式：
指定位置插入一个数
指定位置插入n个val值的数
指定迭代器位置插入一段迭代器区间（左闭右开）
int main() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); list<int>::iterator pos = find(lt.begin(), lt.end(), 3); if(pos != lt.end()) { lt.insert(pos, 20); } for (auto e : lt) { cout << endl; } cout << endl;// 1 2 20 3 pos = find(lt.begin(), lt.end(), 3); if(pos != lt.end()) { lt.insert(pos, 5, 30);//在三的位置插入5个30 } for (auto e : lt) { cout << endl; } cout << endl;// 1 2 20 30 30 30 30 30 3 vector<int> v(2, 7); list<int>::iterator pos = find(lt.begin(), lt.end(), 1); if(pos != lt.end()) { lt.insert(pos, v.begin(), v.end()); //在1的位置插入2个7 } for (auto e : lt) { cout << e << " "; } cout << endl; //7 7 1 2 20 30 30 30 30 30 3 return 0; }
💢问：这里的pos会失效吗？
不会，在pos位置前增加一个节点，并改变链接关系，但pos还是指向原本的位置，也不存在野指针
ps：由于find是stl各个容器都需要的，所以实现在了头文件algorithm.h中
🎨erase
int main() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); list<int>::iterator pos = find(lt.begin(), lt.end(), 2); if (pos != lt.end()) { lt.erase(pos); //删除2 } for (auto e : lt) { cout << e << " "; } cout << endl; //1 3 4 5 pos = find(lt.begin(), lt.end(), 4); if (pos != lt.end()) { lt.erase(pos, lt.end()); //删除4及其之后的元素 } for (auto e : lt) { cout << e << " "; } cout << endl; //1 3 return 0; }
💢灵魂发问：此处的pos会失效吗？
打印崩溃了，显而易见，删除后，再访问就是野指针了
四. list的迭代器的使用
🌊正向迭代器
话不多说，上代码
#include <iostream> #include <list> using namespace std; int main() { list<int> lt(10, 2); //正向遍历 list<int>::iterator it = lt.begin(); while (it != lt.end()) { cout << *it << " "; it++; } cout << endl; return 0; }
🌊反向迭代器
#include <iostream> #include <list> using namespace std; int main() { list<int> lt(10, 5); //反向迭代器遍历容器 list<int>::reverse_iterator rit = lt.rbegin(); while (rit != lt.rend()) { cout << *rit << " "; rit++; } cout << endl; return 0; }
五. list元素的获取
🌍fornt & back
int main() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); cout << lt.front() << endl; cout << lt.back() << endl; return 0; }
六. list的操作函数
⚡splice 转移
int main() { list<int> lt1(4, 2); list<int> lt2(4, 6); lt1.splice(lt1.begin(), lt2); //将容器lt2拼接到容器lt1的开头 for (auto e : lt1) { cout << e << " "; } cout << endl; //6 6 6 6 2 2 2 2 list<int> lt3(4, 2); list<int> lt4(4, 6); lt3.splice(lt3.begin(), lt4, lt4.begin()); //将容器lt4的第一个数据拼接到容器lt3的开头 for (auto e : lt3) { cout << e << " "; } cout << endl; //6 2 2 2 2 list<int> lt5(4, 2); list<int> lt6(4, 6); lt5.splice(lt5.begin(), lt6, lt6.begin(), lt6.end()); //将容器lt6的指定迭代器区间内的数据拼接到容器lt5的开头 for (auto e : lt5) { cout << e << " "; } cout << endl; //6 6 6 6 2 2 2 2 return 0; }
ps： 容器当中被拼接到另一个容器的数据在原容器当中就不存在了。（移植技术）
⚡remove
remove函数用于删除容器当中特定元素
int main() { list<int> lt; lt.push_back(1); lt.push_back(1); lt.push_back(1); lt.push_back(3); lt.push_back(2); lt.push_back(2); lt.push_back(1); lt.push_back(3); for (auto e : lt) { cout << e << " "; } cout << endl; //1 1 1 3 2 2 1 3 lt.remove(1); //删除容器当中值为1的元素 for (auto e : lt) { cout << e << " "; } cout << endl; return 0; }
⚡remove_if
remove_if函数用于删除容器当中满足条件的元素
bool single_digit(const int& val) { return val < 10; } int main() { list<int> lt; lt.push_back(10); lt.push_back(4); lt.push_back(7); lt.push_back(18); lt.push_back(2); lt.push_back(5); lt.push_back(9); for (auto e : lt) { cout << e << " "; } cout << endl; //10 4 7 18 2 5 9 lt.remove_if(single_digit); //删除容器当中值小于10的元素 for (auto e : lt) { cout << e << " "; } cout << endl; //10 18 return 0; }
⚡unique
unique函数用于删除容器当中连续的重复元素（前提是先排序）
int main() { list<int> lt; lt.push_back(1); lt.push_back(4); lt.push_back(3); lt.push_back(3); lt.push_back(2); lt.push_back(2); lt.push_back(3); for (auto e : lt) { cout << e << " "; } cout << endl; //1 4 3 3 2 2 3 lt.sort(); //升序 lt.unique(); for (auto e : lt) { cout << e << " "; } cout << endl; return 0; }
⚡sort
算法库里面已经有一个sort 了，为什么list里也实现了一个sort？
list的空间不是连续的，算法库中的sort要求物理空间要是连续的，所以vector和string才用，快排实现的参数取中，在链表实现不了
链表的sort是归并排序实现的
int main() { list<int> lt; lt.push_back(4); lt.push_back(7); lt.push_back(5); lt.push_back(9); lt.push_back(6); lt.push_back(0); lt.push_back(3); for (auto e : lt) { cout << e << " "; } cout << endl; //4 7 5 9 6 0 3 lt.sort(); //默认升序 for (auto e : lt) { cout << e << " "; } cout << endl; //0 3 4 5 6 7 9 return 0; }
