Dandelion 1.1.2
A light-weight 3D builder for educational usage
载入中...
搜索中...
未找到
linked_list.hpp
浏览该文件的文档.
1#ifndef DANDELION_UTILS_LINKED_LIST_HPP
2#define DANDELION_UTILS_LINKED_LIST_HPP
3
4#include <cstddef>
5#include <utility>
6#include <type_traits>
7
8/*!
9 * \file utils/linked_list.hpp
10 * \ingroup utils
11 */
12
13// ------------------- Declarations ----------------------
14
15/*!
16 * \~chinese
17 * \brief 链表节点类型的基类。
18 *
19 * 若需要构造 `Node` 类型的链表,则 `Node` 类型应该继承这个类,
20 * 形成 CRTP (Curiously Recurring Template Pattern) 结构,从而为 `Node`
21 * 类添加侵入式链表所需的指针成员。
22 *
23 * \tparam Node 链表数据类型
24 */
25template<typename Node>
26struct LinkedListNode
27{
28 LinkedListNode();
29 Node* next_node;
30 Node* prev_node;
31};
32
33/*!
34 * \~chinese
35 * \brief 侵入式双链表。
36 *
37 * 这个类实现了一个通用侵入式双链表,允许尾插入(插入到 tail 之后)
38 * 和随机删除。
39 *
40 * \tparam Node 链表数据类型
41 */
42template<typename Node>
43class LinkedList
44{
45 static_assert(
46 std::is_base_of_v<LinkedListNode<Node>, Node>,
47 "Type Node must inherit from LinkedListNode<Node>"
48 );
49
50public:
51
52 LinkedList();
53 ~LinkedList();
54 /*! \~chinese 链表头指针(非头节点,数据有意义)。 */
55 Node* head;
56 /*! \~chinese 链表尾指针。 */
57 Node* tail;
58 /*! \~chinese 在链表末尾插入一个元素,使用 `std::forward` 转发参数原地构造,无需移动。 */
59 template<typename... Args>
60 Node* append(Args&&... args);
61 /*! \~chinese 删除指针指向的节点。 */
62 void erase(Node* node);
63 /*! \~chinese 将指针指向的节点从链表中释放(删除),但不释放该节点的内存。 */
64 Node* release(Node* node);
65 /*! \~chinese 链表中存储的元素数量。 */
66 std::size_t size;
67};
68
69// ------------------- Definitions ----------------------
70
71template<typename Node>
72LinkedListNode<Node>::LinkedListNode() : next_node(nullptr), prev_node(nullptr)
73{
74}
75
76template<typename Node>
77LinkedList<Node>::LinkedList() : head(nullptr), tail(nullptr), size(0)
78{
79}
80
81template<typename Node>
82LinkedList<Node>::~LinkedList()
83{
84 Node* node = this->head;
85 while (node != nullptr) {
86 Node* to_be_deleted = node;
87 node = node->next_node;
88 delete to_be_deleted;
89 }
90}
91
92template<typename Node>
93template<typename... Args>
94Node* LinkedList<Node>::append(Args&&... args)
95{
96 Node* new_node = new Node(std::forward<Args>(args)...);
97 ++this->size;
98 if (this->head == nullptr) {
99 this->head = new_node;
100 this->tail = new_node;
101 return new_node;
102 }
103 this->tail->next_node = new_node;
104 new_node->prev_node = this->tail;
105 this->tail = new_node;
106 return new_node;
107}
108
109template<typename Node>
111{
112 if (node == nullptr || !this->size) {
113 return;
114 }
115 --this->size;
116 // Erase the last element in the list
117 if (!this->size) {
118 delete this->head;
119 this->head = nullptr;
120 this->tail = nullptr;
121 return;
122 }
123 Node* to_be_deleted = node;
124 // Erasure for the head node
125 if (node == this->head) {
126 this->head = this->head->next_node;
127 this->head->prev_node = nullptr;
128 delete to_be_deleted;
129 return;
130 }
131 // Erasure for the tail node
132 if (node == this->tail) {
133 this->tail = this->tail->prev_node;
134 this->tail->next_node = nullptr;
135 delete to_be_deleted;
136 return;
137 }
138 // Otherwise a general erasure
139 node->prev_node->next_node = node->next_node;
140 node->next_node->prev_node = node->prev_node;
141 delete to_be_deleted;
142}
143
144template<typename Node>
146{
147 if (node == nullptr || !this->size) {
148 return nullptr;
149 }
150 --this->size;
151 if (!this->size) {
152 // Erase the last element in the list
153 this->head = nullptr;
154 this->tail = nullptr;
155 } else if (node == this->head) {
156 // Erasure for the head node
157 this->head = this->head->next_node;
158 this->head->prev_node = nullptr;
159 } else if (node == this->tail) {
160 // Erasure for the tail node
161 this->tail = this->tail->prev_node;
162 this->tail->next_node = nullptr;
163 } else {
164 // Otherwise a general erasure
165 node->prev_node->next_node = node->next_node;
166 node->next_node->prev_node = node->prev_node;
167 }
168 return node;
169}
170
171#endif // DANDELION_UTILS_LINKED_LIST_HPP
Node * head
定义 linked_list.hpp:55
std::size_t size
定义 linked_list.hpp:66
void erase(Node *node)
定义 linked_list.hpp:110
Node * tail
定义 linked_list.hpp:57
Node * append(Args &&... args)
定义 linked_list.hpp:94
Node * release(Node *node)
定义 linked_list.hpp:145