E

EdwardWong

V1

2022/12/01阅读:64主题:姹紫

STL序列型容器之list容器

STLlist容器,又称双向链表容器,即该容器的底层是以双向链表的形式实现的。 list容器中的元素可以分散的存储在内存空间中,而不是必须存储在一整块连续的内存空间中。

list容器中各个元素的前后顺序是靠指针来维系的,每个元素配备了2个指针,分别指向它的前一个元素和后一个元素。其中第一个元素的前向指针总为null,尾部元素的后向指针也总为null.

list容器可以在快速的以O(1)的时间复杂度插入或删除元素。但是其不能像arrayvector那样快速的随机访问元素,只能从容器中第一个元素或者最后一个元素开始遍历容器,直到找到该位置。

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,dequearray最大的不同在于,list容器配备的迭代器类型为双向迭代器,而不是是随机访问迭代器。

双向迭代器支持使用++p1p1++p1--p1--*p1p1==p2以及p1!=p2(逻辑运算符)运算符,但不支持以下操作:

  • p1[i]: 不能通过下标访问list容器中指定位置处的元素。

  • p1-=i、p1+=i、p1+i、p1-i:双向迭代器p1不支持-=+=+-运算符。

  • p1<p2p1>p2p1<=p2p1>=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容器迭代器的实现

arrayvector这些容器迭代器的实现方式不同,由于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)的时间复杂度。

这个结论不仅适用于vectordequelist容器,后续还会讲解更多容器的用法,该结论也依然使用。

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时,需要判断两个元素xy的大小,会以xy作为参数,调用lambda表达式所代表的函数,根据返回值来判断xy的大小

#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]表示外部变量xy的值可以被修改,其余外部变量不能被修改

  • [&,x,y]表示除xy外的外部变量,值都可以被修改。

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

分类:

后端

标签:

C++

作者介绍

E
EdwardWong
V1