深入STL之list - 模拟实现深入理解List与迭代器

Shaw0xyz

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节点结构体

1. struct ListNode {
   
2.     int val;
   
3.     ListNode* prev;
   
4.     ListNode* next;
   
5.     ListNode(int x) : val(x), prev(nullptr), next(nullptr) {}
   
6. };

复制代码

3.2 定义list类

1. class MyList {
   
2. private:
   
3.     ListNode* head;
   
4.     ListNode* tail;
   
5. public:
   
6.     MyList() : head(nullptr), tail(nullptr) {}
   
7. 
   
8.     // 插入操作
   
9.     void insert(int val) {
   
10.         ListNode* node = new ListNode(val);
    
11.         if (!head) {
    
12.             head = node;
    
13.             tail = node;
    
14.         } else {
    
15.             tail->next = node;
    
16.             node->prev = tail;
    
17.             tail = node;
    
18.         }
    
19.     }
    
20. 
    
21.     // 删除操作
    
22.     void erase(int val) {
    
23.         ListNode* cur = head;
    
24.         while (cur) {
    
25.             if (cur->val == val) {
    
26.                 if (cur == head) {
    
27.                     head = cur->next;
    
28.                 } else if (cur == tail) {
    
29.                     tail = cur->prev;
    
30.                 } else {
    
31.                     cur->prev->next = cur->next;
    
32.                     cur->next->prev = cur->prev;
    
33.                 }
    
34.                 delete cur;
    
35.                 return;
    
36.             }
    
37.             cur = cur->next;
    
38.         }
    
39.     }
    
40. 
    
41.     // 迭代器操作
    
42.     class iterator {
    
43.     private:
    
44.         ListNode* node;
    
45.     public:
    
46.         iterator(ListNode* n) : node(n) {}
    
47. 
    
48.         int& operator*() {
    
49.             return node->val;
    
50.         }
    
51. 
    
52.         iterator& operator++() {
    
53.             node = node->next;
    
54.             return *this;
    
55.         }
    
56. 
    
57.         iterator& operator--() {
    
58.             node = node->prev;
    
59.             return *this;
    
60.         }
    
61. 
    
62.         bool operator!=(const iterator& other) const {
    
63.             return node != other.node;
    
64.         }
    
65.     };
    
66. 
    
67.     iterator begin() {
    
68.         return iterator(head);
    
69.     }
    
70. 
    
71.     iterator end() {
    
72.         return iterator(nullptr);
    
73.     }
    
74. };

复制代码

4. 结论

通过模拟实现list容器，我们深入理解了list容器的工作原理和基本操作。list容器作为STL中的一个重要组件，为我们提供了高效的链表操作，可以在实际编程中大显身手。希望本文能帮助读者更好地理解list容器和迭代器的使用方式。




/ 荔枝学姐de课后专栏 /

Hi！这里是荔枝学姐~

欢迎来到我的课后专栏

自然语言学渣 NLP摆烂姐

热衷于技术写作 IT边角料

AIGC & Coding & linux ...

~互撩~ TG: @Shaw_0xyz