ObjectArx 双向循环链表 LoopList

枫叶棋语

有的时候需要一些环形结构操作，闲暇之余，做了一个循环链表，对于封闭的曲线点集操作有些用处

2. #pragma once
   
3. #include <vector>
   
4. #include <initializer_list>
   
5. #include <iostream>
   
6. #include <stdexcept>
   
7. #include <utility>
   
8. 
   
9. 
   
10. template<typename T>
    
11. class LoopList {
    
12. public:
    
13.         struct Node {
    
14.                 T data;
    
15.                 Node* prev;
    
16.                 Node* next;
    
17. 
    
18.                 template<typename... Args>
    
19.                 Node(Args&&... args)
    
20.                         : data(std::forward<Args>(args)...), prev(nullptr), next(nullptr) {
    
21.                 }
    
22.         };
    
23. protected:
    
24. 
    
25.         // 内存池实现
    
26.         class NodePool {
    
27.                 std::vector<Node*> chunks;
    
28.                 Node* freeList = nullptr;
    
29.                 size_t nextAllocPos = 0;
    
30.                 const size_t CHUNK_SIZE = 128;
    
31. 
    
32.                 void allocateChunk() {
    
33.                         Node* newChunk = static_cast<Node*>(::operator new(CHUNK_SIZE * sizeof(Node)));
    
34.                         chunks.push_back(newChunk);
    
35.                         nextAllocPos = 0;
    
36.                 }
    
37. 
    
38.         public:
    
39.                 NodePool() = default;
    
40. 
    
41.                 // 禁用拷贝
    
42.                 NodePool(const NodePool&) = delete;
    
43.                 NodePool& operator=(const NodePool&) = delete;
    
44. 
    
45.                 // 移动语义
    
46.                 NodePool(NodePool&& other) noexcept
    
47.                         : chunks(std::move(other.chunks)),
    
48.                         freeList(other.freeList),
    
49.                         nextAllocPos(other.nextAllocPos) {
    
50.                         other.freeList = nullptr;
    
51.                         other.nextAllocPos = 0;
    
52.                 }
    
53. 
    
54.                 NodePool& operator=(NodePool&& other) noexcept {
    
55.                         if (this != &other) {
    
56.                                 clear();
    
57.                                 chunks = std::move(other.chunks);
    
58.                                 freeList = other.freeList;
    
59.                                 nextAllocPos = other.nextAllocPos;
    
60.                                 other.freeList = nullptr;
    
61.                                 other.nextAllocPos = 0;
    
62.                         }
    
63.                         return *this;
    
64.                 }
    
65. 
    
66.                 ~NodePool() {
    
67.                         clear();
    
68.                 }
    
69. 
    
70.                 void clear() {
    
71.                         for (auto chunk : chunks) {
    
72.                                 for (size_t i = 0; i < CHUNK_SIZE; ++i) {
    
73.                                         if (&chunk[i] != freeList) {
    
74.                                                 chunk[i].~Node();
    
75.                                         }
    
76.                                 }
    
77.                                 ::operator delete(chunk);
    
78.                         }
    
79.                         chunks.clear();
    
80.                         freeList = nullptr;
    
81.                 }
    
82. 
    
83.                 template<typename... Args>
    
84.                 Node* create(Args&&... args) {
    
85.                         if (!freeList) {
    
86.                                 if (chunks.empty() || nextAllocPos >= CHUNK_SIZE) {
    
87.                                         allocateChunk();
    
88.                                 }
    
89.                                 Node* node = &chunks.back()[nextAllocPos++];
    
90.                                 new (node) Node(std::forward<Args>(args)...);
    
91.                                 return node;
    
92.                         }
    
93. 
    
94.                         Node* node = freeList;
    
95.                         freeList = freeList->next;
    
96.                         new (node) Node(std::forward<Args>(args)...);
    
97.                         return node;
    
98.                 }
    
99. 
    
100.                 void destroy(Node* node) noexcept {
     
101.                         node->~Node();
     
102.                         node->next = freeList;
     
103.                         freeList = node;
     
104.                 }
     
105. 
     
106.                 void reserve(size_t n) {
     
107.                         size_t neededChunks = (n + CHUNK_SIZE - 1) / CHUNK_SIZE;
     
108.                         while (chunks.size() < neededChunks) {
     
109.                                 allocateChunk();
     
110.                         }
     
111.                 }
     
112.         };
     
113. 
     
114. 
     
115.         NodePool pool;
     
116.         Node* head = nullptr;
     
117.         size_t length = 0;
     
118. 
     
119.         void initHead(Node* node) noexcept {
     
120.                 head = node;
     
121.                 head->prev = head->next = head;
     
122.         }
     
123. 
     
124.         void insertBefore(Node* nextNode, Node* newNode) noexcept {
     
125.                 newNode->next = nextNode;
     
126.                 newNode->prev = nextNode->prev;
     
127.                 nextNode->prev->next = newNode;
     
128.                 nextNode->prev = newNode;
     
129.         }
     
130. 
     
131. public:
     
132.         // 构造/析构
     
133.         LoopList() = default;
     
134. 
     
135.         LoopList(std::initializer_list<T> init) {
     
136.                 for (auto& item : init) push_back(item);
     
137.         }
     
138. 
     
139.         ~LoopList() { clear(); }
     
140. 
     
141.         // 禁用拷贝
     
142.         LoopList(const LoopList&) = delete;
     
143.         LoopList& operator=(const LoopList&) = delete;
     
144. 
     
145.         // 移动语义
     
146.         LoopList(LoopList&& other) noexcept
     
147.                 : pool(std::move(other.pool)), head(other.head), length(other.length) {
     
148.                 other.head = nullptr;
     
149.                 other.length = 0;
     
150.         }
     
151. 
     
152.         LoopList& operator=(LoopList&& other) noexcept {
     
153.                 if (this != &other) {
     
154.                         clear();
     
155.                         pool = std::move(other.pool);
     
156.                         head = other.head;
     
157.                         length = other.length;
     
158.                         other.head = nullptr;
     
159.                         other.length = 0;
     
160.                 }
     
161.                 return *this;
     
162.         }
     
163. 
     
164.         // 容量
     
165.         bool empty() const noexcept { return length == 0; }
     
166.         size_t size() const noexcept { return length; }
     
167. 
     
168.         // 节点访问
     
169.         Node* front() noexcept { return head; }
     
170.         const Node* front() const noexcept { return head; }
     
171.         Node* back() noexcept { return head ? head->prev : nullptr; }
     
172.         const Node* back() const noexcept { return head ? head->prev : nullptr; }
     
173. 
     
174.         // 内存预分配
     
175.         void reserve(size_t n) {
     
176.                 pool.reserve(n);
     
177.         }
     
178. 
     
179.         // 原位构造
     
180.         template<typename... Args>
     
181.         Node* emplace_back(Args&&... args) {
     
182.                 Node* newNode = pool.create(std::forward<Args>(args)...);
     
183.                 if (!head) {
     
184.                         initHead(newNode);
     
185.                 }
     
186.                 else {
     
187.                         insertBefore(head, newNode);
     
188.                 }
     
189.                 ++length;
     
190.                 return newNode;
     
191.         }
     
192. 
     
193.         template<typename... Args>
     
194.         Node* emplace_front(Args&&... args) {
     
195.                 Node* newNode = pool.create(std::forward<Args>(args)...);
     
196.                 if (!head) {
     
197.                         initHead(newNode);
     
198.                 }
     
199.                 else {
     
200.                         insertBefore(head, newNode);
     
201.                         head = newNode;
     
202.                 }
     
203.                 ++length;
     
204.                 return newNode;
     
205.         }
     
206. 
     
207.         // 传统插入
     
208.         template<typename U = T>
     
209.         Node* push_back(U&& value) {
     
210.                 return emplace_back(std::forward<U>(value));
     
211.         }
     
212. 
     
213.         template<typename U = T>
     
214.         Node* push_front(U&& value) {
     
215.                 return emplace_front(std::forward<U>(value));
     
216.         }
     
217. 
     
218.         void pop_front() noexcept {
     
219.                 if (head) removeNode(head);
     
220.         }
     
221. 
     
222.         void pop_back() noexcept {
     
223.                 if (head) removeNode(head->prev);
     
224.         }
     
225. 
     
226.         void removeNode(Node* node) noexcept {
     
227.                 if (!node || !head) return;
     
228. 
     
229.                 if (length == 1) {
     
230.                         head = nullptr;
     
231.                 }
     
232.                 else {
     
233.                         node->prev->next = node->next;
     
234.                         node->next->prev = node->prev;
     
235.                         if (node == head) head = head->next;
     
236.                 }
     
237. 
     
238.                 pool.destroy(node);
     
239.                 --length;
     
240.         }
     
241. 
     
242.         void clear() noexcept {
     
243.                 while (head) pop_front();
     
244.         }
     
245. 
     
246.         void reverse() noexcept {
     
247.                 if (length <= 1) return;
     
248. 
     
249.                 Node* current = head;
     
250.                 do {
     
251.                         std::swap(current->prev, current->next);
     
252.                         current = current->prev;
     
253.                 } while (current != head);
     
254. 
     
255.                 head = head->next;
     
256.         }
     
257.         //相邻节点去重
     
258.         void uniqueAdjacent() {
     
259.                 if (length <= 1) return;
     
260. 
     
261.                 Node* current = head;
     
262.                 size_t processed = 0;
     
263.                 bool hasRemoved = false;
     
264. 
     
265.                 do {
     
266.                         Node* next = current->next;
     
267.                         if (current->data == next->data) {
     
268.                                 // 特殊处理头节点
     
269.                                 if (next == head) {
     
270.                                         // 如果头节点和尾节点相同，且不是唯一节点
     
271.                                         if (length > 1 && head->data == head->prev->data) {
     
272.                                                 removeNode(head->prev);
     
273.                                                 hasRemoved = true;
     
274.                                         }
     
275.                                         break;
     
276.                                 }
     
277. 
     
278.                                 removeNode(next);
     
279.                                 hasRemoved = true;
     
280.                                 continue;
     
281.                         }
     
282.                         current = next;
     
283.                         processed++;
     
284. 
     
285.                         if (processed >= length * 2) break;
     
286.                 } while (!empty() && current != head && processed < length);
     
287. 
     
288.                 // 再次检查头尾是否相同（环形链表特例）
     
289.                 if (length >= 2 && head->data == head->prev->data) {
     
290.                         // 保留头节点，删除尾节点
     
291.                         removeNode(head->prev);
     
292.                 }
     
293.         }
     
294. 
     
295.         //转换为std::Vectot<T>
     
296.         std::vector<T> toVector() const {
     
297.                 std::vector<T> result;
     
298.                 if (empty()) return result;
     
299. 
     
300.                 result.reserve(length);   // 预分配空间优化性能
     
301.                 const Node* current = head;
     
302.                 do {
     
303.                         result.push_back(current->data);
     
304.                         current = current->next;
     
305.                 } while (current != head);
     
306. 
     
307.                 return result;
     
308.         }
     
309. 
     
310.         LoopList deepClone() const {
     
311.                 LoopList newList;
     
312.                 if (!empty()) {
     
313.                         newList.reserve(length);  // 预分配相同容量
     
314.                         const Node* current = head;
     
315.                         do {
     
316.                                 newList.emplace_back(current->data);  // 深度拷贝每个元素
     
317.                                 current = current->next;
     
318.                         } while (current != head);
     
319.                 }
     
320.                 return newList; // 利用移动语义返回
     
321.         }
     
322. 
     
323.         class data_iterator {
     
324.                 Node* current;
     
325.                 const LoopList* parent;
     
326.                 bool firstPass;
     
327. 
     
328.         public:
     
329.                 using iterator_category = std::forward_iterator_tag;
     
330.                 using value_type = T;
     
331.                 using difference_type = std::ptrdiff_t;
     
332.                 using pointer = T*;
     
333.                 using reference = T&;
     
334. 
     
335.                 data_iterator(Node* n = nullptr, const LoopList* p = nullptr, bool first = true)
     
336.                         : current(n), parent(p), firstPass(first&& n != nullptr) {
     
337.                 }
     
338. 
     
339.                 reference operator*() const { return current->data; }
     
340.                 pointer operator->() const { return ¤t->data; }
     
341. 
     
342.                 data_iterator& operator++() {
     
343.                         if (!current) return *this;
     
344.                         current = current->next;
     
345.                         if (current == parent->head) firstPass = false;
     
346.                         if (!firstPass) current = nullptr;
     
347.                         return *this;
     
348.                 }
     
349. 
     
350.                 data_iterator operator++(int) {
     
351.                         data_iterator tmp = *this;
     
352.                         ++(*this);
     
353.                         return tmp;
     
354.                 }
     
355. 
     
356.                 bool operator==(const data_iterator& other) const {
     
357.                         return current == other.current;
     
358.                 }
     
359. 
     
360.                 bool operator!=(const data_iterator& other) const {
     
361.                         return !(*this == other);
     
362.                 }
     
363.         };
     
364. 
     
365.         // 2. 常量数据迭代器
     
366.         class const_data_iterator {
     
367.                 const Node* current;
     
368.                 const LoopList* parent;
     
369.                 bool firstPass;
     
370. 
     
371.         public:
     
372.                 using iterator_category = std::forward_iterator_tag;
     
373.                 using value_type = const T;
     
374.                 using difference_type = std::ptrdiff_t;
     
375.                 using pointer = const T*;
     
376.                 using reference = const T&;
     
377. 
     
378.                 const_data_iterator(const Node* n = nullptr, const LoopList* p = nullptr, bool first = true)
     
379.                         : current(n), parent(p), firstPass(first&& n != nullptr) {
     
380.                 }
     
381. 
     
382.                 reference operator*() const { return current->data; }
     
383.                 pointer operator->() const { return ¤t->data; }
     
384. 
     
385.                 const_data_iterator& operator++() {
     
386.                         if (!current) return *this;
     
387.                         current = current->next;
     
388.                         if (current == parent->head) firstPass = false;
     
389.                         if (!firstPass) current = nullptr;
     
390.                         return *this;
     
391.                 }
     
392. 
     
393.                 const_data_iterator operator++(int) {
     
394.                         const_data_iterator tmp = *this;
     
395.                         ++(*this);
     
396.                         return tmp;
     
397.                 }
     
398. 
     
399.                 bool operator==(const const_data_iterator& other) const {
     
400.                         return current == other.current;
     
401.                 }
     
402. 
     
403.                 bool operator!=(const const_data_iterator& other) const {
     
404.                         return !(*this == other);
     
405.                 }
     
406.         };
     
407. 
     
408.         // 3. 节点指针迭代器（非常量版）
     
409.         class nodePtr_iterator {
     
410.                 Node* current;
     
411.                 const LoopList* parent;
     
412.                 bool firstPass;
     
413. 
     
414.         public:
     
415.                 using iterator_category = std::forward_iterator_tag;
     
416.                 using value_type = Node*;
     
417.                 using difference_type = std::ptrdiff_t;
     
418.                 using pointer = Node**;
     
419.                 using reference = Node*&;
     
420. 
     
421.                 nodePtr_iterator(Node* n = nullptr, const LoopList* p = nullptr, bool first = true)
     
422.                         : current(n), parent(p), firstPass(first&& n != nullptr) {
     
423.                 }
     
424. 
     
425.                 reference operator*() const { return current; }
     
426.                 pointer operator->() const { return ¤t; }
     
427. 
     
428.                 nodePtr_iterator& operator++() {
     
429.                         if (!current) return *this;
     
430.                         current = current->next;
     
431.                         if (current == parent->head) firstPass = false;
     
432.                         if (!firstPass) current = nullptr;
     
433.                         return *this;
     
434.                 }
     
435. 
     
436.                 nodePtr_iterator operator++(int) {
     
437.                         nodePtr_iterator tmp = *this;
     
438.                         ++(*this);
     
439.                         return tmp;
     
440.                 }
     
441. 
     
442.                 bool operator==(const nodePtr_iterator& other) const {
     
443.                         return current == other.current;
     
444.                 }
     
445. 
     
446.                 bool operator!=(const nodePtr_iterator& other) const {
     
447.                         return !(*this == other);
     
448.                 }
     
449.         };
     
450. 
     
451.         // 4. 常量节点指针迭代器
     
452.         class const_nodePtr_iterator {
     
453.                 const Node* current;
     
454.                 const LoopList* parent;
     
455.                 bool firstPass;
     
456. 
     
457.         public:
     
458.                 using iterator_category = std::forward_iterator_tag;
     
459.                 using value_type = const Node*;
     
460.                 using difference_type = std::ptrdiff_t;
     
461.                 using pointer = const Node**;
     
462.                 using reference = const Node*&;
     
463. 
     
464.                 const_nodePtr_iterator(const Node* n = nullptr, const LoopList* p = nullptr, bool first = true)
     
465.                         : current(n), parent(p), firstPass(first&& n != nullptr) {
     
466.                 }
     
467. 
     
468.                 reference operator*() const { return current; }
     
469.                 pointer operator->() const { return ¤t; }
     
470. 
     
471.                 const_nodePtr_iterator& operator++() {
     
472.                         if (!current) return *this;
     
473.                         current = current->next;
     
474.                         if (current == parent->head) firstPass = false;
     
475.                         if (!firstPass) current = nullptr;
     
476.                         return *this;
     
477.                 }
     
478. 
     
479.                 const_nodePtr_iterator operator++(int) {
     
480.                         const_nodePtr_iterator tmp = *this;
     
481.                         ++(*this);
     
482.                         return tmp;
     
483.                 }
     
484. 
     
485.                 bool operator==(const const_nodePtr_iterator& other) const {
     
486.                         return current == other.current;
     
487.                 }
     
488. 
     
489.                 bool operator!=(const const_nodePtr_iterator& other) const {
     
490.                         return !(*this == other);
     
491.                 }
     
492.         };
     
493. 
     
494.         // 迭代器访问方法
     
495.         data_iterator data_begin() noexcept { return data_iterator(head, this); }
     
496.         data_iterator data_end() noexcept { return data_iterator(nullptr, this); }
     
497. 
     
498.         const_data_iterator data_begin() const noexcept { return const_data_iterator(head, this); }
     
499.         const_data_iterator data_end() const noexcept { return const_data_iterator(nullptr, this); }
     
500.         const_data_iterator data_cbegin() const noexcept { return data_begin(); }
     
501.         const_data_iterator data_cend() const noexcept { return data_end(); }
     
502. 
     
503.         nodePtr_iterator node_begin() noexcept { return nodePtr_iterator(head, this); }
     
504.         nodePtr_iterator node_end() noexcept { return nodePtr_iterator(nullptr, this); }
     
505. 
     
506.         const_nodePtr_iterator node_begin() const noexcept { return const_nodePtr_iterator(head, this); }
     
507.         const_nodePtr_iterator node_end() const noexcept { return const_nodePtr_iterator(nullptr, this); }
     
508.         const_nodePtr_iterator node_cbegin() const noexcept { return node_begin(); }
     
509.         const_nodePtr_iterator node_cend() const noexcept { return node_end(); }
     
510. 
     
511.         // 兼容STL的默认迭代器（使用数据迭代器）
     
512.         data_iterator begin() noexcept { return data_begin(); }
     
513.         data_iterator end() noexcept { return data_end(); }
     
514.         const_data_iterator begin() const noexcept { return data_begin(); }
     
515.         const_data_iterator end() const noexcept { return data_end(); }
     
516.         const_data_iterator cbegin() const noexcept { return data_begin(); }
     
517.         const_data_iterator cend() const noexcept { return data_end(); }
     
518. };
     
