解密C++ STL:深入理解并使用list容器
- 引言
- 一、list 容器概述
- 二、list容器常用的API
- 2.1、构造函数
- 2.2、数据元素插入和删除操作
- 2.3、大小操作
- 2.4、赋值操作
- 2.5、数据的存取
- 2.6、list容器的反转和排序
- 三、使用示例
- 总结
引言
💡 作者简介:一个热爱分享高性能服务器后台开发知识的博主,目标是通过理论与代码实践的结合,让世界上看似难以掌握的技术变得易于理解与掌握。技能涵盖了多个领域,包括C/C++、Linux、Nginx、MySQL、Redis、fastdfs、kafka、Docker、TCP/IP、协程、DPDK等。
👉
🎖️ CSDN实力新星、CSDN博客专家
👉
🔔 专栏介绍:从零到c++精通的学习之路。内容包括C++基础编程、中级编程、高级编程;掌握各个知识点。
👉
🔔 专栏地址:C++从零开始到精通
👉
🔔 博客主页:https://blog.csdn.net/Long_xu
🔔 上一篇:【042】解密C++ STL:深入理解并使用queue容器
一、list 容器概述
链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。相较于vector的连续线性空间,list就显得负责许多,它的好处是每次插入或者删除一个元素,就是配置或者释放一个元素的空间。因此,list对于空间的运用有绝对的精准,一点也不浪费。而且,对于任何位置的元素插入或元素的移除,list永远是常数时间。List和vector是两个最常被使用的容器。List容器是一个双向链表。
采用动态存储分配,不会造成内存浪费和溢出链表执行插入和删除操作十分方便,修改指针即可,不需要移动大量元素链表灵活,但是空间和时间额外耗费较大。
二、list容器常用的API
2.1、构造函数
C++标准库中的列表容器(List Container)是一个双向链表的实现,提供了高效的插入和删除操作。其构造函数的原型如下:
explicit list(const Allocator& alloc = Allocator());
list(size_type count, const T& value, const Allocator& alloc = Allocator());
explicit list(size_type count, const Allocator& alloc = Allocator());
template <class InputIt>
list(InputIt first, InputIt last, const Allocator& alloc = Allocator());
list(const list& other);
list(const list& other, const Allocator& alloc);
list(list&& other) noexcept;
list(list&& other, const Allocator& alloc);
使用示例:
- 使用默认构造函数创建空的列表:
std::list<int> myList;
- 使用指定元素个数和默认值创建列表:
std::list<int> myList(5, 10); // 创建包含5个值为10的元素的列表
- 使用范围内的元素创建列表:
std::vector<int> vec{1, 2, 3, 4, 5};
std::list<int> myList(vec.begin(), vec.end()); // 从vector中的元素创建列表
- 复制另一个列表创建新列表:
std::list<int> myList1{1, 2, 3};
std::list<int> myList2(myList1); // 通过复制myList1创建一个新列表
- 移动另一个列表创建新列表:
std::list<int> myList1{1, 2, 3};
std::list<int> myList2(std::move(myList1)); // 通过移动myList1创建一个新列表
2.2、数据元素插入和删除操作
- 插入操作:
-
push_back:在列表末尾插入一个元素。
void push_back(const T& value);
示例:
std::list<int> myList; myList.push_back(42); // 在列表末尾插入值为42的元素
-
push_front:在列表开头插入一个元素。
void push_front(const T& value);
示例:
std::list<int> myList; myList.push_front(42); // 在列表开头插入值为42的元素
-
insert:在指定位置插入一个或多个元素。
iterator insert(const_iterator pos, const T& value); iterator insert(const_iterator pos, size_type count, const T& value);
示例:
std::list<int> myList{1, 2, 3}; myList.insert(myList.begin() + 1, 4); // 在索引1处插入值为4的元素 myList.insert(myList.end(), 2, 5); // 在末尾插入两个值为5的元素 myList.insert(myList.begin(), {6, 7, 8}); // 在开头插入值为6、7、8的元素
- 删除操作:
-
pop_back:删除列表末尾的一个元素。
void pop_back();
示例:
std::list<int> myList{1, 2, 3}; myList.pop_back(); // 删除列表末尾的元素
-
pop_front:删除列表开头的一个元素。
void pop_front();
示例:
std::list<int> myList{1, 2, 3}; myList.pop_front(); // 删除列表开头的元素
-
erase:在指定位置或范围内删除一个或多个元素。
iterator erase(const_iterator pos); iterator erase(const_iterator first, const_iterator last);
示例:
std::list<int> myList{1, 2, 3, 4, 5}; myList.erase(myList.begin() + 2); // 删除索引为2的元素 myList.erase(myList.begin() + 1, myList.end()); // 删除从索引1到末尾的所有元素
-
remove:删除列表中值等于给定值的所有元素。
void remove(const T& value);
示例:
std::list<int> myList{1, 2, 3, 2, 4, 2}; myList.remove(2); // 删除所有值为2的元素
-
clear:清空列表中的所有元素。
void clear();
示例:
std::list<int> myList{1, 2, 3, 4, 5}; myList.clear(); // 清空列表中的所有元素
2.3、大小操作
下面是list容器大小操作的函数原型和使用示例:
- size:返回列表中元素的个数。
size_type size() const;
示例:
std::list<int> myList{1, 2, 3, 4, 5};
size_t size = myList.size(); // 获取列表中元素的个数,结果为5
- empty:检查列表是否为空。
bool empty() const;
示例:
std::list<int> myList;
bool isEmpty = myList.empty(); // 检查列表是否为空,结果为true
- max_size:返回列表可能包含的最大元素数量。
size_type max_size() const;
示例:
std::list<int> myList;
size_t maxSize = myList.max_size(); // 获取列表可能包含的最大元素数量
- resize:改变列表的大小,可以增加或减少元素的数量。
void resize(size_type count);
void resize(size_type count, const value_type& value);
- 第一个版本将列表的大小更改为指定的count值,如果count小于当前大小,则删除多余的元素;如果count大于当前大小,则在末尾插入默认构造的元素。新添加的元素将使用T的默认构造函数创建。
- 第二个版本将列表的大小更改为指定的count值,并使用value作为新插入元素的值。
示例1:
std::list<int> myList{1, 2, 3, 4, 5};
myList.resize(8); // 将列表的大小更改为8,多出的3个元素将使用int的默认构造函数创建,结果为 {1, 2, 3, 4, 5, 0, 0, 0}
示例2:
std::list<int> myList{1, 2, 3, 4, 5};
myList.resize(10, 42); // 将列表的大小更改为10,多出的5个元素将使用值为42的元素填充,结果为 {1, 2, 3, 4, 5, 42, 42, 42, 42, 42}
2.4、赋值操作
list容器提供了几种赋值操作函数:assign、operator=重载和swap。
- assign:用新元素替换列表中的内容。
void assign(size_type count, const T& value);
template<class InputIterator>
void assign(InputIterator first, InputIterator last);
- 第一个版本将列表的内容替换为count个值为value的元素。
- 第二个版本将列表的内容替换为范围[first, last)中的元素,可以是另一个容器或迭代器表示的序列。
示例1:
std::list<int> myList;
myList.assign(5, 42); // 将列表赋值为5个值为42的元素,结果为 {42, 42, 42, 42, 42}
示例2:
std::list<int> myList1{1, 2, 3};
std::list<int> myList2{4, 5, 6};
myList1.assign(myList2.begin(), myList2.end()); // 将列表赋值为myList2的内容,结果为 {4, 5, 6}
- operator=重载:使用一个列表替换另一个列表的内容。
list& operator=(const list& other);
示例:
std::list<int> myList1{1, 2, 3};
std::list<int> myList2{4, 5, 6};
myList1 = myList2; // 将myList1的内容替换为myList2的内容,结果为 {4, 5, 6}
- swap:交换两个列表的内容。
void swap(list& other);
示例:
std::list<int> myList1{1, 2, 3};
std::list<int> myList2{4, 5, 6};
myList1.swap(myList2); // 交换myList1和myList2的内容,结果为 myList1: {4, 5, 6},myList2: {1, 2, 3}
2.5、数据的存取
list容器提供了两个用于数据存取的函数:front和back。
- front:返回第一个元素的引用。
reference front();
const_reference front() const;
- 第一个版本返回对第一个元素的引用,可以用于修改元素的值。
- 第二个版本在常量列表上返回对第一个元素的引用,不能用于修改元素的值。
示例:
std::list<int> myList{1, 2, 3, 4, 5};
int& firstElement = myList.front(); // 获取第一个元素的引用
int firstValue = myList.front(); // 获取第一个元素的值
firstElement = 10; // 修改第一个元素的值
std::cout << myList.front() << std::endl; // 输出结果为 10
- back:返回最后一个元素的引用。
reference back();
const_reference back() const;
- 第一个版本返回对最后一个元素的引用,可以用于修改元素的值。
- 第二个版本在常量列表上返回对最后一个元素的引用,不能用于修改元素的值。
示例:
std::list<int> myList{1, 2, 3, 4, 5};
int& lastElement = myList.back(); // 获取最后一个元素的引用
int lastValue = myList.back(); // 获取最后一个元素的值
lastElement = 20; // 修改最后一个元素的值
std::cout << myList.back() << std::endl; // 输出结果为 20
通过使用front和back函数,您可以访问和修改list容器中的首尾元素。但是,在空列表上调用front或back函数是错误的,因为列表不包含任何元素时是无效的操作,可能引发未定义的行为。
2.6、list容器的反转和排序
list容器提供了两个函数用于反转排序:reverse和sort。以下是它们的函数原型和使用示例:
- reverse:将列表中的元素按相反的顺序重新排列。
void reverse();
- 该函数会更改列表中元素的顺序,将第一个元素置于最后一个元素的位置,第二个元素置于倒数第二个位置,依此类推。
示例:
std::list<int> myList{1, 2, 3, 4, 5};
myList.reverse(); // 反转列表中元素的顺序
for (const auto& num : myList) {
std::cout << num << " "; // 输出结果为 5 4 3 2 1
}
- sort:对列表中的元素进行排序。
void sort();
- 该函数会按升序对列表中的元素进行排序,默认使用
<
运算符进行比较。
示例:
std::list<int> myList{5, 2, 4, 1, 3};
myList.sort(); // 对列表中元素进行升序排序
for (const auto& num : myList) {
std::cout << num << " "; // 输出结果为 1 2 3 4 5
}
通过调用reverse函数,可以将list容器中的元素按相反的顺序重新排列。而通过调用sort函数,则可以对列表中的元素进行排序。
三、使用示例
以下是一个使用list容器的简单案例:
#include <iostream>
#include <list>
int main() {
std::list<int> myList;
// 向列表中添加元素
myList.push_back(1);
myList.push_back(2);
myList.push_back(3);
// 遍历并输出列表中的元素
for (const auto& num : myList) {
std::cout << num << " ";
}
std::cout << std::endl;
// 在特定位置插入元素
auto it = myList.begin();
++it; // 移动迭代器到第二个位置
myList.insert(it, 4);
// 遍历并输出更新后的列表
for (const auto& num : myList) {
std::cout << num << " ";
}
std::cout << std::endl;
// 从列表中删除指定元素
myList.remove(2);
// 遍历并输出更新后的列表
for (const auto& num : myList) {
std::cout << num << " ";
}
std::cout << std::endl;
// 清空列表
myList.clear();
// 检查列表是否为空
if (myList.empty()) {
std::cout << "列表为空" << std::endl;
}
return 0;
}
上述代码展示了使用list容器的一些常见操作:
- 使用
push_back
函数向列表末尾添加元素。 - 使用循环遍历列表并输出其中的元素。
- 使用
insert
函数在指定位置插入元素。 - 使用
remove
函数删除指定元素。 - 使用
clear
函数清空列表中的所有元素。 - 使用
empty
函数检查列表是否为空。
总结
List容器是C++标准库中的一种线性容器,它提供了双向链表的实现。
-
特点:
- 双向链表:list容器使用双向链表实现,每个节点都包含一个指向前驱节点和后继节点的指针,因此在插入和删除操作上具有较好的性能。
- 动态大小:list容器的大小可以根据需要动态调整,不会有预设上限。
- 插入和删除效率高:由于双向链表的特性,list容器对于插入和删除操作具有较高的效率。插入和删除元素时不会产生元素的移动操作。
- 迭代器稳定性:list容器支持稳定的迭代器,即当进行插入和删除操作时,仅影响相关节点,不会使其他迭代器失效。
-
使用方法:
- 头文件:
<list>
。 - 声明容器:
std::list<T> myList;
,其中T为存储在列表中的元素类型。 - 添加元素:使用
push_back
函数将元素添加到列表末尾,使用push_front
函数将元素添加到列表头部。 - 遍历列表:可以使用范围-based for循环或迭代器遍历访问列表中的元素。
- 插入和删除元素:使用
insert
函数在指定位置插入元素,使用erase
函数删除指定位置的元素。 - 反转和排序:可以使用
reverse
函数反转列表中元素的顺序,使用sort
函数对列表进行排序。 - 其他操作:list容器还提供了诸如访问第一个元素、最后一个元素、大小、清空列表等操作。
- 头文件:
-
适用场景:
- 需要频繁进行插入和删除操作,而不关注随机访问性能。
- 需要稳定的迭代器,避免插入和删除操作导致迭代器失效。
- 需要支持高效地在任意位置插入和删除元素,而不需要连续内存空间的特性。
-
注意点:
- list容器的迭代器是双向迭代器,不支持+2,但支持++。
- STL提供的算法只支持随机访问迭代器,而list容器的迭代器是双向迭代器,所以sort算法不支持list迭代器。如果要排序,可以使用list类模板提供的sort函数。
list容器是一个非常有用的线性容器,适用于需要频繁进行插入和删除操作,并且需要稳定迭代器的场景。它通过双向链表的实现,在插入和删除操作上具有较好的性能,并提供了丰富的操作函数来满足各种需求。