深入解析【C++ list 容器】:高效数据管理的秘密武器

CSDN 2024-07-21 09:05:02 阅读 80

目录

1. list 的介绍及使用

1.1 list 的介绍

知识点:

小李的理解:

1.2 list 的使用

1.2.1 list 的构造

知识点:

小李的理解:

代码示例:

1.2.2 list 迭代器的使用

知识点:

小李的理解:

代码示例:

1.2.3 list 的容量

知识点:

小李的理解:

代码示例:

1.2.4 list 的元素访问

知识点:

小李的理解:

代码示例:

1.2.5 list 的修改操作

知识点:

小李的理解:

代码示例:

1.2.6 list 迭代器失效

知识点:

小李的理解:

代码示例:

2. list 的模拟实现

知识点:

小李的理解:

代码示例:

3. list 与 vector 的对比

知识点:

小李的理解:

 总结


专栏:C++学习笔记 

上一卷:【C++ 】-vector:新时代动态数组的革新与未来

C++ 中的 <code>list 是一个强大的容器,特别适用于需要频繁插入和删除元素的场景。本文将详细介绍 list 容器,包括其介绍、使用方法、实现原理以及与 vector 容器的对比。

1. list 的介绍及使用

1.1 list 的介绍

知识点:

list 是一种序列式容器,底层实现为双向链表。双向链表中的每个元素存储在独立的节点中,节点通过指针互相连接,可以在常数时间内在任意位置进行插入和删除操作。与 forward_list 的单链表不同,list 支持双向迭代。与其他序列式容器(如 arrayvectordeque)相比,list 在插入和删除操作方面表现更优,但不支持随机访问。

小李的理解:

list 就像一条双向街道上的车队,每辆车(节点)都有前后两个链接,指向前后两辆车。你可以轻松地在任何地方插入或删除一辆车,而不需要移动其他车。但是,如果你想找到某辆车,就需要从头或尾开始,一辆辆查找,比较费时。

1.2 <code>list 的使用

1.2.1 list 的构造

知识点:

list 提供多种构造方法,包括创建空的 list,创建包含多个相同元素list,使用区间构造 list 以及拷贝构造等。

小李的理解:

构造 list 就像创建不同类型的车队,你可以创建一个空车队,或者一个全是同样车的车队,还可以用现有的车队来创建新的车队。

代码示例:

<code>#include <list>

#include <iostream>

int main() {

// 创建一个空的 list

std::list<int> empty_list;

// 创建一个包含 5 个值为 10 的元素的 list

std::list<int> filled_list(5, 10);

// 使用区间构造 list

int arr[] = {1, 2, 3, 4, 5};

std::list<int> range_list(arr, arr + 5);

// 打印 filled_list 的元素

for(int n : filled_list) {

std::cout << n << " ";

}

std::cout << std::endl;

return 0;

}

这个程序首先创建一个空的 <code>list,然后创建一个包含 5 个值为 10 的 list,接着用数组中的元素构造一个 list。最后打印 filled_list 的元素,显示 5 个 10。

1.2.2 list 迭代器的使用

知识点:

list 的迭代器类似于指针,指向 list 中的节点。你可以使用迭代器遍历 list,访问或修改元素。

小李的理解:

迭代器就像你走在车队中的一个人,你可以走到每辆车旁边查看里面的东西,或者往回走查看后面的车。

代码示例:

#include <list>

#include <iostream>

int main() {

std::list<int> my_list = {1, 2, 3, 4, 5};

// 正向迭代

for (auto it = my_list.begin(); it != my_list.end(); ++it) {

std::cout << *it << " ";

}

std::cout << std::endl;

// 反向迭代

for (auto rit = my_list.rbegin(); rit != my_list.rend(); ++rit) {

std::cout << *rit << " ";

}

std::cout << std::endl;

return 0;

}

这个程序创建一个包含 5 个整数的 <code>list。正向迭代器遍历 list,从头到尾打印元素,反向迭代器遍历 list,从尾到头打印元素。

1.2.3 list 的容量

知识点:

你可以使用 empty() 函数检查 list 是否为空,使用 size() 函数获取 list 中的元素个数。

小李的理解:

这就像你检查车队中是否有车,以及数一数车队中有多少辆车。

代码示例:

#include <list>

#include <iostream>

int main() {

std::list<int> my_list = {1, 2, 3, 4, 5};

// 检查是否为空

if (my_list.empty()) {

std::cout << "List is empty" << std::endl;

} else {

std::cout << "List is not empty" << std::endl;

}

// 获取大小

std::cout << "List size: " << my_list.size() << std::endl;

return 0;

}

 

程序首先检查 <code>list 是否为空,显然 my_list 不为空,然后打印 list 的大小,显示有 5 个元素

1.2.4 list 的元素访问

知识点:

你可以使用 front() 函数访问 list 的第一个元素,使用 back() 函数访问 list 的最后一个元素。

小李的理解:

这就像你想看看车队的第一辆车和最后一辆车里装了什么东西。

代码示例:

#include <list>

#include <iostream>

int main() {

std::list<int> my_list = {1, 2, 3, 4, 5};

// 访问第一个和最后一个元素

std::cout << "First element: " << my_list.front() << std::endl;

std::cout << "Last element: " << my_list.back() << std::endl;

return 0;

}