519. 
     

#pragma once<br /> #include <vector><br /> #include <initializer_list><br /> #include <iostream><br /> #include <stdexcept><br /> #include <utility><br /> <br /> <br /> template<typename T><br /> class LoopList {<br /> public:<br />         struct Node {<br />                 T data;<br />                 Node* prev;<br />                 Node* next;<br /> <br />                 template<typename... Args><br />                 Node(Args&&... args)<br />                         : data(std::forward<Args>(args)...), prev(nullptr), next(nullptr) {<br />                 }<br />         };<br /> protected:<br /> <br />         // 内存池实现 <br />         class NodePool {<br />                 std::vector<Node*> chunks;<br />                 Node* freeList = nullptr;<br />                 size_t nextAllocPos = 0;<br />                 const size_t CHUNK_SIZE = 128;<br /> <br />                 void allocateChunk() {<br />                         Node* newChunk = static_cast<Node*>(::operator new(CHUNK_SIZE * sizeof(Node)));<br />                         chunks.push_back(newChunk);<br />                         nextAllocPos = 0;<br />                 }<br /> <br />         public:<br />                 NodePool() = default;<br /> <br />                 // 禁用拷贝 <br />                 NodePool(const NodePool&) = delete;<br />                 NodePool& operator=(const NodePool&) = delete;<br /> <br />                 // 移动语义 <br />                 NodePool(NodePool&& other) noexcept<br />                         : chunks(std::move(other.chunks)),<br />                         freeList(other.freeList),<br />                         nextAllocPos(other.nextAllocPos) {<br />                         other.freeList = nullptr;<br />                         other.nextAllocPos = 0;<br />                 }<br /> <br />                 NodePool& operator=(NodePool&& other) noexcept {<br />                         if (this != &other) {<br />                                 clear();<br />                                 chunks = std::move(other.chunks);<br />                                 freeList = other.freeList;<br />                                 nextAllocPos = other.nextAllocPos;<br />                                 other.freeList = nullptr;<br />                                 other.nextAllocPos = 0;<br />                         }<br />                         return *this;<br />                 }<br /> <br />                 ~NodePool() {<br />                         clear();<br />                 }<br /> <br />                 void clear() {<br />                         for (auto chunk : chunks) {<br />                                 for (size_t i = 0; i < CHUNK_SIZE; ++i) {<br />                                         if (&chunk[i] != freeList) {<br />                                                 chunk[i].~Node();<br />                                         }<br />                                 }<br />                                 ::operator delete(chunk);<br />                         }<br />                         chunks.clear();<br />                         freeList = nullptr;<br />                 }<br /> <br />                 template<typename... Args><br />                 Node* create(Args&&... args) {<br />                         if (!freeList) {<br />                                 if (chunks.empty() || nextAllocPos >= CHUNK_SIZE) {<br />                                         allocateChunk();<br />                                 }<br />                                 Node* node = &chunks.back()[nextAllocPos++];<br />                                 new (node) Node(std::forward<Args>(args)...);<br />                                 return node;<br />                         }<br /> <br />                         Node* node = freeList;<br />                         freeList = freeList->next;<br />                         new (node) Node(std::forward<Args>(args)...);<br />                         return node;<br />                 }<br /> <br />                 void destroy(Node* node) noexcept {<br />                         node->~Node();<br />                         node->next = freeList;<br />                         freeList = node;<br />                 }<br /> <br />                 void reserve(size_t n) {<br />                         size_t neededChunks = (n + CHUNK_SIZE - 1) / CHUNK_SIZE;<br />                         while (chunks.size() < neededChunks) {<br />                                 allocateChunk();<br />                         }<br />                 }<br />         };<br /> <br /> <br />         NodePool pool;<br />         Node* head = nullptr;<br />         size_t length = 0;<br /> <br />         void initHead(Node* node) noexcept {<br />                 head = node;<br />                 head->prev = head->next = head;<br />         }<br /> <br />         void insertBefore(Node* nextNode, Node* newNode) noexcept {<br />                 newNode->next = nextNode;<br />                 newNode->prev = nextNode->prev;<br />                 nextNode->prev->next = newNode;<br />                 nextNode->prev = newNode;<br />         }<br /> <br /> public:<br />         // 构造/析构<br />         LoopList() = default;<br /> <br />         LoopList(std::initializer_list<T> init) {<br />                 for (auto& item : init) push_back(item);<br />         }<br /> <br />         ~LoopList() { clear(); }<br /> <br />         // 禁用拷贝 <br />         LoopList(const LoopList&) = delete;<br />         LoopList& operator=(const LoopList&) = delete;<br /> <br />         // 移动语义 <br />         LoopList(LoopList&& other) noexcept<br />                 : pool(std::move(other.pool)), head(other.head), length(other.length) {<br />                 other.head = nullptr;<br />                 other.length = 0;<br />         }<br /> <br />         LoopList& operator=(LoopList&& other) noexcept {<br />                 if (this != &other) {<br />                         clear();<br />                         pool = std::move(other.pool);<br />                         head = other.head;<br />                         length = other.length;<br />                         other.head = nullptr;<br />                         other.length = 0;<br />                 }<br />                 return *this;<br />         }<br /> <br />         // 容量 <br />         bool empty() const noexcept { return length == 0; }<br />         size_t size() const noexcept { return length; }<br /> <br />         // 节点访问<br />         Node* front() noexcept { return head; }<br />         const Node* front() const noexcept { return head; }<br />         Node* back() noexcept { return head ? head->prev : nullptr; }<br />         const Node* back() const noexcept { return head ? head->prev : nullptr; }<br /> <br />         // 内存预分配 <br />         void reserve(size_t n) {<br />                 pool.reserve(n);<br />         }<br /> <br />         // 原位构造 <br />         template<typename... Args><br />         Node* emplace_back(Args&&... args) {<br />                 Node* newNode = pool.create(std::forward<Args>(args)...);<br />                 if (!head) {<br />                         initHead(newNode);<br />                 }<br />                 else {<br />                         insertBefore(head, newNode);<br />                 }<br />                 ++length;<br />                 return newNode;<br />         }<br /> <br />         template<typename... Args><br />         Node* emplace_front(Args&&... args) {<br />                 Node* newNode = pool.create(std::forward<Args>(args)...);<br />                 if (!head) {<br />                         initHead(newNode);<br />                 }<br />                 else {<br />                         insertBefore(head, newNode);<br />                         head = newNode;<br />                 }<br />                 ++length;<br />                 return newNode;<br />         }<br /> <br />         // 传统插入<br />         template<typename U = T><br />         Node* push_back(U&& value) {<br />                 return emplace_back(std::forward<U>(value));<br />         }<br /> <br />         template<typename U = T><br />         Node* push_front(U&& value) {<br />                 return emplace_front(std::forward<U>(value));<br />         }<br /> <br />         void pop_front() noexcept {<br />                 if (head) removeNode(head);<br />         }<br /> <br />         void pop_back() noexcept {<br />                 if (head) removeNode(head->prev);<br />         }<br /> <br />         void removeNode(Node* node) noexcept {<br />                 if (!node || !head) return;<br /> <br />                 if (length == 1) {<br />                         head = nullptr;<br />                 }<br />                 else {<br />                         node->prev->next = node->next;<br />                         node->next->prev = node->prev;<br />                         if (node == head) head = head->next;<br />                 }<br /> <br />                 pool.destroy(node);<br />                 --length;<br />         }<br /> <br />         void clear() noexcept {<br />                 while (head) pop_front();<br />         }<br /> <br />         void reverse() noexcept {<br />                 if (length <= 1) return;<br /> <br />                 Node* current = head;<br />                 do {<br />                         std::swap(current->prev, current->next);<br />                         current = current->prev;<br />                 } while (current != head);<br /> <br />                 head = head->next;<br />         }<br />         //相邻节点去重<br />         void uniqueAdjacent() {<br />                 if (length <= 1) return;<br /> <br />                 Node* current = head;<br />                 size_t processed = 0;<br />                 bool hasRemoved = false;<br /> <br />                 do {<br />                         Node* next = current->next;<br />                         if (current->data == next->data) {<br />                                 // 特殊处理头节点 <br />                                 if (next == head) {<br />                                         // 如果头节点和尾节点相同，且不是唯一节点 <br />                                         if (length > 1 && head->data == head->prev->data) {<br />                                                 removeNode(head->prev);<br />                                                 hasRemoved = true;<br />                                         }<br />                                         break;<br />                                 }<br /> <br />                                 removeNode(next);<br />                                 hasRemoved = true;<br />                                 continue;<br />                         }<br />                         current = next;<br />                         processed++;<br /> <br />                         if (processed >= length * 2) break;<br />                 } while (!empty() && current != head && processed < length);<br /> <br />                 // 再次检查头尾是否相同（环形链表特例）<br />                 if (length >= 2 && head->data == head->prev->data) {<br />                         // 保留头节点，删除尾节点 <br />                         removeNode(head->prev);<br />                 }<br />         }<br /> <br />         //转换为std::Vectot<T> <br />         std::vector<T> toVector() const {<br />                 std::vector<T> result;<br />                 if (empty()) return result;<br /> <br />                 result.reserve(length);   // 预分配空间优化性能 <br />                 const Node* current = head;<br />                 do {<br />                         result.push_back(current->data);<br />                         current = current->next;<br />                 } while (current != head);<br /> <br />                 return result;<br />         }<br /> <br />         LoopList deepClone() const {<br />                 LoopList newList;<br />                 if (!empty()) {<br />                         newList.reserve(length);  // 预分配相同容量 <br />                         const Node* current = head;<br />                         do {<br />                                 newList.emplace_back(current->data);  // 深度拷贝每个元素<br />                                 current = current->next;<br />                         } while (current != head);<br />                 }<br />                 return newList; // 利用移动语义返回 <br />         }<br /> <br />         class data_iterator {<br />                 Node* current;<br />                 const LoopList* parent;<br />                 bool firstPass;<br /> <br />         public:<br />                 using iterator_category = std::forward_iterator_tag;<br />                 using value_type = T;<br />                 using difference_type = std::ptrdiff_t;<br />                 using pointer = T*;<br />                 using reference = T&;<br /> <br />                 data_iterator(Node* n = nullptr, const LoopList* p = nullptr, bool first = true)<br />                         : current(n), parent(p), firstPass(first&& n != nullptr) {<br />                 }<br /> <br />                 reference operator*() const { return current->data; }<br />                 pointer operator->() const { return ¤t->data; }<br /> <br />                 data_iterator& operator++() {<br />                         if (!current) return *this;<br />                         current = current->next;<br />                         if (current == parent->head) firstPass = false;<br />                         if (!firstPass) current = nullptr;<br />                         return *this;<br />                 }<br /> <br />                 data_iterator operator++(int) {<br />                         data_iterator tmp = *this;<br />                         ++(*this);<br />                         return tmp;<br />                 }<br /> <br />                 bool operator==(const data_iterator& other) const {<br />                         return current == other.current;<br />                 }<br /> <br />                 bool operator!=(const data_iterator& other) const {<br />                         return !(*this == other);<br />                 }<br />         };<br /> <br />         // 2. 常量数据迭代器 <br />         class const_data_iterator {<br />                 const Node* current;<br />                 const LoopList* parent;<br />                 bool firstPass;<br /> <br />         public:<br />                 using iterator_category = std::forward_iterator_tag;<br />                 using value_type = const T;<br />                 using difference_type = std::ptrdiff_t;<br />                 using pointer = const T*;<br />                 using reference = const T&;<br /> <br />                 const_data_iterator(const Node* n = nullptr, const LoopList* p = nullptr, bool first = true)<br />                         : current(n), parent(p), firstPass(first&& n != nullptr) {<br />                 }<br /> <br />                 reference operator*() const { return current->data; }<br />                 pointer operator->() const { return ¤t->data; }<br /> <br />                 const_data_iterator& operator++() {<br />                         if (!current) return *this;<br />                         current = current->next;<br />                         if (current == parent->head) firstPass = false;<br />                         if (!firstPass) current = nullptr;<br />                         return *this;<br />                 }<br /> <br />                 const_data_iterator operator++(int) {<br />                         const_data_iterator tmp = *this;<br />                         ++(*this);<br />                         return tmp;<br />                 }<br /> <br />                 bool operator==(const const_data_iterator& other) const {<br />                         return current == other.current;<br />                 }<br /> <br />                 bool operator!=(const const_data_iterator& other) const {<br />                         return !(*this == other);<br />                 }<br />         };<br /> <br />         // 3. 节点指针迭代器（非常量版）<br />         class nodePtr_iterator {<br />                 Node* current;<br />                 const LoopList* parent;<br />                 bool firstPass;<br /> <br />         public:<br />                 using iterator_category = std::forward_iterator_tag;<br />                 using value_type = Node*;<br />                 using difference_type = std::ptrdiff_t;<br />                 using pointer = Node**;<br />                 using reference = Node*&;<br /> <br />                 nodePtr_iterator(Node* n = nullptr, const LoopList* p = nullptr, bool first = true)<br />                         : current(n), parent(p), firstPass(first&& n != nullptr) {<br />                 }<br /> <br />                 reference operator*() const { return current; }<br />                 pointer operator->() const { return ¤t; }<br /> <br />                 nodePtr_iterator& operator++() {<br />                         if (!current) return *this;<br />                         current = current->next;<br />                         if (current == parent->head) firstPass = false;<br />                         if (!firstPass) current = nullptr;<br />                         return *this;<br />                 }<br /> <br />                 nodePtr_iterator operator++(int) {<br />                         nodePtr_iterator tmp = *this;<br />                         ++(*this);<br />                         return tmp;<br />                 }<br /> <br />                 bool operator==(const nodePtr_iterator& other) const {<br />                         return current == other.current;<br />                 }<br /> <br />                 bool operator!=(const nodePtr_iterator& other) const {<br />                         return !(*this == other);<br />                 }<br />         };<br /> <br />         // 4. 常量节点指针迭代器 <br />         class const_nodePtr_iterator {<br />                 const Node* current;<br />                 const LoopList* parent;<br />                 bool firstPass;<br /> <br />         public:<br />                 using iterator_category = std::forward_iterator_tag;<br />                 using value_type = const Node*;<br />                 using difference_type = std::ptrdiff_t;<br />                 using pointer = const Node**;<br />                 using reference = const Node*&;<br /> <br />                 const_nodePtr_iterator(const Node* n = nullptr, const LoopList* p = nullptr, bool first = true)<br />                         : current(n), parent(p), firstPass(first&& n != nullptr) {<br />                 }<br /> <br />                 reference operator*() const { return current; }<br />                 pointer operator->() const { return ¤t; }<br /> <br />                 const_nodePtr_iterator& operator++() {<br />                         if (!current) return *this;<br />                         current = current->next;<br />                         if (current == parent->head) firstPass = false;<br />                         if (!firstPass) current = nullptr;<br />                         return *this;<br />                 }<br /> <br />                 const_nodePtr_iterator operator++(int) {<br />                         const_nodePtr_iterator tmp = *this;<br />                         ++(*this);<br />                         return tmp;<br />                 }<br /> <br />                 bool operator==(const const_nodePtr_iterator& other) const {<br />                         return current == other.current;<br />                 }<br /> <br />                 bool operator!=(const const_nodePtr_iterator& other) const {<br />                         return !(*this == other);<br />                 }<br />         };<br /> <br />         // 迭代器访问方法 <br />         data_iterator data_begin() noexcept { return data_iterator(head, this); }<br />         data_iterator data_end() noexcept { return data_iterator(nullptr, this); }<br /> <br />         const_data_iterator data_begin() const noexcept { return const_data_iterator(head, this); }<br />         const_data_iterator data_end() const noexcept { return const_data_iterator(nullptr, this); }<br />         const_data_iterator data_cbegin() const noexcept { return data_begin(); }<br />         const_data_iterator data_cend() const noexcept { return data_end(); }<br /> <br />         nodePtr_iterator node_begin() noexcept { return nodePtr_iterator(head, this); }<br />         nodePtr_iterator node_end() noexcept { return nodePtr_iterator(nullptr, this); }<br /> <br />         const_nodePtr_iterator node_begin() const noexcept { return const_nodePtr_iterator(head, this); }<br />         const_nodePtr_iterator node_end() const noexcept { return const_nodePtr_iterator(nullptr, this); }<br />         const_nodePtr_iterator node_cbegin() const noexcept { return node_begin(); }<br />         const_nodePtr_iterator node_cend() const noexcept { return node_end(); }<br /> <br />         // 兼容STL的默认迭代器（使用数据迭代器）<br />         data_iterator begin() noexcept { return data_begin(); }<br />         data_iterator end() noexcept { return data_end(); }<br />         const_data_iterator begin() const noexcept { return data_begin(); }<br />         const_data_iterator end() const noexcept { return data_end(); }<br />         const_data_iterator cbegin() const noexcept { return data_begin(); }<br />         const_data_iterator cend() const noexcept { return data_end(); }<br /> };<br /> <br />

