C++效率掌握之STL库：list函数全解

本篇是STL库专题之list，本质是一个双向带头循环链表，提供了双向迭代器，可以向前和向后遍历链表。这在一些需要双向操作的算法中非常有用，比如实现回文检查等1.为什么要学习list？什么是list？ list 是 C++ 标准模板库中的一个容器，它实现了双向链表的数据结构。双向链表由一系列节点组成，每个节点包含一个数据元素和两个指针，分别指向前一个节点和后一个节点。在链表的任意位置进行插入和删除操作的时间复杂度都是O(1) 。这使得它在需要频繁插入和删除元素的场景下表现出色，比如实现一个任务调度器，需要不断地添加新任务、移除已完成的任务

list 也是一种很常用的容器，对于链表的处理提供了极大的便利性

list 的主要特征可总结为：

list 是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代list 的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素list 与 forward_list 非常相似：最主要的不同在于 forward_list 是单链表，只能朝前迭代，已让其更简单高效与其他的序列式容器相比(array，vector，deque)，list 通常在任意位置进行插入、移除元素的执行效率更好。与其他序列式容器相比，list 和 forward_list 最大的缺陷是不支持任意位置的随机访问，比如：要访问 list 的第 6 个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list 还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大 list 来说这可能是一个重要的因素)2.list类对象的常见构造list作为一个类也有构造函数，析构函数，=运算符重载，我们重点介绍构造函数里的功能

函数名

功能说明

list()

无参构造

list (size_type n, const value_type& val = value_type())

构造并初始化n个val

list (const list& x)

拷贝构造

list (InputIterator first, InputIterator last)

使用迭代器进行初始化构造

💻代码测试示例：

代码语言：javascript复制#include

#include

using namespace std;

int main()

{

list first;

list second(4, 100);

list third(second.begin(), second.end());

list fourth(third);

int myints[] = { 16,2,77,29 };

list fifth(myints, myints + sizeof(myints) / sizeof(int));

cout << "The contents of fifth are: ";

for (list::iterator it = fifth.begin(); it != fifth.end(); it++)

{

cout << *it << ' ';

}

cout << endl;

return 0;

}⌨️代码输出示例：

3.list类对象的容量操作因为是链表，所以对容量的操作并不需要太多，大部分是通过创建节点并链接实现

函数名

功能说明

empty

检测list是否为空，是返回true，否则返回false

size

返回list中有效节点的个数

max_size

返回链表能存储的最多节点个数

💻代码测试示例：

代码语言：javascript复制#include

#include

using namespace std;

int main()

{

list lt;

cout << "empty:" << lt.empty() << endl;

cout << "size:" << lt.size() << endl;

cout << "max_size:" << lt.max_size() << endl;

return 0;

}⌨️代码输出示例：

4.list类对象的迭代器list 的迭代器和 vector 的基本使用方法一致，但是底层的迭代器结构不同，在 list 底层结构剖析有详细的解答

传送门：

函数名

功能说明

begin + end

迭代器：begin 获取开头一个节点 + end 获取最后一个节点下一个位置

rbegin + rend

反向迭代器：rbegin 获取最后一个节点 + end 获取开头一个节点上一个位置

cbegin + cend

和 begin + end 一样，但是常量迭代器只读

crbegin + crend

和 rbegin + rend 一样，但是反向常量迭代器只读

🔥值得注意的是：

begin 与 end 为正向迭代器，对迭代器执行 ++ 操作，迭代器向后移动rbegin(end) 与 rend(begin) 为反向迭代器，对迭代器执行 ++ 操作，迭代器向前移动💻代码测试示例：

代码语言：javascript复制#include

#include

using namespace std;

int main()

{

list lt;

lt.push_back(1);

lt.push_back(2);

lt.push_back(3);

lt.push_back(4);

cout << "迭代器:";

list::iterator it = lt.begin();

while (it != lt.end())

{

cout<< *it << " ";

++it;

}

cout<< endl;

cout << "反向迭代器:";

list::reverse_iterator it1 = lt.rbegin();

while (it1 != lt.rend())

{

cout << *it1 << " ";

++it1;

}

cout << endl;

}⌨️代码输出示例：

5.list类对象的元素修改emplace 的实现涉及 C++11 左值右值的知识，等到后面再拓展

函数名

功能说明

assign

将新的内容赋值给链表

push_front

在 list 首元素前插入值为 val 的元素

pop_front

删除 list 中第一个元素

push_back

在 list 尾部插入值为 val 的元素

pop_back

删除 list 中最后一个元素

insert

在 list position 位置中插入值为 val 的元素

erase

删除 list position 位置的元素

swap

交换两个 list 中的元素

resize

将有效数据的个数增加或减少 n 个，多出的空间用默认值，少的截断即可

clear

清空 list 中的有效元素

💻代码测试示例：

代码语言：javascript复制#include

#include

using namespace std;

int main()