程序分别打印 <code>list 的第一个和最后一个元素,显示 1 和 5。

1.2.5 list 的修改操作

知识点:

list 提供丰富的修改操作,包括在头部和尾部插入和删除元素,插入和删除特定位置的元素,交换两个 list 的内容以及清空 list

小李的理解:

这就像你可以在车队的任何位置加车或减车,甚至可以交换两队车里的车,或者把整个车队清空。

代码示例:

#include <list>

#include <iostream>

int main() {

std::list<int> my_list = {1, 2, 3, 4, 5};

// 插入和删除操作

my_list.push_front(0); // 在前面插入 0

my_list.push_back(6); // 在后面插入 6

my_list.pop_front(); // 删除第一个元素

my_list.pop_back(); // 删除最后一个元素

// 插入和删除特定位置的元素

auto it = my_list.begin();

++it; // 指向第二个元素

my_list.insert(it, 100); // 在第二个位置插入 100

it = my_list.begin();

++it;

my_list.erase(it); // 删除第二个位置的元素

// 交换和清空 list

std::list<int> another_list = {10, 20, 30};

my_list.swap(another_list);

my_list.clear();

return 0;

}

以下是程序在各步之后的状态:

my_list 初始为 {1, 2, 3, 4, 5}插入 0 和 6 后为 {0, 1, 2, 3, 4, 5, 6}删除第一个和最后一个元素后为 {1, 2, 3, 4, 5}在第二个位置插入 100 后为 {1, 100, 2, 3, 4, 5}删除第二个位置的元素后为 {1, 2, 3, 4, 5}another_list 交换后 my_list{10, 20, 30}清空后 my_list 为空

1.2.6 list 迭代器失效

知识点:

list 中,插入操作不会导致迭代器失效,删除操作会使指向被删除节点的迭代器失效。

小李的理解:

就像你从车队中移走一辆车时,那个位置的指示牌(迭代器)也被移走了,但其他位置的指示牌不受影响。

代码示例:

#include <list>

#include <iostream>

int main() {

std::list<int> my_list = {1, 2, 3, 4, 5};

auto it = my_list.begin();

while (it != my_list.end()) {

it = my_list.erase(it); // 删除元素后,更新迭代器

}

return 0;

}

这个程序将删除 list 中的所有元素,最后 my_list 为空。

每次删除一个元素后,迭代器指向下一个元素,直到 list 清空。

2. list 的模拟实现

知识点:

实现一个简化版本的 list,需要理解其底层结构和接口的含义。以下是一个简化的 list 实现示例:

小李的理解:

模拟实现 list 就像你自己动手造一辆汽车,你需要理解汽车的每个部件和它们如何协同工作。

代码示例:

#include <iostream>

template<typename T>

class Node {

public:

T data;

Node* prev;

Node* next;

Node(T val) : data(val), prev(nullptr), next(nullptr) {}

};

template<typename T>

class List {

private:

Node<T>* head;

Node<T>* tail;

public:

List() : head(nullptr), tail(nullptr) {}

void push_back(T val) {

Node<T>* newNode = new Node<T>(val);

if (!tail) {

head = tail = newNode;

} else {

tail->next = newNode;

newNode->prev = tail;

tail = newNode;

}

}

void print() {

Node<T>* temp = head;

while (temp) {

std::cout << temp->data << " ";

temp = temp->next;

}

std::cout << std::endl;

}

~List() {

Node<T>* temp;

while (head) {

temp = head;

head = head->next;

delete temp;

}

}

};

int main() {

List<int> my_list;

my_list.push_back(1);

my_list.push_back(2);

my_list.push_back(3);

my_list.print();

return 0;

}

这个程序手动实现了一个简单的 <code>list,并添加了 3 个元素。最终打印出 list 中的所有元素。

3. listvector 的对比

知识点:

底层结构

vector:动态顺序表,连续内存空间。list:双向链表,不连续。

随机访问

vector:支持,效率为 O(1)。list:不支持,效率为 O(N)。

插入和删除

vector:效率低,时间复杂度为 O(N)。list:效率高,时间复杂度为 O(1)。

空间利用率

vector:高,连续空间,缓存利用率高。list:低,节点动态分配,容易造成内存碎片。

迭代器

vector:原生指针。list:封装的节点指针。

迭代器失效

vector:插入时可能失效,删除时当前迭代器失效。list:插入不会失效,删除时当前迭代器失效。

使用场景

vector:高效存储,随机访问。list:频繁插入和删除操作。

小李的理解:

vector 就像一块连续的停车场,每辆车(元素)都紧挨着,如果你要在中间插入或删除一辆车,就需要挪动很多车。而 list 就像一列火车,每节车厢(元素)独立,可以随意插入或移除车厢,但要找到某个特定车厢就得一节一节地找。

 总结

C++ 中的 list 容器是一个基于双向链表的序列式容器,适用于需要频繁插入和删除操作的场景,但不支持随机访问。list 提供了多种构造方法和丰富的操作接口,包括插入、删除、访问等。与 vector 相比,list 在插入和删除操作上更高效,但在随机访问和空间利用率上较差。



声明

本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。