明经CAD社区

 找回密码
 注册

QQ登录

只需一步,快速开始

搜索
查看: 299|回复: 1

ObjectArx 双向循环链表 LoopList

  [复制链接]
发表于 2025-6-28 14:23:51 | 显示全部楼层 |阅读模式
本帖最后由 枫叶棋语 于 2025-6-28 20:43 编辑

有的时候需要一些环形结构操作,闲暇之余,做了一个循环链表,对于封闭的曲线点集操作有些用处
  1. #pragma once
  2. #include <vector>
  3. #include <initializer_list>
  4. #include <iostream>
  5. #include <stdexcept>
  6. #include <utility>


  7. template<typename T>
  8. class LoopList {
  9. public:
  10.         struct Node {
  11.                 T data;
  12.                 Node* prev;
  13.                 Node* next;

  14.                 template<typename... Args>
  15.                 Node(Args&&... args)
  16.                         : data(std::forward<Args>(args)...), prev(nullptr), next(nullptr) {
  17.                 }
  18.         };
  19. protected:

  20.         // 内存池实现
  21.         class NodePool {
  22.                 std::vector<Node*> chunks;
  23.                 Node* freeList = nullptr;
  24.                 size_t nextAllocPos = 0;
  25.                 const size_t CHUNK_SIZE = 128;

  26.                 void allocateChunk() {
  27.                         Node* newChunk = static_cast<Node*>(::operator new(CHUNK_SIZE * sizeof(Node)));
  28.                         chunks.push_back(newChunk);
  29.                         nextAllocPos = 0;
  30.                 }

  31.         public:
  32.                 NodePool() = default;

  33.                 // 禁用拷贝
  34.                 NodePool(const NodePool&) = delete;
  35.                 NodePool& operator=(const NodePool&) = delete;

  36.                 // 移动语义
  37.                 NodePool(NodePool&& other) noexcept
  38.                         : chunks(std::move(other.chunks)),
  39.                         freeList(other.freeList),
  40.                         nextAllocPos(other.nextAllocPos) {
  41.                         other.freeList = nullptr;
  42.                         other.nextAllocPos = 0;
  43.                 }

  44.                 NodePool& operator=(NodePool&& other) noexcept {
  45.                         if (this != &other) {
  46.                                 clear();
  47.                                 chunks = std::move(other.chunks);
  48.                                 freeList = other.freeList;
  49.                                 nextAllocPos = other.nextAllocPos;
  50.                                 other.freeList = nullptr;
  51.                                 other.nextAllocPos = 0;
  52.                         }
  53.                         return *this;
  54.                 }

  55.                 ~NodePool() {
  56.                         clear();
  57.                 }

  58.                 void clear() {
  59.                         for (auto chunk : chunks) {
  60.                                 for (size_t i = 0; i < CHUNK_SIZE; ++i) {
  61.                                         if (&chunk[i] != freeList) {
  62.                                                 chunk[i].~Node();
  63.                                         }
  64.                                 }
  65.                                 ::operator delete(chunk);
  66.                         }
  67.                         chunks.clear();
  68.                         freeList = nullptr;
  69.                 }

  70.                 template<typename... Args>
  71.                 Node* create(Args&&... args) {
  72.                         if (!freeList) {
  73.                                 if (chunks.empty() || nextAllocPos >= CHUNK_SIZE) {
  74.                                         allocateChunk();
  75.                                 }
  76.                                 Node* node = &chunks.back()[nextAllocPos++];
  77.                                 new (node) Node(std::forward<Args>(args)...);
  78.                                 return node;
  79.                         }

  80.                         Node* node = freeList;
  81.                         freeList = freeList->next;
  82.                         new (node) Node(std::forward<Args>(args)...);
  83.                         return node;
  84.                 }

  85.                 void destroy(Node* node) noexcept {
  86.                         node->~Node();
  87.                         node->next = freeList;
  88.                         freeList = node;
  89.                 }

  90.                 void reserve(size_t n) {
  91.                         size_t neededChunks = (n + CHUNK_SIZE - 1) / CHUNK_SIZE;
  92.                         while (chunks.size() < neededChunks) {
  93.                                 allocateChunk();
  94.                         }
  95.                 }
  96.         };


  97.         NodePool pool;
  98.         Node* head = nullptr;
  99.         size_t length = 0;

  100.         void initHead(Node* node) noexcept {
  101.                 head = node;
  102.                 head->prev = head->next = head;
  103.         }

  104.         void insertBefore(Node* nextNode, Node* newNode) noexcept {
  105.                 newNode->next = nextNode;
  106.                 newNode->prev = nextNode->prev;
  107.                 nextNode->prev->next = newNode;
  108.                 nextNode->prev = newNode;
  109.         }

  110. public:
  111.         // 构造/析构
  112.         LoopList() = default;

  113.         LoopList(std::initializer_list<T> init) {
  114.                 for (auto& item : init) push_back(item);
  115.         }

  116.         ~LoopList() { clear(); }

  117.         // 禁用拷贝
  118.         LoopList(const LoopList&) = delete;
  119.         LoopList& operator=(const LoopList&) = delete;

  120.         // 移动语义
  121.         LoopList(LoopList&& other) noexcept
  122.                 : pool(std::move(other.pool)), head(other.head), length(other.length) {
  123.                 other.head = nullptr;
  124.                 other.length = 0;
  125.         }

  126.         LoopList& operator=(LoopList&& other) noexcept {
  127.                 if (this != &other) {
  128.                         clear();
  129.                         pool = std::move(other.pool);
  130.                         head = other.head;
  131.                         length = other.length;
  132.                         other.head = nullptr;
  133.                         other.length = 0;
  134.                 }
  135.                 return *this;
  136.         }

  137.         // 容量
  138.         bool empty() const noexcept { return length == 0; }
  139.         size_t size() const noexcept { return length; }

  140.         // 节点访问
  141.         Node* front() noexcept { return head; }
  142.         const Node* front() const noexcept { return head; }
  143.         Node* back() noexcept { return head ? head->prev : nullptr; }
  144.         const Node* back() const noexcept { return head ? head->prev : nullptr; }

  145.         // 内存预分配
  146.         void reserve(size_t n) {
  147.                 pool.reserve(n);
  148.         }

  149.         // 原位构造
  150.         template<typename... Args>
  151.         Node* emplace_back(Args&&... args) {
  152.                 Node* newNode = pool.create(std::forward<Args>(args)...);
  153.                 if (!head) {
  154.                         initHead(newNode);
  155.                 }
  156.                 else {
  157.                         insertBefore(head, newNode);
  158.                 }
  159.                 ++length;
  160.                 return newNode;
  161.         }

  162.         template<typename... Args>
  163.         Node* emplace_front(Args&&... args) {
  164.                 Node* newNode = pool.create(std::forward<Args>(args)...);
  165.                 if (!head) {
  166.                         initHead(newNode);
  167.                 }
  168.                 else {
  169.                         insertBefore(head, newNode);
  170.                         head = newNode;
  171.                 }
  172.                 ++length;
  173.                 return newNode;
  174.         }

  175.         // 传统插入
  176.         template<typename U = T>
  177.         Node* push_back(U&& value) {
  178.                 return emplace_back(std::forward<U>(value));
  179.         }

  180.         template<typename U = T>
  181.         Node* push_front(U&& value) {
  182.                 return emplace_front(std::forward<U>(value));
  183.         }

  184.         void pop_front() noexcept {
  185.                 if (head) removeNode(head);
  186.         }

  187.         void pop_back() noexcept {
  188.                 if (head) removeNode(head->prev);
  189.         }

  190.         void removeNode(Node* node) noexcept {
  191.                 if (!node || !head) return;

  192.                 if (length == 1) {
  193.                         head = nullptr;
  194.                 }
  195.                 else {
  196.                         node->prev->next = node->next;
  197.                         node->next->prev = node->prev;
  198.                         if (node == head) head = head->next;
  199.                 }

  200.                 pool.destroy(node);
  201.                 --length;
  202.         }

  203.         void clear() noexcept {
  204.                 while (head) pop_front();
  205.         }

  206.         void reverse() noexcept {
  207.                 if (length <= 1) return;

  208.                 Node* current = head;
  209.                 do {
  210.                         std::swap(current->prev, current->next);
  211.                         current = current->prev;
  212.                 } while (current != head);

  213.                 head = head->next;
  214.         }
  215.         //相邻节点去重
  216.         void uniqueAdjacent() {
  217.                 if (length <= 1) return;

  218.                 Node* current = head;
  219.                 size_t processed = 0;
  220.                 bool hasRemoved = false;

  221.                 do {
  222.                         Node* next = current->next;
  223.                         if (current->data == next->data) {
  224.                                 // 特殊处理头节点
  225.                                 if (next == head) {
  226.                                         // 如果头节点和尾节点相同,且不是唯一节点
  227.                                         if (length > 1 && head->data == head->prev->data) {
  228.                                                 removeNode(head->prev);
  229.                                                 hasRemoved = true;
  230.                                         }
  231.                                         break;
  232.                                 }

  233.                                 removeNode(next);
  234.                                 hasRemoved = true;
  235.                                 continue;
  236.                         }
  237.                         current = next;
  238.                         processed++;

  239.                         if (processed >= length * 2) break;
  240.                 } while (!empty() && current != head && processed < length);

  241.                 // 再次检查头尾是否相同(环形链表特例)
  242.                 if (length >= 2 && head->data == head->prev->data) {
  243.                         // 保留头节点,删除尾节点
  244.                         removeNode(head->prev);
  245.                 }
  246.         }

  247.         //转换为std::Vectot<T>
  248.         std::vector<T> toVector() const {
  249.                 std::vector<T> result;
  250.                 if (empty()) return result;

  251.                 result.reserve(length);   // 预分配空间优化性能
  252.                 const Node* current = head;
  253.                 do {
  254.                         result.push_back(current->data);
  255.                         current = current->next;
  256.                 } while (current != head);

  257.                 return result;
  258.         }

  259.         LoopList deepClone() const {
  260.                 LoopList newList;
  261.                 if (!empty()) {
  262.                         newList.reserve(length);  // 预分配相同容量
  263.                         const Node* current = head;
  264.                         do {
  265.                                 newList.emplace_back(current->data);  // 深度拷贝每个元素
  266.                                 current = current->next;
  267.                         } while (current != head);
  268.                 }
  269.                 return newList; // 利用移动语义返回
  270.         }

  271.         class data_iterator {
  272.                 Node* current;
  273.                 const LoopList* parent;
  274.                 bool firstPass;

  275.         public:
  276.                 using iterator_category = std::forward_iterator_tag;
  277.                 using value_type = T;
  278.                 using difference_type = std::ptrdiff_t;
  279.                 using pointer = T*;
  280.                 using reference = T&;

  281.                 data_iterator(Node* n = nullptr, const LoopList* p = nullptr, bool first = true)
  282.                         : current(n), parent(p), firstPass(first&& n != nullptr) {
  283.                 }

  284.                 reference operator*() const { return current->data; }
  285.                 pointer operator->() const { return ¤t->data; }

  286.                 data_iterator& operator++() {
  287.                         if (!current) return *this;
  288.                         current = current->next;
  289.                         if (current == parent->head) firstPass = false;
  290.                         if (!firstPass) current = nullptr;
  291.                         return *this;
  292.                 }

  293.                 data_iterator operator++(int) {
  294.                         data_iterator tmp = *this;
  295.                         ++(*this);
  296.                         return tmp;
  297.                 }

  298.                 bool operator==(const data_iterator& other) const {
  299.                         return current == other.current;
  300.                 }

  301.                 bool operator!=(const data_iterator& other) const {
  302.                         return !(*this == other);
  303.                 }
  304.         };

  305.         // 2. 常量数据迭代器
  306.         class const_data_iterator {
  307.                 const Node* current;
  308.                 const LoopList* parent;
  309.                 bool firstPass;

  310.         public:
  311.                 using iterator_category = std::forward_iterator_tag;
  312.                 using value_type = const T;
  313.                 using difference_type = std::ptrdiff_t;
  314.                 using pointer = const T*;
  315.                 using reference = const T&;

  316.                 const_data_iterator(const Node* n = nullptr, const LoopList* p = nullptr, bool first = true)
  317.                         : current(n), parent(p), firstPass(first&& n != nullptr) {
  318.                 }

  319.                 reference operator*() const { return current->data; }
  320.                 pointer operator->() const { return ¤t->data; }

  321.                 const_data_iterator& operator++() {
  322.                         if (!current) return *this;
  323.                         current = current->next;
  324.                         if (current == parent->head) firstPass = false;
  325.                         if (!firstPass) current = nullptr;
  326.                         return *this;
  327.                 }

  328.                 const_data_iterator operator++(int) {
  329.                         const_data_iterator tmp = *this;
  330.                         ++(*this);
  331.                         return tmp;
  332.                 }

  333.                 bool operator==(const const_data_iterator& other) const {
  334.                         return current == other.current;
  335.                 }

  336.                 bool operator!=(const const_data_iterator& other) const {
  337.                         return !(*this == other);
  338.                 }
  339.         };

  340.         // 3. 节点指针迭代器(非常量版)
  341.         class nodePtr_iterator {
  342.                 Node* current;
  343.                 const LoopList* parent;
  344.                 bool firstPass;

  345.         public:
  346.                 using iterator_category = std::forward_iterator_tag;
  347.                 using value_type = Node*;
  348.                 using difference_type = std::ptrdiff_t;
  349.                 using pointer = Node**;
  350.                 using reference = Node*&;

  351.                 nodePtr_iterator(Node* n = nullptr, const LoopList* p = nullptr, bool first = true)
  352.                         : current(n), parent(p), firstPass(first&& n != nullptr) {
  353.                 }

  354.                 reference operator*() const { return current; }
  355.                 pointer operator->() const { return ¤t; }

  356.                 nodePtr_iterator& operator++() {
  357.                         if (!current) return *this;
  358.                         current = current->next;
  359.                         if (current == parent->head) firstPass = false;
  360.                         if (!firstPass) current = nullptr;
  361.                         return *this;
  362.                 }

  363.                 nodePtr_iterator operator++(int) {
  364.                         nodePtr_iterator tmp = *this;
  365.                         ++(*this);
  366.                         return tmp;
  367.                 }

  368.                 bool operator==(const nodePtr_iterator& other) const {
  369.                         return current == other.current;
  370.                 }

  371.                 bool operator!=(const nodePtr_iterator& other) const {
  372.                         return !(*this == other);
  373.                 }
  374.         };

  375.         // 4. 常量节点指针迭代器
  376.         class const_nodePtr_iterator {
  377.                 const Node* current;
  378.                 const LoopList* parent;
  379.                 bool firstPass;

  380.         public:
  381.                 using iterator_category = std::forward_iterator_tag;
  382.                 using value_type = const Node*;
  383.                 using difference_type = std::ptrdiff_t;
  384.                 using pointer = const Node**;
  385.                 using reference = const Node*&;

  386.                 const_nodePtr_iterator(const Node* n = nullptr, const LoopList* p = nullptr, bool first = true)
  387.                         : current(n), parent(p), firstPass(first&& n != nullptr) {
  388.                 }

  389.                 reference operator*() const { return current; }
  390.                 pointer operator->() const { return ¤t; }

  391.                 const_nodePtr_iterator& operator++() {
  392.                         if (!current) return *this;
  393.                         current = current->next;
  394.                         if (current == parent->head) firstPass = false;
  395.                         if (!firstPass) current = nullptr;
  396.                         return *this;
  397.                 }

  398.                 const_nodePtr_iterator operator++(int) {
  399.                         const_nodePtr_iterator tmp = *this;
  400.                         ++(*this);
  401.                         return tmp;
  402.                 }

  403.                 bool operator==(const const_nodePtr_iterator& other) const {
  404.                         return current == other.current;
  405.                 }

  406.                 bool operator!=(const const_nodePtr_iterator& other) const {
  407.                         return !(*this == other);
  408.                 }
  409.         };

  410.         // 迭代器访问方法
  411.         data_iterator data_begin() noexcept { return data_iterator(head, this); }
  412.         data_iterator data_end() noexcept { return data_iterator(nullptr, this); }

  413.         const_data_iterator data_begin() const noexcept { return const_data_iterator(head, this); }
  414.         const_data_iterator data_end() const noexcept { return const_data_iterator(nullptr, this); }
  415.         const_data_iterator data_cbegin() const noexcept { return data_begin(); }
  416.         const_data_iterator data_cend() const noexcept { return data_end(); }

  417.         nodePtr_iterator node_begin() noexcept { return nodePtr_iterator(head, this); }
  418.         nodePtr_iterator node_end() noexcept { return nodePtr_iterator(nullptr, this); }

  419.         const_nodePtr_iterator node_begin() const noexcept { return const_nodePtr_iterator(head, this); }
  420.         const_nodePtr_iterator node_end() const noexcept { return const_nodePtr_iterator(nullptr, this); }
  421.         const_nodePtr_iterator node_cbegin() const noexcept { return node_begin(); }
  422.         const_nodePtr_iterator node_cend() const noexcept { return node_end(); }

  423.         // 兼容STL的默认迭代器(使用数据迭代器)
  424.         data_iterator begin() noexcept { return data_begin(); }
  425.         data_iterator end() noexcept { return data_end(); }
  426.         const_data_iterator begin() const noexcept { return data_begin(); }
  427.         const_data_iterator end() const noexcept { return data_end(); }
  428.         const_data_iterator cbegin() const noexcept { return data_begin(); }
  429.         const_data_iterator cend() const noexcept { return data_end(); }
  430. };


