双向链表 lru（C++ STL 容器技术 之 list双向链表容器_断了路梦在天上_百度空间）
简介：
list是双向链表的一个泛化容器 ，它的数据元素可通过链表指针串接成逻辑意义上的线性表 。不同于采用线性表顺序存储结构的vector和deque容器 ，list双向链表中任一位置的元素查找 、插入和删除 ，都具有高效的常数阶算法时间复杂度O(1) 。
list应用基础：
创建list对象：
1 、list(const A& a=A()) 创建一个空的list对象 。
如：list<int> l;
2 、list(size_type n) 创建一个具有n个元素的list对象 ，每个list元素具有它的类型下的默认值 。
如：list<int> l(10);
3 、list(size_type n, const T& value) 创建一个具有n个元素的list对象 ，每个元素具有初始值value 。
如：list<int> l(10, 5);
4 、list(const list&) 通过拷贝一个list对象的各个元素值 ，创建一个新的list对象 。
如：list<int> l1(10, 5); list<int> l2(l1);
5 、list(const InputIterator first, const InputIterator last, const A& a=A()) 通过拷贝迭代器区间[first, last)的元素值 ，创建一个新的list对象中 ，内存分配器可省略 。
如：int iArray[] = {1,2,3}; list<int> l(iArray, iArray+3);
初始化赋值：
list提供的push_back函数常用来进行list容器的初始化 ，push_back函数在容器的尾端插入新元素value 。
void push_back(const T& value)
元素的遍历访问：
由于链表中的数据需要一个个元素进行遍历 ，因此list元素的遍历只使用迭代器的方式进行 。
元素的插入：
由于list链表元素的插入不需要对其他元素进行移位拷贝 ，因此 ，list的元素插入函数具有常数阶的O(1)算法复杂度 。除了push_back函数在尾部添加元素外 ，list还有在链首插入元素的push_front函数和在任意迭代器位置插入的insert函数 。
iterator insert(iterator pos, const T& x)
void push_front(const T&)
元素的删除：
iterator erase(iterator pos) 删除迭代器pos所指的链表元素
iterator erase(iterator first, iterator last) 删除迭代器区间[first, last)的所有链表元素
void clear() 删除所有链表元素
void pop_front() 删除list的第一个链表元素
void pop_back() 删除list的最后一个链表元素
void remove(const T& value) 删除list链表中所有元素值为value的元素
元素的反向遍历：
reverse_iterator rbegin()
reverse_iterator rend()
list的交换：
list容器的swap函数 ，通过简单地交换两个list的头指针 ，来实现list元素的交换 。
void swap(list&)
list的归并：
void splice(iterator position, list& x) 将x的链表归并到当前list链表的position位置之前 ，list对象x将被清空 。
void splice(iterator position, list&, iterator i) 将一个list的迭代器i值所指的元素 ，归并到当前list链表中 ，并将归并的元素从原链表中删除 。
void merge(list& x) 将list对象x的链表归并到当前list链表中 ，并清空x链表 。只有当前链表和被归并的x链表的元素均预先按元素值的"<"关系排好序 ，merge函数才具有意义 ，归并后的链表元素也是按"<"关系排序的 。
list的元素排序：
list提供的void sort函数 ，按"<"关系进行list链表的元素排序 ，较小的元素排在前面 。
list的连续重复元素的删除：
利用list的void unique函数 ，可将连续重复的元素删除 ，仅保留一个 。
举例分析：
1 、
//插入list链表元素
#include <list>
#include <iostream>
using namespace std;
int main(void)
{
list<int> l;
l.push_back(6);
l.push_back(8);
l.push_back(9);
//插入链表元素
list<int>::iterator i, iend;
i = l.begin();
i++;
l.insert(i, 7);
l.push_front(5);
//打印链表元素
iend = l.end();
for (i=l.begin(); i!=iend; i++)
cout << *i << " ";
return 0;
}
2 、
//list链表元素的删除
#include <list>
#include <iostream>
using namespace std;
int main(void)
{
list<int> l;
l.push_back(5);
l.push_back(6);
l.push_back(7);
l.push_back(8);
l.push_back(9);
l.push_back(9);
l.push_back(9);
l.push_back(10);
//删除元素,剩下7 、8和9
list<int>::iterator i, iend;
i = l.begin();
i++;
l.erase(i);
l.pop_back();
l.pop_front();
l.remove(9);
//打印
iend = l.end();
for (i=l.begin(); i!=iend; i++)
{
cout << *i << " ";
}
return 0;
}
3 、
//list链表的归并
#include <list>
#include <iostream>
using namespace std;
void print(list<int>& l)
{
list<int>::iterator i, iend;
iend = l.end();
for (i=l.begin(); i!=iend; i++)
{
cout << *i << " ";
}
}
int main(void)
{
list<int> l;
for (int j=1; j<=10; j++)
{
l.push_back(j);
}
//splice()函数
list<int> carry;
carry.splice(carry.begin(), l, l.begin());
//打印carry
cout << "carry的链表元素为: ";
print(carry);
cout << endl;
//打印l
cout << "l的链表元素为: ";
print(l);
cout << endl;
//merge()函数用法
list<int> x;
x.push_back(30);
x.push_back(31);
x.push_back(32);
l.merge(x);
//打印x
cout << "x的链表元素为: 空";
print(x);
cout << endl;
//打印l
cout << "l的链表元素为: ";
print(l);
cout << endl;
return 0;
}
4 、
//list链表元素的排序
#include <list>
#include <iostream>
using namespace std;
void print(list<int>& l)
{
list<int>::iterator i, iend;
iend=l.end();
for (i=l.begin(); i!=iend; i++)
cout << *i << " ";
cout << endl;
}
int main(void)
{
list<int> l;
for(int j=18; j>=0; j--)
l.push_back(j);
cout << "排序前: ";
print(l);
//调用list<int>::sort()函数排序
l.sort();
cout << "排序后: ";
print(l);
return 0;
}
5 、
//list连续重复元素的删除
#include <list>
#include <iostream>
using namespace std;
int main(void)
{
list<int> l;
l.push_back(6);
l.push_back(8);
l.push_back(6);
l.push_back(6);
l.push_back(6);
l.push_back(9);
l.push_back(13);
l.push_back(6);
l.unique();
list<int>::iterator i, iend;
iend = l.end();
for (i=l.begin(); i!=iend; i++)
cout << *i << " ";
cout << endl;
return 0;
}
创心域SEO版权声明：以上内容作者已申请原创保护，未经允许不得转载，侵权必究！授权事宜、对本内容有异议或投诉，敬请联系网站管理员，我们将尽快回复您，谢谢合作！