深入STL之list - 模拟实现深入理解List与迭代器
本帖最后由 Shaw0xyz 于 2024-6-10 18:23 编辑1. 引言
在C++编程中，STL（标准模板库）是一种强大的工具，它提供了丰富的数据结构和算法，帮助开发者高效地处理各种问题。本文将深入探讨STL中的list容器，并模拟实现一个简单的list以便更好地理解list和迭代器的工作原理。
1.1 什么是list容器
list是STL中的一个双向链表容器，它允许在任意位置进行高效的插入和删除操作，不需要像数组一样移动元素。list容器提供了丰富的成员函数和迭代器来操作链表中的元素。
2. list容器的模拟实现
在模拟实现list容器之前，我们需要了解list容器的基本特性和操作。
2.1 list容器的基本特性
(1) 双向链表：list容器是一个双向链表，每个节点包含一个数据元素和两个指针，分别指向前一个节点和后一个节点。
(2) 高效的插入和删除：由于双向链表的特性，list容器在任意位置进行插入和删除操作的时间复杂度为O(1)。
2.2 list容器的基本操作
(1) 插入操作：在指定位置插入元素。
(2) 删除操作：删除指定位置的元素。
(3) 迭代器操作：获取链表中的元素，并支持前向和后向遍历。
3. list容器的模拟实现
接下来，我们将模拟实现一个简单的list容器，包括插入、删除和迭代器操作。
3.1 定义list节点结构体
struct ListNode {
int val;
ListNode* prev;
ListNode* next;
ListNode(int x) : val(x), prev(nullptr), next(nullptr) {}
};
3.2 定义list类
class MyList {
private:
ListNode* head;
ListNode* tail;
public:
MyList() : head(nullptr), tail(nullptr) {}
// 插入操作
void insert(int val) {
ListNode* node = new ListNode(val);
if (!head) {
head = node;
tail = node;
} else {
tail->next = node;
node->prev = tail;
tail = node;
}
}
// 删除操作
void erase(int val) {
ListNode* cur = head;
while (cur) {
if (cur->val == val) {
if (cur == head) {
head = cur->next;
} else if (cur == tail) {
tail = cur->prev;
} else {
cur->prev->next = cur->next;
cur->next->prev = cur->prev;
}
delete cur;
return;
}
cur = cur->next;
}
}
// 迭代器操作
class iterator {
private:
ListNode* node;
public:
iterator(ListNode* n) : node(n) {}
int& operator*() {
return node->val;
}
iterator& operator++() {
node = node->next;
return *this;
}
iterator& operator--() {
node = node->prev;
return *this;
}
bool operator!=(const iterator& other) const {
return node != other.node;
}
};
iterator begin() {
return iterator(head);
}
iterator end() {
return iterator(nullptr);
}
};
4. 结论
通过模拟实现list容器，我们深入理解了list容器的工作原理和基本操作。list容器作为STL中的一个重要组件，为我们提供了高效的链表操作，可以在实际编程中大显身手。希望本文能帮助读者更好地理解list容器和迭代器的使用方式。
/ 荔枝学姐de课后专栏 /
Hi！这里是荔枝学姐~
欢迎来到我的课后专栏
自然语言学渣 NLP摆烂姐
热衷于技术写作 IT边角料
AIGC & Coding & Linux ...
~互撩~ TG: @Shaw_0xyz
页:
[1]