C++中的list容器详解

C++中的list容器详解

1.list概述

list是C++ STL中的双向链表容器，支持在任何位置高效插入和删除元素。与vector和deque不同，list不提供随机访问能力，但提供了高效的插入和删除操作。

2. 基本特性

• 双向链表：每个元素包含指向前后元素的指针
• 高效插入/删除：在任何位置插入/删除都是O(1)O(1)O(1)时间复杂度
• 无随机访问：不支持下标操作，必须通过迭代器遍历
• 不连续存储：元素分散在内存中

3. 头文件与声明

#include<list>usingnamespacestd;list<int>lst1;// 空listlist<string>lst2(10);// 包含10个默认构造的stringlist<double>lst3(5,3.14);// 包含5个3.14list<char>lst4={'a','b','c'};// 初始化列表

4. 构造函数与初始化

4.1 默认构造

list<int>lst;

4.2 填充构造

list<int>lst(10);// 10个默认初始化的int(0)list<int>lst(5,100);// 5个100

4.3 范围构造

intarr[]={1,2,3};list<int>lst(arr,arr+3);

4.4 拷贝构造

list<int>lst2(lst1);

5. 容量操作

5.1size()

cout<<lst.size();// 返回元素数量

5.2empty()

if(lst.empty()){cout<<"List is empty";}

5.3max_size()

cout<<lst.max_size();// 返回list可容纳的最大元素数

5.4resize()

lst.resize(10);// 调整为10个元素，新增元素默认初始化lst.resize(15,5);// 调整为15个元素，新增元素初始化为5

6. 元素访问

6.1front()

lst.front()=5;// 修改第一个元素intfirst=lst.front();// 访问第一个元素

6.2back()

lst.back()=8;// 修改最后一个元素intlast=lst.back();// 访问最后一个元素

7. 修改操作

7.1push_back()

lst.push_back(10);// 在尾部插入10

7.2push_front()

lst.push_front(5);// 在头部插入5

7.3pop_back()

lst.pop_back();// 删除尾部元素

7.4pop_front()

lst.pop_front();// 删除头部元素

7.5insert()

autoit=lst.insert(lst.begin(),15);// 在头部插入15lst.insert(it,{1,2,3});// 在指定位置插入多个元素

7.6erase()

lst.erase(lst.begin());// 删除第一个元素lst.erase(lst.begin(),lst.end());// 删除所有元素

7.7clear()

lst.clear();// 清空所有元素

7.8swap()

list<int>lst2;lst.swap(lst2);// 交换两个list的内容

8. 特殊操作

8.1splice()

list<int>lst2={4,5,6};lst.splice(lst.end(),lst2);// 将lst2所有元素移动到lst尾部lst.splice(lst.begin(),lst2,lst2.begin());// 移动lst2的第一个元素

8.2remove()

lst.remove(5);// 删除所有值为5的元素

8.3remove_if()

lst.remove_if([](intn){returnn%2==0;});// 删除所有偶数

8.4unique()

lst.unique();// 删除连续重复元素

8.5merge()

list<int>lst2={4,5,6};lst.sort();lst2.sort();lst.merge(lst2);// 合并两个已排序list

8.6sort()

lst.sort();// 升序排序lst.sort(greater<int>());// 降序排序

8.7reverse()

lst.reverse();// 反转list

9. 迭代器

9.1begin()&end()

for(autoit=lst.begin();it!=lst.end();++it){cout<<*it<<" ";}

9.2rbegin()&rend()

for(autorit=lst.rbegin();rit!=lst.rend();++rit){cout<<*rit<<" ";// 反向遍历}

10. 完整示例

#include<iostream>#include<list>#include<algorithm>usingnamespacestd;intmain(){// 创建并初始化listlist<int>lst={2,3,4};// 头部和尾部操作lst.push_front(1);// 头部插入1lst.push_back(5);// 尾部插入5// 访问元素cout<<"First element: "<<lst.front()<<endl;cout<<"Last element: "<<lst.back()<<endl;// 插入元素autoit=next(lst.begin(),2);// 获取第3个位置的迭代器lst.insert(it,{7,8,9});// 在第3个位置插入7,8,9// 删除元素lst.pop_front();// 删除头部元素lst.remove(8);// 删除所有8// 特殊操作list<int>lst2={10,11,12};lst.splice(lst.end(),lst2);// 合并lst2到lstlst.sort();// 排序lst.unique();// 去重// 遍历listcout<<"All elements: ";for(intnum:lst){cout<<num<<" ";}cout<<endl;// 容量信息cout<<"Size: "<<lst.size()<<endl;cout<<"Is empty: "<<(lst.empty()?"Yes":"No")<<endl;return0;}

11. 性能提示

1. 在任何位置插入/删除元素性能都很好(O(1)O(1)O(1))
2. 查找元素需要遍历(O(n)O(n)O(n))
3. 迭代器在插入/删除操作后仍然有效(除非删除的是迭代器指向的元素)
4. 适合频繁插入/删除但不需随机访问的场景