ist的实际上是一个双向链表,本篇文章简单的实现一个list
首先创建一个节点模板类:
template <typename T> class MListNode { public: MListNode<T> *next = nullptr; MListNode<T> *prev = nullptr; T data; };
接下来创建迭代器类,迭代器中包含一个节点的指针,并通过该指针来完成自增自减、比较、和获取值等效果。
template <typename T> class MList; template <typename T> class MListIterator { public: MListIterator(MListNode<T> *p) : node(p){} MListIterator() {} ~MListIterator() {} // 重载前++ MListIterator& operator++ () { node = node->next; return *this; } // 重载后++ MListIterator operator++ (int) { MListIterator temp = *this; node = node->next; return temp; } // 重载前-- MListIterator& operator-- () { node = node->prev; return *this; } // 重载后-- MListIterator operator-- (int) { MListIterator temp; --*this; return temp; } // 重载* T& operator* () { return node->data; } // 重载-> T* operator-> () { return &(node->data); } // 重载 == bool operator== (const MListIterator &itor) { return (node == itor.node); } // 重载 != bool operator!= (const MListIterator& itor) { return (node != itor.node); } friend class MList<T>; private: MListNode<T> *node = nullptr; };
最后实现自己的list列表类,列表初始化时,创建一个头节点(尾节点)并且头尾指针指向自己
template <typename T> class MList { public: typedef MListIterator<T> iterator; public: MList() { m_Node = new MListNode<T>; m_Node->next = m_Node; m_Node->prev = m_Node; } ~MList() { while (m_Length) pop_back(); } iterator begin(void) { return m_Node->next; } iterator end(void) { return m_Node; } // 尾部插入数据 void push_back(const T& d) { insert(end(), d); } // 尾部删除 void pop_back(void) { if (m_Length <= 0) return; erase(--end()); } // 顶部插入数据 void push_front(const T& d) { insert(begin(), d); } // 顶部删除 void pop_front(void) { if (m_Length <= 0) return; erase(begin()); } // 任意位置插入 void insert(iterator& itor, const T& d) { MListNode<T> *node = new MListNode<T>; node->prev = itor.node->prev; node->next = itor.node; node->data = d; itor.node->prev->next = node; itor.node->prev = node; m_Length++; } // 删除元素 void erase(iterator& itor) { itor.node->prev->next = itor.node->next; itor.node->next->prev = itor.node->prev; delete itor.node; m_Length--; } // 获取大小 int size(void) { return m_Length; } // 查找 iterator find(T d) { for (MList<int>::iterator itor = begin(); itor != end(); ++itor) if (d == *itor) return itor; return end(); } private: MListNode<T> *m_Node = nullptr; int m_Length = 0; };
这里 typedef MListIterator iterator; 定义了list的迭代器。并简单实现了 begin() 、end() 、 push_back() 、push_front() 、pop_back() 、pop_front() 等插入删除节点的函数,包括获取容器存储数据大小的函数 size() 和查找函数 find()
测试代码如下:
MList<int> nList; nList.push_back(10); nList.push_back(20); nList.push_back(30); nList.push_front(0); for (MList<int>::iterator itor = nList.begin(); itor != nList.end(); ++itor) std::cout << *itor << std::endl; std::cout << "List Size is " << nList.size() << std::endl; std::cout << "----------------------------------------------------" << std::endl; nList.pop_back(); nList.pop_front(); for (MList<int>::iterator itor = nList.begin(); itor != nList.end(); ++itor) std::cout << *itor << std::endl; std::cout << "List Size is " << nList.size() << std::endl; std::cout << "----------------------------------------------------" << std::endl; if (nList.find(10) != nList.end()) std::cout << "Finded Number 10" << std::endl; else std::cout << "Can't Find Number 10" << std::endl; if (nList.find(0) != nList.end()) std::cout << "Finded Number 0" << std::endl; else std::cout << "Can't Find Number 0" << std::endl;
运行结果:
0
10
20
30
List Size is 4
----------------------------------------------------
10
20
List Size is 2
----------------------------------------------------
Finded Number 10
Can’t Find Number 0
程序的完整代码如下:
#include <iostream> #include <stdlib.h> #include <list> template <typename T> class MListNode { public: MListNode<T> *next = nullptr; MListNode<T> *prev = nullptr; T data; }; template <typename T> class MList; template <typename T> class MListIterator { public: MListIterator(MListNode<T> *p) : node(p){} MListIterator() {} ~MListIterator() {} // 重载前++ MListIterator& operator++ () { node = node->next; return *this; } // 重载后++ MListIterator operator++ (int) { MListIterator temp = *this; node = node->next; return temp; } // 重载前-- MListIterator& operator-- () { node = node->prev; return *this; } // 重载后-- MListIterator operator-- (int) { MListIterator temp; --*this; return temp; } // 重载* T& operator* () { return node->data; } // 重载-> T* operator-> () { return &(node->data); } // 重载 == bool operator== (const MListIterator &itor) { return (node == itor.node); } // 重载 != bool operator!= (const MListIterator& itor) { return (node != itor.node); } friend class MList<T>; private: MListNode<T> *node = nullptr; }; template <typename T> class MList { public: typedef MListIterator<T> iterator; public: MList() { m_Node = new MListNode<T>; m_Node->next = m_Node; m_Node->prev = m_Node; } ~MList() { while (m_Length) pop_back(); } iterator begin(void) { return m_Node->next; } iterator end(void) { return m_Node; } // 尾部插入数据 void push_back(const T& d) { insert(end(), d); } // 尾部删除 void pop_back(void) { if (m_Length <= 0) return; erase(--end()); } // 顶部插入数据 void push_front(const T& d) { insert(begin(), d); } // 顶部删除 void pop_front(void) { if (m_Length <= 0) return; erase(begin()); } // 任意位置插入 void insert(iterator& itor, const T& d) { MListNode<T> *node = new MListNode<T>; node->prev = itor.node->prev; node->next = itor.node; node->data = d; itor.node->prev->next = node; itor.node->prev = node; m_Length++; } // 删除元素 void erase(iterator& itor) { itor.node->prev->next = itor.node->next; itor.node->next->prev = itor.node->prev; delete itor.node; m_Length--; } // 获取大小 int size(void) { return m_Length; } // 查找 iterator find(T d) { for (MList<int>::iterator itor = begin(); itor != end(); ++itor) if (d == *itor) return itor; return end(); } private: MListNode<T> *m_Node = nullptr; int m_Length = 0; }; int main(int argc, char** argv) { MList<int> nList; nList.push_back(10); nList.push_back(20); nList.push_back(30); nList.push_front(0); for (MList<int>::iterator itor = nList.begin(); itor != nList.end(); ++itor) std::cout << *itor << std::endl; std::cout << "List Size is " << nList.size() << std::endl; std::cout << "----------------------------------------------------" << std::endl; nList.pop_back(); nList.pop_front(); for (MList<int>::iterator itor = nList.begin(); itor != nList.end(); ++itor) std::cout << *itor << std::endl; std::cout << "List Size is " << nList.size() << std::endl; std::cout << "----------------------------------------------------" << std::endl; if (nList.find(10) != nList.end()) std::cout << "Finded Number 10" << std::endl; else std::cout << "Can't Find Number 10" << std::endl; if (nList.find(0) != nList.end()) std::cout << "Finded Number 0" << std::endl; else std::cout << "Can't Find Number 0" << std::endl; system("pause"); return 0; }
预览: