文章目录
STL常用容器—— list 容器的使用
1、 list 容器介绍
list容器简介
list 容器：又称双向链表容器，该容器的底层是以双向链表的形式实现的，因此可以高效地进行元素的插入和删除操作。
双向链表可以将链表里的元素存储在不同且不相关的内存位置，所以list 容器中的元素可以是分散存储在内存空间里的，而不是必须存储在一整块连续的内存空间中。
在双向链表的任何位置插入或删除元素时间复杂度为都为O(1)；list 容器移动元素的效率也比其它容器高。
list容器底层实现
双向链表的各个节点中不仅存储元素的值，还包含两个指针（头指针和尾指针），分别指向该元素的前一个节点和后一个节点，
list 容器各元素占用的节点是独立的、分散的，它们之间的线性关系通过指针来维持。
双向链表第一个元素的头指针总为空指针，因为它前面没有元素；双向链表的最后一个元素的尾指针也总为空指针。
list容器的优缺点
优点：
- 采用动态内存分配，不会造成内存浪费和溢出
- 链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素
缺点：
- 不能随机访问元素。只能顺序访问，额外耗费较大
2、list容器的构造函数
默认构造
语法：list<T> values;
创建一个int类型的空 list 容器：
list<int> l;
赋值构造
语法1：list<T> values(n); 创建一个包含 n 个元素的 list 容器，每个元素的值都为相应类型的默认值
语法2：list<T> values(n,elem); 创建一个包含 n 个元素的 list 容器，每个元素的初始值为elem
list<int> L2(6);
list<int> L3(6,8);
拷贝相同类型构造
语法：list<T> value2(const list &lst); 里外容器存储的元素类型要一致
list<int> L3(6,8);
list<int> L4(L3);
拷贝不同类型构造
拷贝其他类型容器（或者普通数组）中指定区间内的元素，可以创建新的 list 容器
代码实例：
#include<iostream>
using namespace std;
#include<list>
#include<array>
void printList(const list<int>& L)
{
for (list<int>:: const_iterator it = L.begin();it != L.end(); it++)
{
cout << *it << " ";
}
cout << endl;
}
void test1(){
//默认构造
list<int> L1;
printList(L1);
//赋值构造
list<int> L2(6);
printList(L2);
list<int> L3(6,8);
printList(L3);
//拷贝构造
list<int> L4(L3);
printList(L4);
//拷贝普通数组，创建list容器
int a[] = { 1,2,3,4,5 };
list<int> L5(a, a + 4);
printList(L5);
//拷贝其它类型的容器，创建 list 容器
array<int, 5> arr{ 11,12,13,14,15 };
list<int> L6(arr.begin() + 2, arr.end());
printList(L6);
}
int main()
{
test1();
system("pause");
return 0;
}
3、list容器的赋值和交换
| 成员函数 | 功能 |
|---|---|
| list& operator=(const list &lst) | 重载等号操作符 |
| assign(n,elem) | 将n个elem元素替换掉容器中原有内容 |
| assign(beg ,end) | 将[ beg,end )区间中的元素替换掉容器中原有内容 |
| swap(list) | 将list与本身容器的元素互换，必须保证两个容器中存储的元素类型是相同的 |
代码实例：
#include<iostream>
using namespace std;
#include<list>
void printList(const list<int>& L)
{
for (list<int>:: const_iterator it = L.begin();it != L.end(); it++)
{
cout << *it << " ";
}
cout << endl;
}
void test1(){
//默认构造
list<int> L1;
list<int> L2;
list<int> L3;
list<int> L4;
for (int i = 0; i < 10; i++)
{
L1.push_back(i);
}
printList(L1);
L2 = L1;
printList(L2);
L3.assign(6, 8);
printList(L3);
L4.assign(L2.begin() , L2.end());
printList(L4);
L4.swap(L3);
printList(L4);
}
int main()
{
test1();
system("pause");
return 0;
}
4、list容器大小操作
| 成员函数 | 功能 |
|---|---|
| size() | 返回当前容器实际包含的元素个数。 |
| max_size() | 返回容器所能包含元素个数的最大值。 |
| empty() | 判断容器中是否有元素，若无元素，则返回 true；反之，返回 false。 |
| resize(num) | 重新指定容器的长度为num，如果容器变长，以对应类型的默认值填充，如果容器变短，超出容器长度的元素被删除 |
| resize(num，elem) | 重新指定容器的长度为num，如果容器变长，以elem填充，如果容器变短，超出容器长度的元素被删除 |
代码实例
#include<iostream>
using namespace std;
#include<list>
void printList(const list<int>& L)
{
for (list<int>:: const_iterator it = L.begin();it != L.end(); it++)
{
cout << *it << " ";
}
cout << endl;
}
void test1(){
//默认构造
list<int> L1;
list<int> L2;
for (int i = 0; i < 10; i++)
{
L1.push_back(i);
}
cout << "list.size:" << L1.size() << endl;
if (L2.empty())
{
cout << "L2容器为空" << endl;
}
L1.resize(13);
printList(L1);
L2.resize(12,6);
printList(L2);
}
int main()
{
test1();
system("pause");
return 0;
}
5、list容器添加和删除元素操作
| 成员函数 | 功能 |
|---|---|
| push_front() | 在容器头部添加一个元素 |
| pop_front() | 删除容器第一个元素 |
| push_back() | 在容器尾部添加一个元素 |
| pop_back() | 删除容器最后一个元素 |
| insert(pos,elem) | 在pos位置插入elem元素，返回新元素的位置 |
| insert(pos,n,elem) | 在pos位置插入n个elem元素，无返回值 |
| insert(pos,beg,end) | 在pos位置插入[ beg,end )区间的元素，无返回值 |
| erase(pos) | 删除pos位置的元素，返回下一个元素的位置 |
| erase(beg,end) | 删除[ beg,end)区间的元素，返回下一个元素的位置 |
| clear() | 移除容器存储的所有元素 |
| remove(elem) | 删除容器中所有与elem值匹配的元素 |
代码实例：
#include<iostream>
using namespace std;
#include<list>
void printList(const list<int>& L) {
for (list<int>::const_iterator it = L.begin(); it != L.end(); it++) {
cout << *it << " ";
}
cout << endl;
}
void test01() {
list<int> L1;
//尾插
L1.push_back(10);
L1.push_back(20);
L1.push_back(30);
//头插
L1.push_front(3);
L1.push_front(2);
L1.push_front(1);
printList(L1);
//尾删
L1.pop_back();
//头删
L1.pop_front();
printList(L1);
//insert插入
L1.insert(L1.begin(), 100);
printList(L1);
L1.insert(L1.begin(), 3, 6);
printList(L1);
list<int> L2;
L2.assign(2, 1);
printList(L2);
L2.insert(L2.end(), L1.begin(), L1.end());
printList(L2);
//移除元素
L2.remove(1);
printList(L2);
//删除全部元素
L2.erase(L2.begin(), L2.end());
printList(L2);
//删除单个位置元素
L1.erase(L1.begin());
cout << "删除it位置后的L1：" << endl;
printList(L1);
//移除所有元素
L1.clear();
printList(L1);
}
int main() {
test01();
system("pause");
return 0;
}
6、list容器数据存取
list 容器不支持随机访问，未提供下标操作符 [] 和 at() 成员函数，也没有提供 data() 成员函数。
只能使用 front() 和 back() 成员函数，或者使用 list 容器迭代器访问或修改元素的值。
使用 front() 和 back() 成员函数
| 成员函数 | 功能 |
|---|---|
| front() | 返回第一个元素的引用。 |
| back() | 返回最后一个元素的引用。 |
#include <iostream>
#include <list>
using namespace std;
int main()
{
list<int> L1{ 1,2,3,4 };
//获取元素
int& first = L1.front();
int& last = L1.back();
cout << first << " " << last << endl;
//修改元素
first = 11;
last = 22;
cout << L1.front() << " " << L1.back() << endl;
system("pause");
return 0;
}
使用 list 容器迭代器
#include <iostream>
#include <list>
using namespace std;
int main()
{
list<int> L1{ 1,2,3,4,5 };
auto it = L1.begin();
cout << *it << " ";
++it;
while (it != L1.end())
{
cout << *it << " ";
++it;
}
system("pause");
return 0;
}
注意：list容器的迭代器类型为双向迭代器，而不是和之前的array、vector容器一样是随机访问迭代器。
双向迭代器特性：假如L1，L2都是双向迭代器，那么
-
支持 ++L1、 L1++、 L1–、 L1++、 *L1、 L1==L2以及 L1!=L2
-
不支持 L1[i]、L1-=i、 L1+=i、 L1+i 、L1-i、L1<L2、 L1>L2、 L1<=L2、 L1>=L2
7、list容器反转和排序
| 成员函数 | 功能 |
|---|---|
| sort() | 链表排序，默认升序 |
| reverse() | 反转链表 |
代码实例：
#include<iostream>
using namespace std;
#include<algorithm>
#include<list>
void printList(const list<int>& l) {
for (list<int>::const_iterator it = l.begin(); it != l.end(); it++) {
cout << *it << " ";
}
cout << endl;
}
bool myCompare(int v1, int v2) {
return v1 > v2;
}
void test01() {
list<int> L1;
L1.push_back(10);
L1.push_back(2);
L1.push_back(30);
L1.push_front(3);
L1.push_front(20);
L1.push_front(1);
printList(L1);
//反转链表
L1.reverse();
printList(L1);
//排序 默认升序
L1.sort();
printList(L1);
//排序 降序
L1.sort(myCompare);
printList(L1);
}
int main() {
test01();
system("pause");
return 0;
}
