C++的序列式容器（二）list

news/2024/11/14 13:52:37/

std::list 是 C++ 标准库中的双向链表容器，提供了快速的插入和删除操作。与 vector 不同，list 是链式存储结构，因此它不支持随机访问。

1. 概述

std::list 是一个双向链表容器，位于 <list> 头文件中。链表是一种线性表数据结构，其中每个节点都包含一个数据元素和指向前后节点的指针。它适合在任意位置进行频繁插入和删除操作，但不适合随机访问。list 提供了指针稳定性，即插入或删除元素不会影响其他元素的地址，因此适合需要频繁插入和删除操作的场景。

#include <iostream>
#include <list>int main() {std::list<int> myList = {1, 2, 3, 4, 5};for (int val : myList) {std::cout << val << " ";    // 输出 1 2 3 4 5}return 0;
}

2. 节点

在 list 中，每个元素都被存储在一个节点中，节点通常包含以下部分：

  • 数据域：存储实际的数据值。
  • 前向指针（prev）：指向前一个节点。
  • 后向指针（next）：指向后一个节点。

这种链式结构允许 list 快速插入和删除元素（时间复杂度为 O(1)），因为只需要调整相邻节点的指针即可，不需要像 vector 那样进行数据的移动。

3. 迭代器

list 支持双向迭代器，可以通过 begin() 和 end() 方法获取头部和尾部迭代器。此外，list 还支持 rbegin() 和 rend() 迭代器进行反向遍历。

#include <iostream>
#include <list>int main() {std::list<int> myList = {1, 2, 3, 4, 5};// 正向迭代for (auto it = myList.begin(); it != myList.end(); ++it) {std::cout << *it << " ";}std::cout << std::endl;// 反向迭代for (auto it = myList.rbegin(); it != myList.rend(); ++it) {std::cout << *it << " ";}return 0;
}

运行结果

1 2 3 4 5 
5 4 3 2 1

与 vector 不同，list 不支持随机访问，list 只支持双向迭代器，而不支持随机访问迭代器。每次访问某个特定位置的元素都需要一个完整的遍历过程，因此不能使用 [] 运算符或 at() 访问指定位置的元素，必须通过迭代器进行遍历。

示例对比

以下示例展示了 vector 支持下标操作，而 list 不支持：

#include <iostream>
#include <vector>
#include <list>int main() {std::vector<int> vec = {1, 2, 3, 4, 5};std::list<int> lst = {1, 2, 3, 4, 5};// 直接使用下标访问 vector 中的元素std::cout << "Element at index 2 in vector: " << vec[2] << std::endl;// 使用迭代器访问 list 中的第三个元素auto it = lst.begin();std::advance(it, 2); // 移动迭代器到第三个位置std::cout << "Element at index 2 in list: " << *it << std::endl;return 0;
}

运行输出：

Element at index 2 in vector: 3
Element at index 2 in list: 3

因为 list 是链表结构而不是连续内存，因此它无法提供高效的随机访问；只能通过迭代器进行线性遍历，时间复杂度为 O(n)。

需要注意的是，list有一个重要性质：插入操作（insert）和接合操作（splice）都不会造成原有的list迭代器失效。这在vector中是不成立的，因为vector的插入操作可能造成记忆体重新配置，导致原有的迭代器全部失效。甚至list的元素删除操作（erase），也只有“指向被删除元素”的那个迭代器失效，其他迭代器不受任何影响。

下面是一个示例代码，通过删除 std::list 中的某个元素，展示删除操作只使指向被删除元素的迭代器失效，而其他迭代器保持有效：

#include <iostream>
#include <list>int main() {std::list<int> myList = {1, 2, 3, 4, 5};// 获取指向第三个元素的迭代器auto it1 = myList.begin();std::advance(it1, 2); // 指向元素3// 获取指向第四个元素的迭代器auto it2 = it1;++it2; // 指向元素4// 删除第三个元素（值为3）myList.erase(it1);// 尝试访问其他迭代器（it2）std::cout << "Element after deletion (it2): " << *it2 << std::endl;// 遍历并输出剩余元素，验证列表完整性std::cout << "Remaining elements: ";for (const auto& elem : myList) {std::cout << elem << " ";}std::cout << std::endl;return 0;
}
解释
  1. 创建迭代器：it1 指向元素 3，it2 指向元素 4。
  2. 删除操作：调用 erase(it1) 删除元素 3，使 it1 失效。
  3. 验证未失效迭代器：it2 仍然指向元素 4，未受到影响。
  4. 遍历并输出结果：剩余的元素顺序和内容保持正确，验证了删除操作只影响指向被删元素的迭代器，不会影响其他迭代器的有效性。

运行结果

Element after deletion (it2): 4
Remaining elements: 1 2 4 5

