c++ list 详解
c++ list头文件
简介
list实际上是双向链表，故亦可称之为doubly-linked list
性质
双向
链表
双向
双向即给定一个元素，我们能够知道后一个元素和前一个元素
list的迭代器是双向迭代器
链表
优点：与向量(vectors)相比，它可以快速的插入和删除--插入和删除操作是常数时间的
缺点：随机访问比较慢--元素的访问不是常数时间的，获取元素往往需要在给定一个迭代器的基础上来通过遍历实现
时间复杂度
常数时间O(1)(与输入数据无关): 基本操作重复执行的次数是一个固定的常数，执行次数不存在变化，通俗的讲就是：无论n是什么值运算所花时间都一样
线性时间O(n)(与输入数据成正比): 基本操作重复执行的次数是与模块n成线性相关的，其值会随着模块n的变化而变化，当模块n的规模确定为定值后，其时间复杂度转化为O(1)
List
定义和初始化
list
lst1; // 创建空list list
lst2(6); //创建含有6个元素的list list
lst3(3, 2); // 创建含有三个元素的list list
lst4(lst2); // 使用ls2初始化ls4 list
lst5(lst2.begin(), lst2.end()); // 同ls4
list常用操作函数
lst1.assign() // 给list赋值
lst1.front() // 返回第一个元素
lst1.back() // 返回最后一个元素
lst1.begin() // 返回指向第一个元素的迭代器
lst1.end() // 返回末尾的迭代器
lst1.insert() // 插入一个元素到list中
lst1.erase() // 删除一个元素
lst1.pop_back() // 删除最有一个元素
lst1.pop_front() // 删除第一个元素
lst1.clear() // 删除所有元素
lst1.remove(const T & val) // 删除和val相等的元素
lst1.push_back() // 在list的末尾添加一个元素
lst1.push_front() // 在list的首部添加一个元素
lst1.empty() // 判断，若list为空返回true
lst1.max_size() // 返回list能容纳的最大元素数量
lst1.sort() // 给list排序(顺序)
list.reverse() // 把list中的元素倒转
lst1.merge(lst2) // 合并lst2到lst1，并清空lst2
lst1.unique() // 删除所有和前一个元素相等的元素
void splice(iterator i, list
& x, iterator first, iterator last) // 在位置i前面插入链表x中的区间 [first, last）, 并在链表x中删除该区间（链表自身和链表x可以是用一个链表，只要i不在 [first, last) 中即可
list案例
#include // 使用 list 需要包含此头文件
#include // 使用 STL 中的算法需要包含此头文件
#include
using namespace std;
class A
{
public:
A(int n_):n(n_){}
friend bool operator < (const A & a1, const A & a2);
friend bool operator == (const A & a1, const A & a2);
friend ostream & operator << (ostream & out, const A & a);
private:
int n;
};
bool operator < (const A & a1, const A & a2){
return a1.n < a2.n;
}
bool operator == (const A & a1, const A & a2){
return a1.n == a2.n;
}
ostream & operator << (ostream & out, const A & a){
out << a.n;
return out;
}
template
void Print(T first, T last)
{
for(; first != last; ++first)
cout<<*first<<" ";
cout< lst1(a, a+5), lst2(b, b+7);
lst1.sort(); // 顺序排序
cout<<"1. "; Print(lst1.begin(), lst1.end());
lst1.remove(2); // 删除所有和A(2)相等的元素
cout<<"2. "; Print(lst1.begin(), lst1.end());
lst2.pop_front(); // 删除第一个元素
cout<<"3. "; Print(lst2.begin(), lst2.end());
lst2.unique(); // 删除所有和前一个元素相等的元素
cout<<"4. "; Print(lst2.begin(), lst2.end());
lst2.sort(); // 顺序排序
lst1.merge(lst2); // 合并 lst2 到 lst1 并清空 lst2
cout<<"5. "; Print(lst1.begin(), lst1.end());
cout<<"6. "; Print(lst2.begin(), lst2.end()); // lst2 是空的
lst1.reverse(); // 将 lst1 倒置
cout<<"7. "; Print(lst1.begin(), lst1.end());
lst2.insert(lst2.begin(), a + 1, a + 4); // 在 lst2 中插入 3，2，4 三个元素
list::iterator p1, p2, p3;
p1 = find(lst1.begin(), lst1.end(), 30); // 查找元素
p2 = find(lst2.begin(), lst2.end(), 2);
p3 = find(lst2.begin(), lst2.end(), 4);
lst1.splice(p1, lst2, p2, p3); // 将 [p2, p3) 插入p1之前，并从lst2中删除 [p2, p3)
cout<<"8. "; Print(lst1.begin(), lst1.end());
cout<<"9. "; Print(lst2.begin(), lst2.end());
return 0;
}
1. 1 2 2 3 4
2. 1 3 4
3. 30 20 30 30 40 40
4. 30 20 30 40
5. 1 3 4 20 30 30 40
6.
7. 40 30 30 20 4 3 1
8. 40 2 30 30 20 4 3 1
9. 3 4
请按任意键继续. . .
【实例】用 list 解决约瑟夫问题
约瑟夫问题是：有 n 只猴子，按顺时针方向围成一圈选大王（编号为 1~n），从第 1 号开始报数，一直数到 m，数到 m 的猴子退到圈外，剩下的猴子再接着从 1 开始报数。就这样，直到圈内只剩下一只猴子时，这个猴子就是猴王。编程求输入 n、m 后,输出最后猴王的编号。
输入数据：每行是用空格分开的两个整数，第一个是 n，第二个是 m（0 输出要求：对于每行输入数据（最后一行除外），输出数据也是一行，即最后猴王的编号。 输入样例：6 212 48 30 0 输出样例：517 程序如下 erase 成员函数返回被删除元素后面那个元素的迭代器，如果被删除的是最后一个元素，则返回end()#include
#include
10000 3
2694
0 0
请按任意键继续. . .