使用示例：
1. 基础操作示例

1. #include <iostream>
   
2. #include "LoopList.h"
   
3. 
   
4. int main() {
   
5.     // 初始化与插入
   
6.     LoopList<int> list;
   
7.     list.push_back(1);
   
8.     list.push_front(0);           // 头部插入
   
9.     list.emplace_back(2);         // 原位构造
   
10.     list.emplace_front(-1);       // 头部原位构造
    
11. 
    
12.     // 遍历输出（使用数据迭代器）
    
13.     std::cout << "List elements: ";
    
14.     for (const auto& val : list) {
    
15.         std::cout << val << " "; // 输出: -1 0 1 2
    
16.     }
    
17.     std::cout << "\n";
    
18. 
    
19.     // 删除节点
    
20.     list.pop_front();             // 删除-1
    
21.     list.removeNode(list.back());  // 删除尾节点2
    
22. 
    
23.     // 转换为vector
    
24.     auto vec = list.toVector();
    
25.     std::cout << "Vector size: " << vec.size()  << "\n"; // 输出: 2
    
26. }

复制代码

2. 环形特性与内存池验证

1. void testCircularBehavior() {
   
2.     LoopList<std::string> words{"A", "B", "C"};
   
3.    
   
4.     // 验证环形连接
   
5.     auto* head = words.front();
   
6.     auto* thirdNode = head->next->next;
   
7.     std::cout << "Third node next is head: "
   
8.               << (thirdNode->next == head) << "\n"; // 输出: 1 (true)
   
9. 
   
10.     // 内存池预分配
    
11.     words.reserve(100);  // 预分配100个节点内存
    
12.     std::cout << "After reserve, size: " << words.size()  << "\n"; // 输出: 3
    
13. }