4. 数据结构

std::list 的底层数据结构是一个（环状）双向链表。链表的特点是每个节点存储一个数据值和两个指针（prev 和 next），分别指向前一个和后一个节点。双向链表适合频繁的插入和删除操作，尤其是在中间位置插入或删除元素时，可以避免大量数据移动。

然而，链表占用的内存比数组多，因为每个节点都要额外存储两个指针。同时，由于链表分散存储，不具备局部性，不适合频繁的随机访问。

5. 构造与内存管理

list 提供了多种构造方法和内存管理操作：

  • 默认构造：std::list<int> myList;
  • 指定大小构造：std::list<int> myList(10); // 创建10个元素，初始值为0
  • 指定大小和初始值：std::list<int> myList(10, 5); // 创建10个元素，初始值为5
  • 拷贝构造：std::list<int> myList2(myList);
  • 移动构造：高效转移资源，避免拷贝

在内存管理方面，list 没有 vector 的 capacity 和 reserve 方法，因为链表的存储不需要预留空间。但 list 提供了 clear() 方法用于清空所有元素，size() 方法获取元素数量。

#include <iostream>
#include <list>int main() {std::list<int> myList(5, 2); // 大小为5，初始值为2std::cout << "Size: " << myList.size() << std::endl;myList.clear();std::cout << "Size after clear: " << myList.size() << std::endl;return 0;
}

运行结果

Size: 5
Size after clear: 0

6. 元素操作方法

list 提供了一些操作方法，允许在列表任意位置插入和删除元素。

  • 添加：

    • push_front(val)：在头部插入元素
    • push_back(val)：在尾部插入元素
    • emplace_front(args...) 和 emplace_back(args...)：原地构造新元素，避免拷贝
    • insert(pos, val)：在指定迭代器位置插入元素
    • emplace(pos, args...)：在指定位置原地构造元素
    • splice：将一个 list 的元素移动到另一个 list

    splice 用于将一个 list 的一部分或全部转移到另一个 list 中。该操作不会产生拷贝，只是修改指针，因此效率非常高。

#include <iostream>
#include <list>int main() {std::list<int> list1 = {1, 2, 3};std::list<int> list2 = {4, 5, 6};// 将 list2 的所有元素移动到 list1 的末尾list1.splice(list1.end(), list2);std::cout << "After splice, list1: ";for (const auto& elem : list1) {std::cout << elem << " ";}std::cout << std::endl;std::cout << "After splice, list2 (should be empty): ";for (const auto& elem : list2) {std::cout << elem << " ";}std::cout << std::endl;return 0;
}

        运行结果

After splice, list1: 1 2 3 4 5 6
After splice, list2 (should be empty):

        注意：splice 之后，list2 中的元素被转移到 list1，list2 变为空。

  • merge：合并两个排序的 list

  merge 用于将两个已经排序的 list 合并成一个排序的 list。它要求两个列表都已经排好序。

#include <iostream>
#include <list>int main() {std::list<int> list1 = {1, 3, 5};std::list<int> list2 = {2, 4, 6};// 合并 list2 到 list1，并保持排序list1.merge(list2);std::cout << "After merge, list1: ";for (const auto& elem : list1) {std::cout << elem << " ";}std::cout << std::endl;std::cout << "After merge, list2 (should be empty): ";for (const auto& elem : list2) {std::cout << elem << " ";}std::cout << std::endl;return 0;
}

        运行结果

After merge, list1: 1 2 3 4 5 6
After merge, list2 (should be empty):

        注意：merge 会将 list2 合并到 list1，并保持排序。合并后 list2 变为空。

  • 删除：

    • pop_front() 和 pop_back()：删除头部或尾部元素
    • erase(pos)：删除指定位置的元素
    • clear()：清空所有元素
    • remove(val)：删除所有等于 val 的元素
    • unique：移除连续重复的元素。

    unique 用于删除 list 中连续的重复元素。如果列表中的元素是 [1, 2, 2, 3, 3, 3, 4]，调用 unique 后会变成 [1, 2, 3, 4]。

#include <iostream>
#include <list>int main() {std::list<int> myList = {1, 2, 2, 3, 3, 3, 4};// 移除连续重复的元素myList.unique();std::cout << "After unique: ";for (const auto& elem : myList) {std::cout << elem << " ";}std::cout << std::endl;return 0;
}# 输出：After unique: 1 2 3 4

  • 访问：

    • front() 和 back()：访问首尾元素

  • 顺序操作：

    • reverse()：反转 list 中的元素顺序
    • sort()：对 list 进行排序

        sort 用于对 list 中的元素进行排序。list 不支持随机访问，因此不能使用 std::sort，必须使用 list 自带的 sort 方法。

#include <iostream>
#include <list>int main() {std::list<int> myList = {4, 2, 5, 1, 3};// 排序元素myList.sort();std::cout << "After sort: ";for (const auto& elem : myList) {std::cout << elem << " ";}std::cout << std::endl;return 0;
}

        运行结果：

After sort: 1 2 3 4 5

        可以使用自定义比较函数对 list 进行降序排序或其他排序方式。

示例：使用 Lambda 表达式进行降序排序

C++11 引入的 Lambda 表达式可以让我们更简洁地定义比较函数，适合进行一次性排序操作。

#include <iostream>
#include <list>int main() {std::list<int> myList = {4, 2, 5, 1, 3};// 使用 Lambda 表达式进行降序排序myList.sort([](int a, int b) { return a > b; });std::cout << "List after sorting in descending order using Lambda: ";for (const auto& elem : myList) {std::cout << elem << " ";}std::cout << std::endl;return 0;
}

        运行结果

List after sorting in descending order using Lambda: 5 4 3 2 1

总结

std::list 是一种双向链表容器，适合频繁插入和删除操作。但list 是链式存储结构，因此它不支持随机访问


http://www.ppmy.cn/news/1546669.html

相关文章

Oracle RAC的thread

Oracle RAC的thread

参考文档&#xff1a; Real Application Clusters Administration and Deployment Guide 3 Administering Database Instances and Cluster Databases Initialization Parameter Use in Oracle RAC Table 3-3 Initialization Parameters Specific to Oracle RAC THREAD Sp…
阅读更多...
dapp获取钱包地址,及签名

dapp获取钱包地址,及签名

npm install ethersimport {ethers} from ethers const accounts await ethereum.request({method: eth_requestAccounts}); // 获取钱包地址 this.form.address accounts[0] console.log("accounts:" this.address)const provider new ethers.BrowserProvider(…
阅读更多...
无人驾驶汽车——AI技术在交通领域的进展与未来展望

无人驾驶汽车——AI技术在交通领域的进展与未来展望

文章目录 前言什么是无人驾驶汽车？特斯拉的无人驾驶愿景无人驾驶的技术进程：从DARPA挑战赛到特斯拉中国无人驾驶技术的现状谷歌的加入与优步的竞争深度学习的到来与特斯拉的独特优势无人驾驶的未来：机遇与挑战总结前言 今天，我想通过讲一个故事，帮助大家更好地理解无人驾…
阅读更多...
vite构建的react程序放置图片

vite构建的react程序放置图片

在 Vite 中&#xff0c;将图片放置在 public 文件夹中可以直接使用相对路径&#xff08;如 /logo.png&#xff09;的原因主要与 Vite 的构建和资源处理方式有关。以下是详细的解释&#xff1a; 1. 公共访问性 public 文件夹中的文件在构建过程中不会被 Vite 处理或哈希化。这…
阅读更多...
如何在本地文件系统中预览 Vue 项目？

如何在本地文件系统中预览 Vue 项目？

要在本地文件系统中直接预览 Vue 项目&#xff0c;你需要确保打包后的 dist 文件夹中的资源能够正确加载。这里有几个步骤可以帮助你实现这一点&#xff1a; 1. 配置 vue.config.js 确保在 vue.config.js 中设置 publicPath 为 ‘./’。这会让所有的资源路径相对于当前目录&a…
阅读更多...
Jmeter的安装，设置中文，解决乱码问题

Jmeter的安装，设置中文，解决乱码问题

1.Jmeter安装 1-Jmeter如何下载 1---我这里提供一个下载快的方式 https://www.123684.com/s/lWZKVv-4jiav?提取码:4x4y 2---Jmeter官网下载地址 Apache JMeter - Download Apache JMeter 2-配置java环境 1---下载javaJDK 官方下载地址 https://www.oracle.com/java/techno…
阅读更多...
数据分析考试怎么考

数据分析考试怎么考

数据分析在现代商业和学术领域变得越来越重要&#xff0c;为决策提供了坚实的基础。对于那些希望在这一领域发展职业生涯的人来说&#xff0c;通过专业认证来展示自己在数据分析方面的能力无疑是一个明智之举。在众多数据分析认证中&#xff0c;CDA&#xff08;Certified Data …
阅读更多...
从“大吼”到“轻触”，防爆手机如何改变危险油气环境通信？

从“大吼”到“轻触”，防爆手机如何改变危险油气环境通信？

众所周知&#xff0c;在加油站用手机打电话是被明令禁止的&#xff0c;这是因为手机内部会产生静电或射频火花&#xff0c;可能点燃空气中的油气混合物&#xff0c;导致爆炸或火灾。那么加油站的工作人员如何交流呢&#xff1f;以前他们靠吼&#xff0c;现在有了防爆手机&#…
阅读更多...
最新文章

Copyright @ 2022~2023