使用示例:
1. 基础操作示例
  1. #include <iostream>
  2. #include "LoopList.h"

  3. int main() {
  4.     // 初始化与插入
  5.     LoopList<int> list;
  6.     list.push_back(1);
  7.     list.push_front(0);           // 头部插入
  8.     list.emplace_back(2);         // 原位构造
  9.     list.emplace_front(-1);       // 头部原位构造

  10.     // 遍历输出(使用数据迭代器)
  11.     std::cout << "List elements: ";
  12.     for (const auto& val : list) {
  13.         std::cout << val << " "; // 输出: -1 0 1 2
  14.     }
  15.     std::cout << "\n";

  16.     // 删除节点
  17.     list.pop_front();             // 删除-1
  18.     list.removeNode(list.back());  // 删除尾节点2

  19.     // 转换为vector
  20.     auto vec = list.toVector();
  21.     std::cout << "Vector size: " << vec.size()  << "\n"; // 输出: 2
  22. }
复制代码
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.     words.reserve(100);  // 预分配100个节点内存
  11.     std::cout << "After reserve, size: " << words.size()  << "\n"; // 输出: 3
  12. }
复制代码
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.     dupList.reverse();
  13.     std::cout << "After reverse: ";
  14.     for (const auto& val : dupList) {
  15.         std::cout << val << " "; // 输出: 4 3 2 1
  16.     }
  17. }