复制代码

3. 高级操作：去重与反转

1. void testAdvancedFeatures() {
   
2.     LoopList<int> dupList{1, 1, 2, 3, 3, 3, 4};
   
3.    
   
4.     // 相邻去重
   
5.     dupList.uniqueAdjacent();
   
6.     std::cout << "After uniqueAdjacent: ";
   
7.     for (const auto& val : dupList) {
   
8.         std::cout << val << " "; // 输出: 1 2 3 4
   
9.     }
   
10.     std::cout << "\n";
    
11. 
    
12.     // 反转链表
    
13.     dupList.reverse();
    
14.     std::cout << "After reverse: ";
    
15.     for (const auto& val : dupList) {
    
16.         std::cout << val << " "; // 输出: 4 3 2 1
    
17.     }
    
18. }
    

复制代码

4. 迭代器分类使用

1. void testIterators() {
   
2.     LoopList<double> nums{1.1, 2.2, 3.3};
   
3. 
   
4.     // 数据迭代器（默认）
   
5.     std::cout << "Data iteration: ";
   
6.     for (auto it = nums.begin();  it != nums.end();  ++it) {
   
7.         std::cout << *it << " ";
   
8.     }
   
9. 
   
10.     // 节点指针迭代器（访问节点结构）
    
11.     std::cout << "\nNode addresses: ";
    
12.     for (auto it = nums.node_begin();  it != nums.node_end();  ++it) {
    
13.         std::cout << *it << " "; // 输出节点地址
    
14.     }
    
15. }

复制代码

5. 移动语义与深拷贝

1. void testMoveAndCopy() {
   
2.     LoopList<int> original{10, 20, 30};
   
3.    
   
4.     // 移动构造
   
5.     LoopList<int> moved(std::move(original));
   
6.     std::cout << "Moved size: " << moved.size()  << "\n"; // 输出: 3
   
7.     std::cout << "Original now empty: " << original.empty()  << "\n"; // 输出: 1
   
8. 
   
9.     // 深拷贝
   
10.     auto cloned = moved.deepClone();
    
11.     cloned.push_back(40);
    
12.     std::cout << "Cloned size: " << cloned.size()  << "\n"; // 输出: 4
    
13. }

复制代码

你有种再说一遍

用链表太慢了,如果只是为了回环,大可直接封装vector的访问器回0,也就是静态链表.