{

list lt;

lt.push_back(1);

lt.push_back(2);

lt.push_back(3);

lt.push_back(4);

cout << "lt:";

list::iterator it1 = lt.begin();

while (it1 != lt.end())

{

cout << *it1 << " ";

++it1;

}

cout << endl;

lt.assign(4, 0);

cout << "assign:";

list::iterator it2 = lt.begin();

while (it2 != lt.end())

{

cout << *it2 << ' ';

it2++;

}

cout << endl;

lt.push_front(1);

cout << "push_front:";

list::iterator it3 = lt.begin();

while (it3 != lt.end())

{

cout << *it3 << ' ';

it3++;

}

cout << endl;

lt.pop_front();

cout << "pop_front:";

list::iterator it4 = lt.begin();

while (it4 != lt.end())

{

cout << *it4 << ' ';

it4++;

}

cout << endl;

lt.push_back(5);

cout << "push_back:";

list::iterator it5 = lt.begin();

while (it5 != lt.end())

{

cout << *it5 << ' ';

it5++;

}

cout << endl;

lt.pop_back();

cout << "pop_back:";

list::iterator it6 = lt.begin();

while (it6 != lt.end())

{

cout << *it6 << ' ';

it6++;

}

cout << endl;

list::iterator it7 = lt.begin();

int num1 = 3;

while (--num1)

{

it7++;

}

list::iterator pos = it7;

lt.insert(pos, 3, 1);

cout << "insert:";

list::iterator it8 = lt.begin();

while (it8 != lt.end())

{

cout << *it8 << ' ';

it8++;

}

cout << endl;

list::iterator it9 = lt.begin();

int num2 = 3;

while (--num2)

{

it9++;

}

list::iterator pos1 = it9;

list::iterator it10 = lt.begin();

int num3 = 6;

while (--num3)

{

it10++;

}

list::iterator pos2 = it10;

lt.erase(pos1, pos2);

cout << "erase:";

list::iterator it11 = lt.begin();

while (it11 != lt.end())

{

cout << *it11 << ' ';

it11++;

}

cout << endl;

list ltt;

ltt.push_back(10);

ltt.push_back(20);

ltt.push_back(30);

ltt.push_back(40);

cout << "ltt:";

list::iterator it12 = ltt.begin();

while (it12 != ltt.end())

{

cout << *it12 << ' ';

it12++;

}

cout << endl;

swap(lt, ltt);

cout << "swap:" << ' ' << "lt:";

list::iterator it13 = lt.begin();

while (it13 != lt.end())

{

cout << *it13 << ' ';

it13++;

}

cout << ' ' << "ltt:";

list::iterator it14 = ltt.begin();

while (it14 != ltt.end())

{

cout << *it14 << ' ';

it14++;

}

cout << endl;

lt.resize(10);

cout << "resize:" << lt.size() << endl;

lt.clear();

cout << "clear:";

list::iterator it15 = lt.begin();

while (it15 != lt.end())

{

cout << *it15 << ' ';

it15++;

}

cout << endl;

return 0;

}⌨️代码输出示例：

6.list类对象的链表操作这一部分针对链表拓展了一些新的函数

函数名

功能说明

splice

将一个 list 中的元素转移到另一个 list 中

remove

移除 list 中所有等于指定值的元素

remove_if

移除 list 满足特定条件的所有元素

unique

从 list 中移除连续重复的元素

merge

将两个已排序的列表合并成一个有序列表

sort

对 list 中的元素进行排序

reverse

将 list 中的元素顺序进行反转

🔥值得注意的是： remove_if、unique、merge 涉及谓词等知识，放到后面讲

💻代码测试示例：

代码语言：javascript复制#include

#include

using namespace std;

int main()

{

list lt;

lt.push_back(3);

lt.push_back(2);

lt.push_back(1);

lt.push_back(4);

cout << "lt:";

list::iterator it1 = lt.begin();

while (it1 != lt.end())

{

cout << *it1 << ' ';

it1++;

}

cout << endl;

list ltt;

ltt.push_back(10);

ltt.push_back(20);

ltt.push_back(30);

ltt.push_back(40);

cout << "ltt:";

list::iterator it2 = ltt.begin();

while (it2 != ltt.end())

{

cout << *it2 << ' ';

it2++;

}

cout << endl;

lt.splice(lt.begin(), ltt);

cout << "splice:";

list::iterator it3 = lt.begin();

while (it3 != lt.end())

{

cout << *it3 << ' ';

it3++;

}

cout << endl;

lt.remove(40);

cout << "remove:";

list::iterator it4 = lt.begin();

while (it4 != lt.end())

{

cout << *it4 << ' ';

it4++;

}

cout << endl;

lt.sort();

cout << "sort:";

list::iterator it5 = lt.begin();

while (it5 != lt.end())

{

cout << *it5 << ' ';

it5++;

}

cout << endl;

lt.reverse();

cout << "reverse:";

list::iterator it6 = lt.begin();

while (it6 != lt.end())

{

cout << *it6 << ' ';

it6++;

}

cout << endl;

return 0;

}⌨️代码输出示例：

希望读者们多多三连支持小编会继续更新你们的鼓励就是我前进的动力！