c++ list 详解

若尘

关注

发布于: 1 小时前

c++ list 头文件

简介

list 实际上是双向链表，故亦可称之为 doubly-linked list
性质
双向
链表

双向

双向即给定一个元素，我们能够知道后一个元素和前一个元素
list 的迭代器是双向迭代器

链表

优点：与向量(vectors)相比，它可以快速的插入和删除--插入和删除操作是常数时间的
缺点：随机访问比较慢--元素的访问不是常数时间的，获取元素往往需要在给定一个迭代器的基础上来通过遍历实现
时间复杂度
常数时间 O(1)(与输入数据无关): 基本操作重复执行的次数是一个固定的常数，执行次数不存在变化，通俗的讲就是：无论 n 是什么值运算所花时间都一样
线性时间 O(n)(与输入数据成正比): 基本操作重复执行的次数是与模块 n 成线性相关的，其值会随着模块 n 的变化而变化，当模块 n 的规模确定为定值后，其时间复杂度转化为 O(1)

List

定义和初始化

list<int>lst1; // 创建空 list
list<int>lst2(6); //创建含有 6 个元素的 list
list<int>lst3(3, 2); // 创建含有三个元素的 list
list<int>lst4(lst2); // 使用 ls2 初始化 ls4
list<int>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<T> & x, iterator first, iterator last) // 在位置 i 前面插入链表 x 中的区间 [first, last）, 并在链表 x 中删除该区间（链表自身和链表 x 可以是用一个链表，只要 i 不在 [first, last) 中即可

list 案例

#include <list>  // 使用 list 需要包含此头文件#include <algorithm>  // 使用 STL 中的算法需要包含此头文件#include <iostream>  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 <class T>void Print(T first, T last){  for(; first != last; ++first)    cout<<*first<<" ";  cout<<endl;}
int main(){  A a[5] = {1, 3, 2, 4, 2};  A b[7] = {10, 30, 20, 30, 30, 40, 40};  list<A> 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<A>::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 42. 1 3 43. 30 20 30 30 40 404. 30 20 30 405. 1 3 4 20 30 30 406.7. 40 30 30 20 4 3 18. 40 2 30 30 20 4 3 19. 3 4请按任意键继续. . .

复制代码

【实例】用 list 解决约瑟夫问题

约瑟夫问题是：有 n 只猴子，按顺时针方向围成一圈选大王（编号为 1~n），从第 1 号开始报数，一直数到 m，数到 m 的猴子退到圈外，剩下的猴子再接着从 1 开始报数。就这样，直到圈内只剩下一只猴子时，这个猴子就是猴王。编程求输入 n、m 后,输出最后猴王的编号。

输入数据：每行是用空格分开的两个整数，第一个是 n，第二个是 m（0<m, n<=1 000 000）。最后一行是：0 0

输出要求：对于每行输入数据（最后一行除外），输出数据也是一行，即最后猴王的编号。

输入样例：6 212 48 30 0

输出样例：517

程序如下

#include <list>#include <iostream>using namespace std;
int main(){  list<int> monkeys;  int n, m;  while(1)  {    cin >> n >> m;    if(n == 0 && m == 0)      break;    monkeys.clear();  // 清空list容器    for(int i = 0; i <= n; ++ i)  // 将猴子的编号放入list中      monkeys.push_back(i);    list<int>::iterator it = monkeys.begin();  // 定义一个迭代器    while(monkeys.size() > 1)  // 只要还有不止一只猴子，就要找一只猴子让其出列    {        for(int i = 1; i < m; ++ i)  // 报数      {        ++it;        if(it == monkeys.end())          it = monkeys.begin();      }      it = monkeys.erase(it);  // 删除元素后，迭代器失效                               // 要重新让迭代器指向被删元素的后面      if(it == monkeys.end())        it = monkeys.begin();    }    cout<<monkeys.front()<<endl;  // front返回第一个元素的引用  }  return 0;}

复制代码

10000 326940 0请按任意键继续. . .

复制代码

erase 成员函数返回被删除元素后面那个元素的迭代器，如果被删除的是最后一个元素，则返回 end()

发布于: 1 小时前阅读数: 3

原文链接:【http://xie.infoq.cn/article/b9e3fd65261629cb032a889ec】。文章转载请联系作者。

若尘

关注

还未添加个人签名 2021.01.11 加入

还未添加个人简介

发布

暂无评论

创作场景

c++ list 详解

c++ list 头文件

简介

双向

链表

时间复杂度

List

定义和初始化

list 常用操作函数

list 案例

【实例】用 list 解决约瑟夫问题

若尘

评论