一、list的介绍和使用
1、list的介绍
list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代
list的底层是双向链表结构，双向链表中每个元素存储在互不相关的节点中，在节点中通过指针与前一个和后一个元素建立联系
list的优点是在任意位置进行插入和移除元素执行效率高，缺点就是不能支持随机访问
2、list的使用
（1）list的构造
构造函数 | 接口说明 |
|---|---|
list(size_type n,const value_type& val = value_type()) | 构造的list中包含n个值为val的元素 |
list() | 构造空list |
list(const list& x) | 拷贝构造函数 |
list(InputIterator first,InputIterator last) | 用迭代器区间中的元素构造list |
void test1()
{
list<int> lt1(10, 1);
list<int> lt2;
list<int> lt3(lt1);
list<int> lt4(lt1.begin(), lt1.end());
for (auto e : lt1)
{
cout << e << " ";
}
cout << endl;
for (auto e : lt3)
{
cout << e << " ";
}
cout << endl;
for (auto e : lt4)
{
cout << e << " ";
}
cout << endl;
}构造函数、拷贝构造函数正常
这里的lt2还有原始视图是空构造
（2）list 迭代器的使用
函数声明 | 接口说明 |
|---|---|
begin和end | 返回第一个元素的迭代器为begin和返回最后一个元素下一个位置的迭代器为end |
rbegin和rend | 返回第一个元素的迭代器为end和返回最后一个元素下一个位置的迭代器为begin |
值得注意的是，rbegin和rend为反向迭代器，对迭代器执行 操作，迭代器向前移动，也就是说forward_list也就是单链表是没有rbegin和rend迭代器的
代码语言：javascript复制void test2()
{
list<int> lt1(10, 0);
auto it = lt1.begin();
int i = 1;
for (auto& e : lt1)
{
e = i;
i ;
}
for (auto e : lt1)
{
cout << e << " ";
}
cout << endl;
}
（3）list 容量的使用
函数声明 | 接口说明 |
|---|---|
empty | 检测list是否为空 |
size | 返回list中节点的有效个数 |
void test3()
{
list<int> lt1(10, 0);
list<int> lt2;
cout << lt1.empty() << " ";
cout << lt1.size() << endl;
cout << lt2.empty() << " ";
cout << lt2.size() << endl;
}
（4）list元素访问
函数声明 | 接口说明 |
|---|---|
front | 返回list第一个节点值的引用 |
back | 返回list最后一个节点值的引用 |
void test4()
{
list<int> lt1(10, 0);
lt1.front() = 1;
lt1.back() = 2;
for (auto e : lt1)
{
cout << e << " ";
}
cout << endl;
}
（5）list修改
函数声明 | 接口说明 |
|---|---|
push_front | 在list第一个元素之前插入一个元素 |
pop_front | 删除list第一个元素 |
push_back | 在list最后一个元素之后插入一个元素 |
pop_back | 删除list最后一个元素 |
insert | 在pos位置插入一个元素 |
erase | 删除pos位置的元素 |
swap | 交换两个list中的元素 |
clear | 清空list中的有效元素 |
void test5()
{
list<int> lt1(10, 0);
//插入
lt1.push_front(1);
lt1.push_back(2);
for (auto e : lt1)
{
cout << e << " ";
}
cout << endl;
//删除
lt1.pop_front();
lt1.pop_back();
for (auto e : lt1)
{
cout << e << " ";
}
cout << endl;
int i = 1;
for (auto& e : lt1)
{
e = i;
i ;
}
//insert/erase
auto it = find(lt1.begin(), lt1.end(), 5);
lt1.insert(it, 11);
lt1.erase(it);
for (auto e : lt1)
{
cout << e << " ";
}
cout << endl;
//swap
list<int> lt2(10, 1);
lt1.swap(lt2);
for (auto e : lt2)
{
cout << e << " ";
}
cout << endl;
//clear
lt1.clear();
cout << lt1.empty() << endl;
}
使用方面都挺简单的，不再叙述了，参数直接查cplusplus就行
（6）list迭代器失效
因为list的底层结构为带头节点的双向循环链表，所以在list中进行插入是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他的迭代器不受影响
二、list与vector的对比
list和vector都是STL中重要的序列式容器，二者在接口上基本相同，但在底层实现上有巨大的差异，我们来对比一下
对比 | vector | list |
|---|---|---|
底层结构 | 动态顺序表，一段连续空间 | 带头节点的双向循环列表 |
随机访问 | 支持随机访问，访问某个元素效率O(1) | 不支持随机访问，访问某个元素效率O(N) |
插入和删除 | 任意位置插入和删除效率低，需要移动元素，时间复杂度为O(N)，插入时有可能需要增容，开辟新空间，拷贝元素，释放旧空间，导致效率更低 | 任意位置插入和删除效率高，不需要移动元素，时间复杂度为O(1) |
空间利用率 | 底层为连续空间，不容易造成内存碎片，空间利用率高，缓存利用率高 | 底层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低 |
迭代器 | 原生态指针 | 对原生态指针进行封装 |
迭代器失效 | 在插入元素时，要给所有的迭代器重新赋值，因为插入元素有可能会导致重新扩容，致使原来迭代器失效，删除时，当前迭代器需要重新赋值否则会失效 | 插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响 |
使用场景 | 需要高效存储，支持随机访问，不关心插入删除效率 | 大量的插入和删除操作，不关心随机访问 |
两者使用场景不同，各有千秋，在使用的时候合理搭配，就可以发挥最大价值
三、list其他接口
在图中可以看到，list除了常用的几种接口以外，还有其他的功能的接口，这里简单介绍一下，学习还需要到cplusplus网站上详细参考参数返回值以及一系列的内容
1、splice
将某个list移动到另一个容器当中，有三种方式：一是将list中的所有元素都传输到容器中，二是仅将迭代器指向的元素从list传输到另一个容器当中，第三个就是迭代器范围传输，从first迭代器到last迭代器的元素传输到另一个容器当中
代码语言：javascript复制void test6()
{
list<int> lt1(10, 0);
list<int> lt2(10, 1);
lt1.splice(lt1.begin(),lt2);
for (auto e : lt1)
{
cout << e << " ";
}
}
2、remove
与erase可以相比较，它们都是删除接口，而erase的参数是一个迭代器，而remove的参数是一个值，它的作用是删除所有等于某个值的元素，然后调整容器大小
代码语言：javascript复制void test7()
{
list<int> lt1(10, 0);
int i = 1;
for (auto& e : lt1)
{
e = i;
i ;
}
for (auto e : lt1)
{
cout << e << " ";
}
cout << endl;
lt1.remove(5);
for (auto e : lt1)
{
cout << e << " ";
}
}
3、unique
删除连续相等的除了一个以外的元素
代码语言：javascript复制void test8()
{
list<int> lt1(10, 0);
list<int> lt2(10, 1);
lt1.splice(lt1.begin(), lt2);
for (auto e : lt1)
{
cout << e << " ";
}
cout << endl;
lt1.unique();
for (auto e : lt1)
{
cout << e << " ";
}
}
4、sort
代码语言：javascript复制void test9()
{
list<int> lt1(10, 0);
int i = 10;
for (auto& e : lt1)
{
e = i;
i--;
}
for (auto e : lt1)
{
cout << e << " ";
}
cout << endl;
lt1.sort();
for (auto e : lt1)
{
cout << e << " ";
}
}
今日分享就到这了~
