- 积分
- 2191
- 明经币
- 个
- 注册时间
- 2022-4-4
- 在线时间
- 小时
- 威望
-
- 金钱
- 个
- 贡献
-
- 激情
-
|
本帖最后由 枫叶棋语 于 2025-6-28 20:43 编辑
有的时候需要一些环形结构操作,闲暇之余,做了一个循环链表,对于封闭的曲线点集操作有些用处
 - #pragma once
- #include <vector>
- #include <initializer_list>
- #include <iostream>
- #include <stdexcept>
- #include <utility>
- template<typename T>
- class LoopList {
- public:
- struct Node {
- T data;
- Node* prev;
- Node* next;
- template<typename... Args>
- Node(Args&&... args)
- : data(std::forward<Args>(args)...), prev(nullptr), next(nullptr) {
- }
- };
- protected:
- // 内存池实现
- class NodePool {
- std::vector<Node*> chunks;
- Node* freeList = nullptr;
- size_t nextAllocPos = 0;
- const size_t CHUNK_SIZE = 128;
- void allocateChunk() {
- Node* newChunk = static_cast<Node*>(::operator new(CHUNK_SIZE * sizeof(Node)));
- chunks.push_back(newChunk);
- nextAllocPos = 0;
- }
- public:
- NodePool() = default;
- // 禁用拷贝
- NodePool(const NodePool&) = delete;
- NodePool& operator=(const NodePool&) = delete;
- // 移动语义
- NodePool(NodePool&& other) noexcept
- : chunks(std::move(other.chunks)),
- freeList(other.freeList),
- nextAllocPos(other.nextAllocPos) {
- other.freeList = nullptr;
- other.nextAllocPos = 0;
- }
- NodePool& operator=(NodePool&& other) noexcept {
- if (this != &other) {
- clear();
- chunks = std::move(other.chunks);
- freeList = other.freeList;
- nextAllocPos = other.nextAllocPos;
- other.freeList = nullptr;
- other.nextAllocPos = 0;
- }
- return *this;
- }
- ~NodePool() {
- clear();
- }
- void clear() {
- for (auto chunk : chunks) {
- for (size_t i = 0; i < CHUNK_SIZE; ++i) {
- if (&chunk[i] != freeList) {
- chunk[i].~Node();
- }
- }
- ::operator delete(chunk);
- }
- chunks.clear();
- freeList = nullptr;
- }
- template<typename... Args>
- Node* create(Args&&... args) {
- if (!freeList) {
- if (chunks.empty() || nextAllocPos >= CHUNK_SIZE) {
- allocateChunk();
- }
- Node* node = &chunks.back()[nextAllocPos++];
- new (node) Node(std::forward<Args>(args)...);
- return node;
- }
- Node* node = freeList;
- freeList = freeList->next;
- new (node) Node(std::forward<Args>(args)...);
- return node;
- }
- void destroy(Node* node) noexcept {
- node->~Node();
- node->next = freeList;
- freeList = node;
- }
- void reserve(size_t n) {
- size_t neededChunks = (n + CHUNK_SIZE - 1) / CHUNK_SIZE;
- while (chunks.size() < neededChunks) {
- allocateChunk();
- }
- }
- };
- NodePool pool;
- Node* head = nullptr;
- size_t length = 0;
- void initHead(Node* node) noexcept {
- head = node;
- head->prev = head->next = head;
- }
- void insertBefore(Node* nextNode, Node* newNode) noexcept {
- newNode->next = nextNode;
- newNode->prev = nextNode->prev;
- nextNode->prev->next = newNode;
- nextNode->prev = newNode;
- }
- public:
- // 构造/析构
- LoopList() = default;
- LoopList(std::initializer_list<T> init) {
- for (auto& item : init) push_back(item);
- }
- ~LoopList() { clear(); }
- // 禁用拷贝
- LoopList(const LoopList&) = delete;
- LoopList& operator=(const LoopList&) = delete;
- // 移动语义
- LoopList(LoopList&& other) noexcept
- : pool(std::move(other.pool)), head(other.head), length(other.length) {
- other.head = nullptr;
- other.length = 0;
- }
- LoopList& operator=(LoopList&& other) noexcept {
- if (this != &other) {
- clear();
- pool = std::move(other.pool);
- head = other.head;
- length = other.length;
- other.head = nullptr;
- other.length = 0;
- }
- return *this;
- }
- // 容量
- bool empty() const noexcept { return length == 0; }
- size_t size() const noexcept { return length; }
- // 节点访问
- Node* front() noexcept { return head; }
- const Node* front() const noexcept { return head; }
- Node* back() noexcept { return head ? head->prev : nullptr; }
- const Node* back() const noexcept { return head ? head->prev : nullptr; }
- // 内存预分配
- void reserve(size_t n) {
- pool.reserve(n);
- }
- // 原位构造
- template<typename... Args>
- Node* emplace_back(Args&&... args) {
- Node* newNode = pool.create(std::forward<Args>(args)...);
- if (!head) {
- initHead(newNode);
- }
- else {
- insertBefore(head, newNode);
- }
- ++length;
- return newNode;
- }
- template<typename... Args>
- Node* emplace_front(Args&&... args) {
- Node* newNode = pool.create(std::forward<Args>(args)...);
- if (!head) {
- initHead(newNode);
- }
- else {
- insertBefore(head, newNode);
- head = newNode;
- }
- ++length;
- return newNode;
- }
- // 传统插入
- template<typename U = T>
- Node* push_back(U&& value) {
- return emplace_back(std::forward<U>(value));
- }
- template<typename U = T>
- Node* push_front(U&& value) {
- return emplace_front(std::forward<U>(value));
- }
- void pop_front() noexcept {
- if (head) removeNode(head);
- }
- void pop_back() noexcept {
- if (head) removeNode(head->prev);
- }
- void removeNode(Node* node) noexcept {
- if (!node || !head) return;
- if (length == 1) {
- head = nullptr;
- }
- else {
- node->prev->next = node->next;
- node->next->prev = node->prev;
- if (node == head) head = head->next;
- }
- pool.destroy(node);
- --length;
- }
- void clear() noexcept {
- while (head) pop_front();
- }
- void reverse() noexcept {
- if (length <= 1) return;
- Node* current = head;
- do {
- std::swap(current->prev, current->next);
- current = current->prev;
- } while (current != head);
- head = head->next;
- }
- //相邻节点去重
- void uniqueAdjacent() {
- if (length <= 1) return;
- Node* current = head;
- size_t processed = 0;
- bool hasRemoved = false;
- do {
- Node* next = current->next;
- if (current->data == next->data) {
- // 特殊处理头节点
- if (next == head) {
- // 如果头节点和尾节点相同,且不是唯一节点
- if (length > 1 && head->data == head->prev->data) {
- removeNode(head->prev);
- hasRemoved = true;
- }
- break;
- }
- removeNode(next);
- hasRemoved = true;
- continue;
- }
- current = next;
- processed++;
- if (processed >= length * 2) break;
- } while (!empty() && current != head && processed < length);
- // 再次检查头尾是否相同(环形链表特例)
- if (length >= 2 && head->data == head->prev->data) {
- // 保留头节点,删除尾节点
- removeNode(head->prev);
- }
- }
- //转换为std::Vectot<T>
- std::vector<T> toVector() const {
- std::vector<T> result;
- if (empty()) return result;
- result.reserve(length); // 预分配空间优化性能
- const Node* current = head;
- do {
- result.push_back(current->data);
- current = current->next;
- } while (current != head);
- return result;
- }
- LoopList deepClone() const {
- LoopList newList;
- if (!empty()) {
- newList.reserve(length); // 预分配相同容量
- const Node* current = head;
- do {
- newList.emplace_back(current->data); // 深度拷贝每个元素
- current = current->next;
- } while (current != head);
- }
- return newList; // 利用移动语义返回
- }
- class data_iterator {
- Node* current;
- const LoopList* parent;
- bool firstPass;
- public:
- using iterator_category = std::forward_iterator_tag;
- using value_type = T;
- using difference_type = std::ptrdiff_t;
- using pointer = T*;
- using reference = T&;
- data_iterator(Node* n = nullptr, const LoopList* p = nullptr, bool first = true)
- : current(n), parent(p), firstPass(first&& n != nullptr) {
- }
- reference operator*() const { return current->data; }
- pointer operator->() const { return ¤t->data; }
- data_iterator& operator++() {
- if (!current) return *this;
- current = current->next;
- if (current == parent->head) firstPass = false;
- if (!firstPass) current = nullptr;
- return *this;
- }
- data_iterator operator++(int) {
- data_iterator tmp = *this;
- ++(*this);
- return tmp;
- }
- bool operator==(const data_iterator& other) const {
- return current == other.current;
- }
- bool operator!=(const data_iterator& other) const {
- return !(*this == other);
- }
- };
- // 2. 常量数据迭代器
- class const_data_iterator {
- const Node* current;
- const LoopList* parent;
- bool firstPass;
- public:
- using iterator_category = std::forward_iterator_tag;
- using value_type = const T;
- using difference_type = std::ptrdiff_t;
- using pointer = const T*;
- using reference = const T&;
- const_data_iterator(const Node* n = nullptr, const LoopList* p = nullptr, bool first = true)
- : current(n), parent(p), firstPass(first&& n != nullptr) {
- }
- reference operator*() const { return current->data; }
- pointer operator->() const { return ¤t->data; }
- const_data_iterator& operator++() {
- if (!current) return *this;
- current = current->next;
- if (current == parent->head) firstPass = false;
- if (!firstPass) current = nullptr;
- return *this;
- }
- const_data_iterator operator++(int) {
- const_data_iterator tmp = *this;
- ++(*this);
- return tmp;
- }
- bool operator==(const const_data_iterator& other) const {
- return current == other.current;
- }
- bool operator!=(const const_data_iterator& other) const {
- return !(*this == other);
- }
- };
- // 3. 节点指针迭代器(非常量版)
- class nodePtr_iterator {
- Node* current;
- const LoopList* parent;
- bool firstPass;
- public:
- using iterator_category = std::forward_iterator_tag;
- using value_type = Node*;
- using difference_type = std::ptrdiff_t;
- using pointer = Node**;
- using reference = Node*&;
- nodePtr_iterator(Node* n = nullptr, const LoopList* p = nullptr, bool first = true)
- : current(n), parent(p), firstPass(first&& n != nullptr) {
- }
- reference operator*() const { return current; }
- pointer operator->() const { return ¤t; }
- nodePtr_iterator& operator++() {
- if (!current) return *this;
- current = current->next;
- if (current == parent->head) firstPass = false;
- if (!firstPass) current = nullptr;
- return *this;
- }
- nodePtr_iterator operator++(int) {
- nodePtr_iterator tmp = *this;
- ++(*this);
- return tmp;
- }
- bool operator==(const nodePtr_iterator& other) const {
- return current == other.current;
- }
- bool operator!=(const nodePtr_iterator& other) const {
- return !(*this == other);
- }
- };
- // 4. 常量节点指针迭代器
- class const_nodePtr_iterator {
- const Node* current;
- const LoopList* parent;
- bool firstPass;
- public:
- using iterator_category = std::forward_iterator_tag;
- using value_type = const Node*;
- using difference_type = std::ptrdiff_t;
- using pointer = const Node**;
- using reference = const Node*&;
- const_nodePtr_iterator(const Node* n = nullptr, const LoopList* p = nullptr, bool first = true)
- : current(n), parent(p), firstPass(first&& n != nullptr) {
- }
- reference operator*() const { return current; }
- pointer operator->() const { return ¤t; }
- const_nodePtr_iterator& operator++() {
- if (!current) return *this;
- current = current->next;
- if (current == parent->head) firstPass = false;
- if (!firstPass) current = nullptr;
- return *this;
- }
- const_nodePtr_iterator operator++(int) {
- const_nodePtr_iterator tmp = *this;
- ++(*this);
- return tmp;
- }
- bool operator==(const const_nodePtr_iterator& other) const {
- return current == other.current;
- }
- bool operator!=(const const_nodePtr_iterator& other) const {
- return !(*this == other);
- }
- };
- // 迭代器访问方法
- data_iterator data_begin() noexcept { return data_iterator(head, this); }
- data_iterator data_end() noexcept { return data_iterator(nullptr, this); }
- const_data_iterator data_begin() const noexcept { return const_data_iterator(head, this); }
- const_data_iterator data_end() const noexcept { return const_data_iterator(nullptr, this); }
- const_data_iterator data_cbegin() const noexcept { return data_begin(); }
- const_data_iterator data_cend() const noexcept { return data_end(); }
- nodePtr_iterator node_begin() noexcept { return nodePtr_iterator(head, this); }
- nodePtr_iterator node_end() noexcept { return nodePtr_iterator(nullptr, this); }
- const_nodePtr_iterator node_begin() const noexcept { return const_nodePtr_iterator(head, this); }
- const_nodePtr_iterator node_end() const noexcept { return const_nodePtr_iterator(nullptr, this); }
- const_nodePtr_iterator node_cbegin() const noexcept { return node_begin(); }
- const_nodePtr_iterator node_cend() const noexcept { return node_end(); }
- // 兼容STL的默认迭代器(使用数据迭代器)
- data_iterator begin() noexcept { return data_begin(); }
- data_iterator end() noexcept { return data_end(); }
- const_data_iterator begin() const noexcept { return data_begin(); }
- const_data_iterator end() const noexcept { return data_end(); }
- const_data_iterator cbegin() const noexcept { return data_begin(); }
- const_data_iterator cend() const noexcept { return data_end(); }
- };
使用示例:
1. 基础操作示例- #include <iostream>
- #include "LoopList.h"
-
- int main() {
- // 初始化与插入
- LoopList<int> list;
- list.push_back(1);
- list.push_front(0); // 头部插入
- list.emplace_back(2); // 原位构造
- list.emplace_front(-1); // 头部原位构造
-
- // 遍历输出(使用数据迭代器)
- std::cout << "List elements: ";
- for (const auto& val : list) {
- std::cout << val << " "; // 输出: -1 0 1 2
- }
- std::cout << "\n";
-
- // 删除节点
- list.pop_front(); // 删除-1
- list.removeNode(list.back()); // 删除尾节点2
-
- // 转换为vector
- auto vec = list.toVector();
- std::cout << "Vector size: " << vec.size() << "\n"; // 输出: 2
- }
复制代码 2. 环形特性与内存池验证
- void testCircularBehavior() {
- LoopList<std::string> words{"A", "B", "C"};
-
- // 验证环形连接
- auto* head = words.front();
- auto* thirdNode = head->next->next;
- std::cout << "Third node next is head: "
- << (thirdNode->next == head) << "\n"; // 输出: 1 (true)
- // 内存池预分配
- words.reserve(100); // 预分配100个节点内存
- std::cout << "After reserve, size: " << words.size() << "\n"; // 输出: 3
- }
复制代码 3. 高级操作:去重与反转
- void testAdvancedFeatures() {
- LoopList<int> dupList{1, 1, 2, 3, 3, 3, 4};
-
- // 相邻去重
- dupList.uniqueAdjacent();
- std::cout << "After uniqueAdjacent: ";
- for (const auto& val : dupList) {
- std::cout << val << " "; // 输出: 1 2 3 4
- }
- std::cout << "\n";
- // 反转链表
- dupList.reverse();
- std::cout << "After reverse: ";
- for (const auto& val : dupList) {
- std::cout << val << " "; // 输出: 4 3 2 1
- }
- }
复制代码 4. 迭代器分类使用
- void testIterators() {
- LoopList<double> nums{1.1, 2.2, 3.3};
- // 数据迭代器(默认)
- std::cout << "Data iteration: ";
- for (auto it = nums.begin(); it != nums.end(); ++it) {
- std::cout << *it << " ";
- }
- // 节点指针迭代器(访问节点结构)
- std::cout << "\nNode addresses: ";
- for (auto it = nums.node_begin(); it != nums.node_end(); ++it) {
- std::cout << *it << " "; // 输出节点地址
- }
- }
复制代码
5. 移动语义与深拷贝
- void testMoveAndCopy() {
- LoopList<int> original{10, 20, 30};
-
- // 移动构造
- LoopList<int> moved(std::move(original));
- std::cout << "Moved size: " << moved.size() << "\n"; // 输出: 3
- std::cout << "Original now empty: " << original.empty() << "\n"; // 输出: 1
- // 深拷贝
- auto cloned = moved.deepClone();
- cloned.push_back(40);
- std::cout << "Cloned size: " << cloned.size() << "\n"; // 输出: 4
- }
复制代码
|
|