EdwardWong
2022/12/01阅读：23主题：姹紫
STL序列型容器之list容器
STL的list容器，又称双向链表容器，即该容器的底层是以双向链表的形式实现的。 list容器中的元素可以分散的存储在内存空间中，而不是必须存储在一整块连续的内存空间中。
list容器中各个元素的前后顺序是靠指针来维系的，每个元素配备了2个指针，分别指向它的前一个元素和后一个元素。其中第一个元素的前向指针总为null，尾部元素的后向指针也总为null.
list容器可以在快速的以O（1）的时间复杂度插入或删除元素。但是其不能像array和vector那样快速的随机访问元素，只能从容器中第一个元素或者最后一个元素开始遍历容器，直到找到该位置。
list容器以模板类list<T>的形式在<list>头文件中，并且位于std命名空间中，因此使用该容器前，应该包含以下两行代码：
#include<list>
using namespace std;
list容器的创建
创建空的容器
std::list<int> values;
和array容器不同，空的list容器在创建之后仍然可以添加元素。
创建包含n个元素的list容器
std::list<int> values(10);
创建包含n个元素的list容器并指定初值‘
std::list<int> values(10,5)
通过已有list创建新的list容器
std::list<int> values(10);
std::list<int> value2(value1);
需要保证新旧容器存储的元素类型一致。
通过拷贝其他容器或普通数组（可以看作容器）中指定的元素来创建list容器
//拷贝普通数组，创建list容器
int a[] = { 1,2,3,4,5 };
std::list<int> values(a, a+5);
//拷贝其它类型的容器，创建 list 容器
std::array<int, 5>arr{ 11,12,13,14,15 };
std::list<int>values(arr.begin()+2, arr.end());//拷贝arr容器中的{13,14,15}
list可用的成员函数
sort()函数默认升序排序。
#include <iostream>
#include <list>
using namespace std;
int main()
{
//创建空的 list 容器
std::list<double> values;
//向容器中添加元素
values.push_back(3.1);
values.push_back(2.2);
values.push_back(2.9);
cout << "values size：" << values.size() << endl;
//对容器中的元素进行排序
values.sort();
//使用迭代器输出list容器中的元素
for (std::list<double>::iterator it = values.begin(); it != values.end(); ++it) {
std::cout << *it << " ";
}
return 0;
}
注意双向迭代器不支持
<进行比较，且不能支持用下标随机访问元素。
STL list迭代器及用法
list容器迭代器与之前的vector,deque、array最大的不同在于，list容器配备的迭代器类型为双向迭代器，而不是是随机访问迭代器。
双向迭代器支持使用++p1、p1++、p1--、p1--、*p1、p1==p2以及p1!=p2（逻辑运算符）运算符，但不支持以下操作：
-
p1[i]: 不能通过下标访问
list容器中指定位置处的元素。 -
p1-=i、p1+=i、p1+i、p1-i:双向迭代器
p1不支持-=、+=、+、-运算符。 -
p1<p2、p1>p2、p1<=p2、p1>=p2：双向迭代器不支持<、>、<=、>=比较运算符
#include <iostream>
#include <list>
using namespace std;
int main()
{
//创建 list 容器
std::list<char> values{'h','t','t','p',':','/','/','c','.','b','i','a','n','c','h','e','n','g','.','n','e','t'};
//使用begin()/end()迭代器函数对输出list容器中的元素
for (std::list<char>::iterator it = values.begin(); it != values.end(); ++it) {
std::cout << *it;
}
cout << endl;
//使用 rbegin()/rend()迭代器函数输出 lsit 容器中的元素
for (std::list<char>::reverse_iterator it = values.rbegin(); it != values.rend();++it) {
std::cout << *it;
}
return 0;
}
注意程序中用到的是
!=逻辑运算符，而不是<等比较运算符。在实际应用中可以使用auto代替std::list<char>::iterator
list容器在进行插入（insert），结合(splice)等操作时，都不会造成原有的list迭代器失效，甚至删除操作，而只有指向被删除元素的元素的迭代器失效，其他迭代器不受任何影响。
#include <iostream>
#include <list>
using namespace std;
int main()
{
//创建 list 容器
std::list<char> values{'h','t','t','p',':','/','/','c','.','b','i','a','n','c','h','e','n','g','.','n','e','t'};
//创建 begin 和 end 迭代器
std::list<char>::iterator begin = values.begin();
std::list<char>::iterator end = values.end();
//头部和尾部插入字符 '1'
values.insert(begin, '1');
values.insert(end, '1');
while (begin != end)
{
std::cout << *begin;
++begin;
}
return 0;
}
可以看出，在进行插入操作之后，仍使用先前创建的迭代器遍历容器，虽然程序不会出错，但是可能会由于插入位置的不同，会遗漏新插入的元素。
list容器的底层存储结构
对于list容器，有的容器采用双向链表实现，有些使用循环链表。
list容器的节点结构
双向链表的各个节点中存储的不仅仅是元素的值，还包含2个指针，分别指向前一个元素和后一个元素。
template<typename T,...>
struct __List_node{
//...
__list_node<T>* prev;
__list_node<T>* next;
T myval;
//...
}
其中prev指针指向前一个节点，next指向后一个节点，myval用于存储当前元素的值。
list容器迭代器的实现
和array、vector这些容器迭代器的实现方式不同，由于list容器的元素不是连续存储的，所以该容器迭代器中，必须包含一个可以指向list容器的指针，并且该指针可以借助重载的*、++、--、==、!=等运算符，实现迭代器的递增、递减、取值等操作。
template<tyepname T,...>
struct __list_iterator{
__list_node<T>* node;
//...
//重载 == 运算符
bool operator==(const __list_iterator& x){return node == x.node;}
//重载 != 运算符
bool operator!=(const __list_iterator& x){return node != x.node;}
//重载 * 运算符，返回引用类型
T* operator *() const {return *(node).myval;}
//重载前置 ++ 运算符
__list_iterator<T>& operator ++(){
node = (*node).next;
return *this;
}
//重载后置 ++ 运算符
__list_iterator<T>& operator ++(int){
__list_iterator<T> tmp = *this;
++(*this);
return tmp;
}
//重载前置 -- 运算符
__list_iterator<T>& operator--(){
node = (*node).prev;
return *this;
}
//重载后置 -- 运算符
__list_iterator<T> operator--(int){
__list_iterator<T> tmp = *this;
--(*this);
return tmp;
}
//...
}
list访问元素的方法
对于list容器，只能通过front()和end()成员函数，或者迭代器访问元素，不支持随机访问，不支持[]，.at()和data()成员函数。
通过front()和back()成员函数
#include <iostream>
#include <list>
using namespace std;
int main()
{
std::list<int> mylist{ 1,2,3,4 };
int &first = mylist.front();
int &last = mylist.back();
cout << first << " " << last << endl;
first = 10;
last = 20;
cout << mylist.front() << " " << mylist.back() << endl;
return 0;
}
可以看出可以通过引用的方式获取list容器中的首尾元素，必要时还可以修改他们的值。
迭代器访问
如果要访问list容器中存储的其他元素，就只能使用list容器的迭代器。
#include <iostream>
#include <list>
using namespace std;
int main()
{
const std::list<int> mylist{1,2,3,4,5};
auto it = mylist.begin();
cout << *it << " ";
++it;
while (it!=mylist.end())
{
cout << *it << " ";
++it;
}
return 0;
}
list添加元素的方法
-
push_back()
-
push_front()
-
emplace_front()
-
emplace_back()
-
emplace(): 在指定的位置直接生成新的元素
-
insert()： 在指定位置插入元素
-
splice(): 将其他
list容器存储的多个元素添加到当前list容器的指定位置处
以上插入元素的方法除了insert()和splice()方法有多种语法外，其他成员方法都仅有1种语法格式：
#include <iostream>
#include <list>
using namespace std;
int main()
{
std::list<int> values{1,2,3};
values.push_front(0);//{0,1,2,3}
values.push_back(4); //{0,1,2,3,4}
values.emplace_front(-1);//{-1,0,1,2,3,4}
values.emplace_back(5); //{-1,0,1,2,3,4,5}
//emplace(pos,value),其中 pos 表示指明位置的迭代器，value为要插入的元素值
values.emplace(values.end(), 6);//{-1,0,1,2,3,4,5,6}
for (auto p = values.begin(); p != values.end(); ++p) {
cout << *p << " ";
}
return 0;
}
insert()成员函数
#include <iostream>
#include <list>
#include <array>
using namespace std;
int main()
{
std::list<int> values{ 1,2 };
//第一种格式用法
values.insert(values.begin() , 3);//{3,1,2}
//第二种格式用法
values.insert(values.end(), 2, 5);//{3,1,2,5,5}
//第三种格式用法
std::array<int, 3>test{ 7,8,9 };
values.insert(values.end(), test.begin(), test.end());//{3,1,2,5,5,7,8,9}
//第四种格式用法
values.insert(values.end(), { 10,11 });//{3,1,2,5,5,7,8,9,10,11}
for (auto p = values.begin(); p != values.end(); ++p)
{
cout << *p << " ";
}
return 0;
}
splice()成员函数
和insert()成员函数相比， splice()成员方法的作用将其他list容器中的元素添加到当前list容器中指定位置处。
splice()成员函数移动元素的方法是：将存储该元素的节点从list容器底层的链表中摘除，然后在链接到当前list容器底层的链表中，这意味这，当使用splice()成员函数将x容器中的元素添加到当前容器的同时，该元素会从x容器中删除
#include <iostream>
#include <list>
using namespace std;
int main()
{
//创建并初始化 2 个 list 容器
list<int> mylist1{ 1,2,3,4 }, mylist2{10,20,30};
list<int>::iterator it = ++mylist1.begin(); //指向 mylist1 容器中的元素 2
//调用第一种语法格式
mylist1.splice(it, mylist2); // mylist1: 1 10 20 30 2 3 4
// mylist2:
// it 迭代器仍然指向元素 2，只不过容器变为了 mylist1
//调用第二种语法格式，将 it 指向的元素 2 移动到 mylist2.begin() 位置处
mylist2.splice(mylist2.begin(), mylist1, it); // mylist1: 1 10 20 30 3 4
// mylist2: 2
// it 仍然指向元素 2
//调用第三种语法格式，将 [mylist1.begin(),mylist1.end())范围内的元素移动到 mylist.begin() 位置处
mylist2.splice(mylist2.begin(), mylist1, mylist1.begin(), mylist1.end());//mylist1:
//mylist2:1 10 20 30 3 4 2
cout << "mylist1 包含 " << mylist1.size() << "个元素" << endl;
cout << "mylist2 包含 " << mylist2.size() << "个元素" << endl;
//输出 mylist2 容器中存储的数据
cout << "mylist2:";
for (auto iter = mylist2.begin(); iter != mylist2.end(); ++iter) {
cout << *iter << " ";
}
return 0;
}
empty()和size()判断容器是否为空
假设有一个容器cont,则此代码：
if(cont.size()==0)
本质上和如下代码是等价的：
if(cont.empty())
建议使用empty()成员方法，理由很简单。 无论是哪种容器，只要其模板类中提供了empty()成员方法，使用此方法都可以保证在O(1)时间复杂内完成对容器是否为空的判断； 但对于list容器来说，使用size()成员方法判断容器是否为空，可能要消耗O(n)的时间复杂度。
这个结论不仅适用于
vector、deque和list容器，后续还会讲解更多容器的用法，该结论也依然使用。
list删除元素详解
pop_front()，pop_back(), clear()
#include <iostream>
#include <list>
using namespace std;
int main()
{
list<int>values{ 1,2,3,4 };
//删除当前容器中首个元素
values.pop_front();//{2,3,4}
//删除当前容器最后一个元素
values.pop_back();//{2,3}
//清空容器，删除容器中所有的元素
values.clear(); //{}
for (auto begin = values.begin(); begin != values.end(); ++begin)
{
cout << *begin << " ";
}
return 0;
}
erase()函数
iterator erase(iterator position); //删除`list`容器中`position`迭代器所指位置处的元素
iterator erase(iterator first, iterator last); //删除`list`容器中`first`迭代器和`last`迭代器限定区域内的所有元素，不包括`last`指向的元素
#include <iostream>
#include <list>
using namespace std;
int main()
{
list<int>values{ 1,2,3,4,5 };
//指向元素 1 的迭代器
auto del = values.begin();
//迭代器右移，改为指向元素 2
++del;
values.erase(del); //{1,3,4,5}
for (auto begin = values.begin(); begin != values.end(); ++begin)
{
cout << *begin << " ";
}
return 0;
}
#include <iostream>
#include <list>
using namespace std;
int main()
{
list<int>values{ 1,2,3,4,5 };
//指定删除区域的左边界
auto first = values.begin();
++first;//指向元素 2
//指向删除区域的右边界
auto last = values.end();
--last;//指向元素 5
//删除 2、3 和 4
values.erase(first, last);
for (auto begin = values.begin(); begin != values.end(); ++begin)
{
cout << *begin << " ";
}
return 0;
}
remove()函数
erease()函数是按照删除元素的位置来执行删除操作，如果想按照元素的值来执行删除操作，可以使用remove()成员函数。
#include <iostream>
#include <list>
using namespace std;
int main()
{
list<char>values{'a','b','c','d'};
values.remove('c');
for (auto begin = values.begin(); begin != values.end(); ++begin)
{
cout << *begin << " ";
}
return 0;
}
unique()成员函数
void unique()
void unique(BinaryPredicate) //传入一个二元谓词函数
以上两种格式都可以实现去除list容器中相邻重复的元素，仅保留一份。但第二种格式的优势在于可以自定义去重规则
#include <iostream>
#include <list>
using namespace std;
//二元谓词函数
bool demo(double first, double second)
{
return (int(first) == int(second));
}
int main()
{
list<double> mylist{ 1,1.2,1.2,3,4,4.5,4.6 };
//删除相邻重复的元素，仅保留一份
mylist.unique();//{1, 1.2, 3, 4, 4.5, 4.6}
for (auto it = mylist.begin(); it != mylist.end(); ++it)
cout << *it << ' ';
cout << endl;
//demo 为二元谓词函数，是我们自定义的去重规则
mylist.unique(demo);
for (auto it = mylist.begin(); it != mylist.end(); ++it)
std::cout << *it << ' ';
return 0;
}
除了使用一定谓词函数的方式外，还可以使用**
lamba表达式及函数对象**的方式定义
通过无参的unique只能删除相邻的重复元素，而通过自定义去重的规则，可以更好的满足不同场景下去重的需求。
remove_if()成员函数
可以将自定义的谓词函数（不限定参数个数）传给remove_if成员函数，list容器中能使谓词函数成立的元素都会被删除。
#include <iostream>
#include <list>
using namespace std;
int main()
{
std::list<int> mylist{ 15, 36, 7, 17, 20, 39, 4, 1 };
//删除 mylist 容器中能够使 lamba 表达式成立的所有元素。
mylist.remove_if([](int value) {return (value < 10); }); //{15 36 17 20 39}
for (auto it = mylist.begin(); it != mylist.end(); ++it)
std::cout << ' ' << *it;
return 0;
}
补充知识点lamda表达式
可以直接在使用的时候定义函数，这个函数就叫做lamda表达式，在c++11被引入。
lambda表达式的定义形式如下：
[外部变量访问方式说明符]（参数表） -> 返回值类型
{
语句块
}
其中外部变量访问方式说明符可以是=或&,这些外部变量访问方式说明符表示{}用到的，定义在{}外面的变量在{}是否允许被改变，如果是==，表示不允许，&表示允许改变。当然在{}也可以不使用定义在外面的变量， ->返回值类型可以省略
合法的lambda表达式：
[=](int x, int y) -> bool{return x%10<y%10;}
下列代码使用上述无名的函数：
int a[4]={11,2,33,4};
sort(a, a+4,[=](int x, int y)->bool {return x%10 <y%10;});
for_each(a,a+4, [=](int x ){cout << x <<" ";});
上述程序第二行使数组a按个位数从小到大进行排序，具体操作如下：
执行sort时，需要判断两个元素x、y的大小，会以x、y作为参数，调用lambda表达式所代表的函数，根据返回值来判断x、y的大小
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int a[4] = { 1, 2, 3, 4 };
int total = 0;
for_each(a, a + 4, [&](int & x) { total += x; x *= 2; });
cout << total << endl; //输出 10
for_each(a, a + 4, [=](int x) { cout << x << " "; });
return 0;
}
[&]表示该lambda表达式中用到的外部变量total是传引用的，其值可以在表达式执行过程中被改变。在每次执行for_each()的时候，都会将a中的一个元素累加到total中，然后将该元素加倍。
对于外部变量访问方式说明符中，还可以如下使用：
-
[=,&x,&y]表示外部变量x、y的值可以被修改，其余外部变量不能被修改 -
[&,x,y]表示除x、y外的外部变量，值都可以被修改。
#include <iostream>
using namespace std;
int main()
{
int x = 100,y=200,z=300;
auto ff = [=,&y,&z](int n) {
cout <<x << endl;
y++; z++;
return n*n;
};
cout << ff(15) << endl;
cout << y << "," << z << endl;
}
上述代码将lambda表达式赋予给了ff，相当于句柄函数。第 11 行通过 ff，以 15 作为参数 n 调用上面的 Lambda 表达式。该 Lambda 表达式指明，对于外部变量 y、z，可以修改其值；对于其他外部变量，例如 x，不能修改其值。因此在该表达式执行时，可以修改外部变量 y、z 的值，但如果出现试图修改 x 值的语句，就会编译出错。
作者介绍