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 值的语句,就会编译出错。
作者介绍