list双向链表容器
list容器实现了双向链表的数据结构
list的头节点的前驱元素指针域保存的是链表中尾元素的首地址，而list的尾节点的后继元素指针域则保存了头节点的首地址，这样，就构成了一个双向循环链。
由于list对象的节点并不要求在一段连续的内存中，所以，对于迭代器，只能通过“++”或“- -”的操作将迭代器移动到后继/前驱节点元素处。
而不能对迭代器进行+n或-n的操作，这点，是与vector等不同的地方。
头文件包含: “#include <list>”
使用
创建list对象
- 创建空链表，如：
//创建空链表 list<int> l;
- 创建具有n个元素的链表
#include<iostream> #include<list> using namespace std; int main(){ //创建空链表 //list<int> l; //创建具有10元素的链表 list<int> l(10); return 0; }
元素插入和遍历
有三种方法往链表里插入新元素
- 采用push_back()方法往尾部插入新元素，链表自动扩张。
- 采用push_front()方法往首部插入新元素，链表自动扩张。
- 采用insert()方法往迭代器位置处插入新元素，链表自动扩张。
- 注意，迭代器只能进行“++”或“- -”操作，不能进行+n或-n的操作
- 采用前向迭代器iterator对链表进行遍历。
#include<iostream> #include<list> using namespace std; int main(){ //创建空链表 list<int> l; l.push_back(1); l.push_back(2); l.push_back(3); //前向遍历 list<int>::iterator it; for(it = l.begin();it!=l.end();it++){ cout<<*it<<endl; } return 0; }
反向遍历
采用反向迭代器reverse_iterator对链表进行反向遍历。
//反向遍历 list<int>::reverse_iterator rit; for(rit = l.rbegin();rit!=l.rend();rit++){ cout<<*rit<<endl; }
元素删除
- 可以使用remove()方法删除链表中一个元素，值相同的元素都会被删除。
//删除值为1的所有元素 l.remove(1);
- 使用pop_front()方法删除链表首元素
使用pop_back()方法删除链表尾元素。
//删除首元素 l.pop_front(); //删除尾元素 l.pop_back();
- 使用erase()方法删除迭代器位置上的元素。
l.erase(l.begin());
- 使用clear()方法清空链表。
l.clear();
- 打印链表元素个数
cout<<l.size()<<endl;
元素查找
采用find()查找算法可以在链表中查找元素，如果找到该元素，返回的是该元素的迭代器位置；
如果没有找到，则返回end()迭代器位置。
find()算法需要声明头文件包含语句“#include <algorithm>”。
//采用find()查找算法在链表中查找 list<int>::iterator it; it = find(l.begin(),l.end(),1); if(it != l.end()){ cout<<"find it"<<endl; }else{ cout<<"can not find it"<<endl; }
元素排序
- 采用sort()方法可以对链表元素进行升序排列。
//使用sort()方法对链表排序，是升序排列 l.sort();
剔除连续重复元
采用unique()方法可以剔除连续重复元素，只保留一个。
//剔除连续重复元素（只保留一个） l.unique();
