天津网站建设索王道下拉,未做301重定向的网站,长春建站模板厂家,关键词排名优化公司哪家强#x1f31f;#x1f31f;作者主页#xff1a;ephemerals__
#x1f31f;#x1f31f;所属专栏#xff1a;C、STL
目录
前言
list简介
一、list的默认成员函数
构造函数(constructor)
析构函数
赋值重载
二、list的迭代器接口
迭代器的功能分类
三、list的容量…
作者主页ephemerals__
所属专栏C、STL
目录
前言
list简介
一、list的默认成员函数
构造函数(constructor)
析构函数
赋值重载
二、list的迭代器接口
迭代器的功能分类
三、list的容量接口
empty
size
四、list的元素访问接口
front和back
五、list的增删查改
push_front
pop_front
push_back
pop_back
insert和erase
swap
resize
clear
find
六、list的其他操作接口
splice
remove
remove_if
unique
merge
sort
reverse
总结 前言 之前我们已经学习了string、vector两个容器的使用方法及模拟实现今天跟大家介绍list的使用方法。 到了这个阶段我们应该认识到在STL中尽管容器各异但同名接口的功能往往是相似的。因此在我们掌握了少数几个容器的使用方法后对于未曾接触过的其他容器只要了解其底层数据结构就基本能够上手使用它们。
list简介 list是STL中的一种容器用于表示链表结构底层实现是一个双向带头循环链表。如果你对双向带头循环链表不太了解可以参阅这篇文章 【数据结构】双向带头循环链表c语言附源码_c语言双向环链表初始化-CSDN博客 list在插入和删除操作方面非常高效但在遍历和随机访问方面可能不如数组或者vector高效。因此在选择容器时需要根据具体的应用场景和需求进行权衡。
我们在使用list时需要引头文件list并且该容器定义在命名空间std当中。
list相关接口查阅 list - C Reference 一、list的默认成员函数 list显示实现的默认成员函数有三个分别是构造函数、析构函数和赋值重载。 构造函数(constructor) c11下list共有六个构造函数其中较为常用的有如下五种
函数原型功能说明list();无参构造忽略空间配置器创建一个空链表list(size_type n, const value_type val);用n个val值构造一个list对象list(const list x);拷贝构造用一个对象构造另一个对象list(InputIterator first,InputIterator last);迭代器区间构造list(initializer_listvalue_type il);初始化器构造大括号赋值
代码示例
#include iostream
#include list
using namespace std;void print(listint l)
{for (auto e : l){cout e ;}cout endl;
}int main()
{listint l1;//无参构造listint l2(5, 3);//n个val值构造listint l3(l2);//拷贝构造listint l4(l2.begin(), l2.end());//迭代器区间构造listint l5({ 1,2,3,4,5 });//初始化器构造cout l1: ;print(l1);cout l2: ;print(l2);cout l3: ;print(l3);cout l4: ;print(l4);cout l5: ;print(l5);return 0;
} 析构函数 释放动态分配的内存空间在对象声明周期结束时自动调用。 赋值重载 将新内容分配给已经存在的容器替换其当前内容并相应地修改其大小。较为常用的赋值重载有两个
函数原型功能说明list operator (const list x);两个list容器之间的赋值list operator (initializer_listvalue_type il);用初始化器给容器赋值
代码示例
#include iostream
#include list
using namespace std;void print(listint l)
{for (auto e : l){cout e ;}cout endl;
}int main()
{listint l1;listint l2({ 1,2,3,4,5 });l1 l2;//将l2赋值给l1print(l1);l1 { 5,4,3,2,1 };//初始化器赋值print(l1);return 0;
} 二、list的迭代器接口 迭代器接口在string和vector中的使用方法大致相同这里就不多介绍。 由于list元素的内存地址是不连续的因此在迭代器的实现上它与vector和string存在较大差异。我们将在list模拟实现的部分中对此进行深入探讨。 我们在这里重点讲一下迭代器的功能分类
迭代器的功能分类
根据功能强弱迭代器可以分为以下三种 1. 单向迭代器它仅支持在容器中进行从头到尾的遍历操作重载了“”运算符。 2. 双向迭代器它支持从头到尾的遍历和从尾到头的遍历重载了“”和“--”运算符。 3. 随机迭代器顾名思义它不仅支持双向的遍历还支持随机位置的访问重载了“”“--”“”“-”等运算符。 这三种迭代器的功能是向下兼容的即随机迭代器具有双向迭代器的功能而双向迭代器具有单向迭代器的功能。
为什么会有这样的分类呢其实这是由底层数据结构的实现导致的。 有些数据结构元素的内存地址连续还能够支持双向遍历并且遍历效率高那么就可以支持随机迭代器例如string、vector有些数据结构能够支持双向遍历但是随机访问的效率低下那就支持双向迭代器例如list有些数据结构只能做到从前向后访问元素那么就只能支持单向迭代器例如单链表forward_list。 所以我们在使用string、vector的迭代器时可以使用“”“-”操作符进行随机访问而对于list就只能通过“”“--”来移动迭代器指向的位置。 三、list的容量接口 三个容量接口当中前两个比较常用我们重点介绍一下
empty empty函数用于判断该列表容器是否为空即元素个数是否为0。注意该函数不会以任何方式修改容器。 size size函数用于获取容器内元素的个数。 代码示例
#include iostream
#include list
using namespace std;int main()
{listint l1;listint l2({ 1,2,3,4,5 });cout l1.size(): l1.size() endl;cout l1.empty() endl;cout l2.size(): l2.size() endl;cout l2.empty() endl;return 0;
} 四、list的元素访问接口 front和back front函数返回对列表容器中第一个元素的引用在空容器上调用此函数会导致未定义行为。 back函数返回对列表容器中最后一个元素的引用在空容器上调用此函数会导致未定义行为。 代码示例
#include iostream
#include list
using namespace std;int main()
{listint l { 1,2,3,4,5 };cout l.front() endl;cout l.back() endl;return 0;
}相比vector的元素访问接口list缺少了operator[ ]和at。是因为它们不能实现吗当然不是而是由于链表的特殊结构。如果实现了这两个接口则使用时都需要遍历元素效率的代价是很大的。 五、list的增删查改 在涉及增删查改操作的接口中鉴于部分接口功能有所重复博主仅挑选几个进行介绍。
push_front push_front的功能是在容器的开头插入一个新元素就在它当前的第一个元素之前。val的内容被复制或移动到插入的元素中。这有效地将容器大小增加了1。 pop_front pop_front的功能是删除列表容器中的第一个元素有效地将其大小减小1。这将破坏被删除的元素。 push_back push_back的作用是在容器的末尾插入一个新元素。val的内容被复制或移动到新元素中。这有效地将容器大小增加了1。 pop_back pop_back的作用是删除容器中的最后一个元素有效地将容器大小减少一个。这将破坏被删除的元素。 代码示例
#include iostream
#include list
using namespace std;void print(listint l)
{for (auto e : l){cout e ;}cout endl;
}int main()
{listint l1 { 1,2,3,4,5 };cout 原链表;print(l1);l1.push_back(0);cout 尾插;print(l1);l1.push_front(0);cout 头插;print(l1);l1.pop_back();cout 尾删;print(l1);l1.pop_front();cout 头删;print(l1);return 0;
} insert和erase insert用于指定位置插入元素需要使用迭代器指定。该函数支持单个元素插入、n个val值插入、迭代器区间插入以及初始化器插入。操作结束后该函数会返回新插入部分首元素的迭代器。 erase的作用是删除指定位置的元素或区间需要使用迭代器指定。操作结束后函数返回删除部分的后一个位置的迭代器防止迭代器失效。 代码举例
#include iostream
#include list
using namespace std;void print(listint l)
{for (auto e : l){cout e ;}cout endl;
}int main()
{listint l { 1,2,3,4,5 };l.insert(l.begin(), 0);//在第二个位置插入一个元素print(l);l.erase(----l.end());//删除倒数第二个元素print(l);return 0;
}swap swap的功能是交换两个list容器的内容。 当然也有一个非成员函数的swap支持list的交换 resize resize的功能是调整容器的大小使其包含n个元素。 如果n小于当前容器的大小则内容将被减少到前n个元素并删除超出的元素销毁它们 如果n大于当前容器的大小则通过在末尾插入所需的元素来扩展内容以达到n的大小。如果指定了val则将新元素初始化为val的副本否则调用其构造函数来初始化元素。 注意这个函数通过插入或删除元素来改变容器的实际内容。 代码示例
#include iostream
#include list
using namespace std;void print(listint l)
{for (auto e : l){cout e ;}cout endl;
}int main()
{listint l1;listint l2;l1.resize(10);l2.resize(10, 5);print(l1);print(l2);listint l3({ 1,2,3,4,5 });print(l3);l3.resize(3);print(l3);return 0;
} clear clear的功能是从列表容器中删除所有元素并将容器的大小保留为0。 find 与vector相同list并没有用于查找的函数find要使用STL实现的通用find完成查找。该find函数定义在算法库algorithm当中用于容器元素的查找。它接受两个迭代器参数和一个值参数表示需要查找的区间和值。如果找到了函数会返回指向第一个查找到的元素的迭代器否则返回尾迭代器。 六、list的其他操作接口 除了传统的成员函数外list还提供了一些特有的与插入删除相关的操作接口供我们使用。通过学习这些接口的使用方法我们可以初步了解仿函数的相关知识。
splice splice的功能是剪切。它能够将 容器x / 容器x的某个元素 / 容器的一部分 拷贝到原容器的指定位置并且删除x中的相应元素。 代码示例
#include iostream
#include list
using namespace std;void print(listint l)
{for (auto e : l){cout e ;}cout endl;
}int main()
{listint l1;listint l2({ 1,2,3,4,5 });l1.splice(l1.end(), l2);//将l2剪切到l1的末尾cout l1:;print(l1);cout l2:;print(l2);cout endl;l2 { 1,2,3,4,5 };l1.splice(l1.end(), l2, l2.begin());//将l2的首元素剪切到l1的末尾cout l1:;print(l1);cout l2:;print(l2);cout endl;l2 { 1,2,3,4,5 };l1.splice(l1.end(), l2, l2.begin(), --l2.end());//将l2掐头去尾的部分剪切到l1的末尾cout l1:;print(l1);cout l2:;print(l2);cout endl;
} remove remove的功能是删除指定值的元素。 该函数从容器中删除比较结果为val的所有元素。这将调用这些对象的析构函数并按删除元素的数量减少容器大小。 与erase不同erase根据元素的位置删除元素该函数根据元素的值删除元素。 代码示例
#include iostream
#include list
using namespace std;void print(listint l)
{for (auto e : l){cout e ;}cout endl;
}int main()
{listint l { 1,2,3,2,4,2,2,5 };print(l);l.remove(2);//删除所有的2print(l);return 0;
} remove_if remove_if用于删除list容器中满足特定条件的所有元素特定条件由我们设定。 该函数的参数是一个谓词Predicate如果容器中的某元素使得该谓词返回true就将该元素删除。 这里简单介绍一下谓词 之前我们在c语言部分使用qsort函数时需要显示写一个比较函数用于确定排序的规则谓词的功能就相当于我们显示写的比较函数。 谓词可以是以下几种形式之一 1. 返回值为bool类型的函数指针 2. 仿函数重载了函数调用操作符()的类且该重载函数的返回值是bool类型 3. Lambda表达式c11之后支持 -------------------- 由于我们已经使用过函数指针在接下来的代码示例当中我们就尝试写一个仿函数来表示谓词。 代码示例
#include iostream
#include list
using namespace std;void print(listint l)
{for (auto e : l){cout e ;}cout endl;
}//仿函数
class f
{
public:bool operator()(int value){return value 10;//将小于10的元素确定为true}
};int main()
{listint l { 20,1,5,9,15,17 };l.remove_if(f());//删除所有小于10的元素print(l);return 0;
} unique unique函数的功能是删除所有与它的前一个元素满足某特定关系特定关系可由我们设定的元素。当然该特定关系也是使用谓词表示。当我们没有显示设置特定关系那么该特定关系就是两元素相等也就是说我们没有传参时函数的功能是删除所有相邻的重复元素保留一个重复的元素不会全部删除。 代码示例
#include iostream
#include list
using namespace std;void print(listint l)
{for (auto e : l){cout e ;}cout endl;
}int main()
{listint l1 { 1,1,2,3,3,4,4,4,5,5,6,7,8,8 };//有序序列l1.unique();print(l1);listint l2 { 2,2,1,2,2 };//无序序列无法直接删除所有重复元素l2.unique();print(l2);return 0;
} 对于一个无序list序列如果想要删除所有的重复元素那么就需要先对list进行排序然后再调用unique函数。
merge merge的作用是合并两个有序链表注意两个容器都应是有序状态。 这实际上删除了x中的所有元素但不是销毁其中元素而是将节点的指针互相连接最后全部并入到原容器中。 该函数可以接受一个特定的谓词comp来执行元素之间的比较操作。 函数执行后等价元素的相对位置不变即原容器的在前x的在后。 如果x就是原容器那么函数什么也不做。 代码示例
#include iostream
#include list
using namespace std;void print(listint l)
{for (auto e : l){cout e ;}cout endl;
}int main()
{listint l1 { 1,3,5,7,9 };listint l2 { 2,4,6,8,10 };l1.merge(l2);//合并cout l1:;print(l1);cout l2:;print(l2);return 0;
} sort sort用于排序list容器。当然我们也可以传入一个谓词来确定排序规则否则默认升序。 它的底层是一个优化的归并排序意味着等价元素相对位置不变。 说起sort博主在这里补充一点与通用find函数相同STL实现了一个通用的排序函数sort参数是随机迭代器构成的迭代器区间用于容器排序。 为什么要实现一个成员函数版的sort呢直接使用算法库中的通用sort不行吗刚才博主已经提到list支持的是双向迭代器并不具备随机迭代器的功能所以list无法使用通用的sort函数完成排序会发生报错。所以说list的成员函数当中实现了一个排序函数sort。
接下来我们尝试使用该函数
#include iostream
#include list
#include algorithm
using namespace std;void print(listint l)
{for (auto e : l){cout e ;}cout endl;
}int main()
{listint l { 5,1,7,2,4,8,0,3 };l.sort();//排序print(l);return 0;
} 由于list底层是一个链表所以对于排序这种需要重复调整元素顺序的算法它的效率不是很高。如果要对list排序建议将list的内容拷贝给vector然后进行排序最后拷贝回list。 reverse reverse的功能是反转链表。 代码示例
#include iostream
#include list
#include algorithm
using namespace std;void print(listint l)
{for (auto e : l){cout e ;}cout endl;
}int main()
{listint l { 1,2,3,4,5 };l.reverse();//反转print(l);return 0;
} 总结 今天我们学习了STL容器--list的使用方法。当我们需要频繁进行插入和删除操作时可以考虑使用该容器。之后博主会和大家一起模拟实现list并且借此来深入学习迭代器的底层实现。如果你觉得博主讲的还不错就请留下一个小小的赞在走哦感谢大家的支持❤❤❤