复制代码
4. 迭代器分类使用
  1. void testIterators() {
  2.     LoopList<double> nums{1.1, 2.2, 3.3};

  3.     // 数据迭代器(默认)
  4.     std::cout << "Data iteration: ";
  5.     for (auto it = nums.begin();  it != nums.end();  ++it) {
  6.         std::cout << *it << " ";
  7.     }

  8.     // 节点指针迭代器(访问节点结构)
  9.     std::cout << "\nNode addresses: ";
  10.     for (auto it = nums.node_begin();  it != nums.node_end();  ++it) {
  11.         std::cout << *it << " "; // 输出节点地址
  12.     }
  13. }
复制代码

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.     auto cloned = moved.deepClone();
  10.     cloned.push_back(40);
  11.     std::cout << "Cloned size: " << cloned.size()  << "\n"; // 输出: 4
  12. }
复制代码










回复

使用道具 举报

发表于 2025-6-28 15:45:26 | 显示全部楼层
用链表太慢了,如果只是为了回环,大可直接封装vector的访问器回0,也就是静态链表.
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

本版积分规则

小黑屋|手机版|CAD论坛|CAD教程|CAD下载|联系我们|关于明经|明经通道 ( 粤ICP备05003914号 )  
©2000-2023 明经通道 版权所有 本站代码,在未取得本站及作者授权的情况下,不得用于商业用途

GMT+8, 2025-7-27 04:09 , Processed in 0.136287 second(s), 22 queries , Gzip On.

Powered by Discuz! X3.4

Copyright © 2001-2021, Tencent Cloud.

快速回复 返回顶部 返回列表