【C++】list模拟实现

📝前言：
这篇文章我们来讲讲STL中list的模拟实现：

🎬个人简介：努力学习ing
📋个人专栏：C++学习笔记
🎀CSDN主页 愚润求学
🌄其他专栏：C语言入门基础，python入门基础，python刷题专栏

---

一，简单了解STL中的list

1. list的特点

1. list也是一个类模板
   
2. list的结构是：带哨兵节点的双向循环链表
3. list的迭代器性质是：双向迭代器
   

迭代器的区别

迭代器按性质分可以分为：
随机迭代器，双向迭代器，单向迭代器，只读/只写迭代器，越往后能实现的功能越少。能用双向的地方就也可以用随机…其他的同理。
迭代器的性质（功能）由底层容器的结构决定

迭代器类型	可实现操作
随机	++、–、+n、-n
双向迭代器	++、–
单向迭代器	++

2. list的常用用法

大多数接口和用法与string和vector类似，就不过多介绍了，使用时要查看具体的用法细节，可以查看list文档介绍

这里特别提一下排序算法sort()

排序问题

首先，<algorithm>里面的sort()函数，接收的是一个RandomAccessIterator迭代器（即随机迭代器）：

但是list的迭代器是双向迭代器，所以不能使用库里的sort()

因此，如果想直接对list进行排序，需要使用list自己的sort方法：

但是，当元素个数很多的时候，list.sotr()的效率会很低。因为插入删除的时间复杂度虽然是O(1)，但是访问元素的时间复杂度却是O(n)

提升效率

所以，当元素个数很多的时候，推荐先把list的元素拷贝到vector，然后再在vector内对元素排序，排序好后，再拷贝回给list
如：

#include <iostream>
#include <list>
#include <vector>
#include <algorithm>int main() {std::list<int> myList = {5, 3, 8, 1, 2};// 将元素从list拷贝到vectorstd::vector<int> myVector(myList.begin(), myList.end());// 在vector中排序std::sort(myVector.begin(), myVector.end());// 将排序后的元素从vector拷贝回listmyList.assign(myVector.begin(), myVector.end());for (int num : myList) {std::cout << num << " ";}std::cout << std::endl;return 0;
}

assign直接修改原容器：

二，list的模拟实现

1. 实现功能汇总

主要实现三个类，及链表类中的五大功能/接口
类包括：

• list类
• list的节点类
• list的迭代器类

链表中五大功能/接口;

• 构造及析构
• 迭代器操作
• 容量操作
• 访问操作
• 修改操作

#include<iostream>
using namespace std;namespace tr
{// List的节点类template<class T>struct ListNode{ListNode(const T& val = T());ListNode<T>* _pPre;ListNode<T>* _pNext;T _val;};//List的迭代器类template<class T, class Ref, class Ptr>struct ListIterator{typedef ListNode<T>* PNode;typedef ListIterator<T, Ref, Ptr> Self;ListIterator(PNode pNode = nullptr);ListIterator(const Self& l);T& operator*();T* operator->();Self& operator++();Self operator++(int);Self& operator--();Self& operator--(int);bool operator!=(const Self& l);bool operator==(const Self& l);PNode _pNode;};//list类template<class T>class list{typedef ListNode<T> Node;typedef Node* PNode;public:typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T, const T&, const T&> const_iterator;public:// List的构造void CreateHead();list();list(int n, const T& value = T());template <class Iterator>list(Iterator first, Iterator last);list(const list<T>& l);list<T>& operator=(const list<T> l);~list();// List Iteratoriterator begin();iterator end();const_iterator begin();const_iterator end();// List Capacitysize_t size()const;bool empty()const;// List AccessT& front();const T& front()const;T& back();const T& back()const;// List Modifyvoid push_back(const T& val) { insert(end(), val); }void pop_back() { erase(--end()); }void push_front(const T& val) { insert(begin(), val); }void pop_front() { erase(begin()); }// 在pos位置前插入值为val的节点iterator insert(iterator pos, const T& val);// 删除pos位置的节点，返回该节点的下一个位置iterator erase(iterator pos);void clear();void swap(list<T>& l);private:PNode _pHead;};
};

2. 三大类的实现

b. 链表节点类

    template<class T>struct ListNode // struct 默认成员是公共的{ListNode(const T& val = T()):_pPre(nullptr),_pNext(nullptr),_val(val){ }ListNode<T>* _pPre;ListNode<T>* _pNext;T _val;};

• struct 默认成员是公共的
• ListNode<T> 是模板类 ListNode 在指定模板参数为 T 时所形成的具体类型。T不同时，ListNode不同，ListNode*也不同

c. 链表迭代器类

迭代器的成员是指针，但是因为链表的存储空间并不连续，对指针本身直接进行操作无法实现自增，自减。所以需要自行实现，并且把这些功能封装起来，形成迭代器。

template<class T, class Ref, class Ptr>
struct ListIterator
{typedef ListNode<T>* PNode;typedef ListIterator<T, Ref, Ptr> Self; ListIterator(PNode pNode = nullptr):_pNode(pNode){ }ListIterator(const Self& l){_pNode = l._pNode;}Ref operator*(){return (*_pNode)._val;}Ptr operator->()  // ???{return &((*_pNode)._val);}Self& operator++(){_pNode = _pNode->_pNext;return *this; }Self operator++(int){Self tmp(_pNode);_pNode = _pNode->_pNext;return tmp;}Self& operator--(){_pNode = _pNode->_pPre;return *this;}Self operator--(int)  {Self tmp(_pNode);_pNode = _pNode->_pPre;return tmp;}bool operator!=(const Self& l){return _pNode != l._pNode;}bool operator==(const Self& l){return _pNode == l._pNode;}PNode _pNode;
};

• operator++：这些操作返回的都应该是iterator本身
• operator--(int)：因为tmp是临时对象，所以要返回tmp本身，不能返回引用，不然会悬空引用

a. 链表类

链表链接的是节点，并且链表类的实例化需要和节点模板类的实例化相对应。

a. 构造和析构

CreateHead函数：

void CreateHead()
{_pHead = new Node(); // 哨兵节点，不存数据_pHead->_pNext = _pHead;_pHead->_pPre = _pHead;
}

_pHead = new Node()：这样才能在开空间
错误写法：ListNode _pHead;，这个是栈上函数内创建的临时变量。

构造函数内都需要先CreateHead();，因为操作都是基于有哨兵节点的：

list()
{CreateHead();
}
list(int n, const T& value = T())
{CreateHead();while (n--){push_back(value);}
}
template <class Iterator>
list(Iterator first, Iterator last)
{CreateHead();while (first != last){push_back(*first);first++;}
}list(const list<T>& l)
{CreateHead();PNode cur = l._pHead -> _pNext;while (cur != l._pHead){push_back(cur->_val);cur = cur->_pNext;}
}list<T>& operator=(const list<T> l)
{for (const_iterator it = l.begin(); it != l.end(); it++){push_back(*it);}return *this;
}
~list()
{clear();delete _pHead;_pHead = nullptr;
}

b. 迭代器操作

iterator begin()
{return iterator(_pHead->_pNext);
}
iterator end()
{return iterator(_pHead); // 最后一个节点的next就是head
}
const_iterator begin() const
{return const_iterator(_pHead->_pNext);
}
const_iterator end() const
{return const_iterator(_pHead);
}

c. 容量操作

size_t size()const
{size_t count = 0;for (const_iterator it = begin(); it != end(); it++){count++;}return count;
}
bool empty()const
{return _pHead->_pNext == _pHead;
}

d. 访问操作

T& front()
{return _pHead->_pNext->_val;
}
const T& front()const
{return _pHead->_pNext->_val;
}
T& back()
{return _pHead->_pPre->_val;
}
const T& back()const
{return _pHead->_pPre->_val;
}

e. 修改操作

void push_back(const T& val) { insert(end(), val); }
void pop_back() { erase(--end()); }
void push_front(const T& val) { insert(begin(), val); }
void pop_front() { erase(begin()); }
// 在pos位置前插入值为val的节点
iterator insert(iterator pos, const T& val)
{PNode cur = pos._pNode;PNode pre = cur->_pPre;PNode newnode = new Node(val);newnode->_pPre = pre;newnode->_pNext = cur;pre->_pNext = newnode;cur->_pPre = newnode;return iterator(newnode);
}
// 删除pos位置的节点，返回该节点的下一个位置
iterator erase(iterator pos)
{PNode cur = pos._pNode;PNode pre = cur->_pPre;PNode nxt = cur->_pNext;pre->_pNext = nxt;nxt->_pPre = pre;delete cur;return iterator(nxt);
}
void clear()
{iterator cur(_pHead->_pNext);while (cur != end()){cur = erase(cur);}
}

三，代码汇总

实现文件，my_list.h文件：

// list 的模拟实现
#include<iostream>
using namespace std;namespace tr
{// 节点类template<class T>struct ListNode // struct 默认成员是公共的{ListNode(const T& val = T()):_pPre(nullptr),_pNext(nullptr),_val(val){ }ListNode<T>* _pPre;ListNode<T>* _pNext;T _val;};//List的迭代器类template<class T, class Ref, class Ptr>struct ListIterator // 节点的指针{typedef ListNode<T>* PNode;typedef ListIterator<T, Ref, Ptr> Self; // ListIterator<T, Ref, Ptr>就是这个类本身ListIterator(PNode pNode = nullptr):_pNode(pNode){ }ListIterator(const Self& l){_pNode = l._pNode;}Ref operator*(){return (*_pNode)._val;}Ptr operator->()  // ???{return &((*_pNode)._val);}Self& operator++(){_pNode = _pNode->_pNext;return *this; // 不能返回_PNode，返回的应该是iterator，虽然iterator 的成员变量是PNode，但是有很多封装好的接口和操作}Self operator++(int){Self tmp(_pNode);_pNode = _pNode->_pNext;return tmp;}Self& operator--(){_pNode = _pNode->_pPre;return *this;}Self operator--(int)  // 因为tmp是临时对象，所以要返回tmp本身，不然会悬空引用{Self tmp(_pNode);_pNode = _pNode->_pPre;return tmp;}bool operator!=(const Self& l){return _pNode != l._pNode;}bool operator==(const Self& l){return _pNode == l._pNode;}PNode _pNode;};//list类template<class T>class list{typedef ListNode<T> Node;typedef Node* PNode;public:typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T, const T&, const T*> const_iterator;public:void CreateHead(){_pHead = new Node();_pHead->_pNext = _pHead;_pHead->_pPre = _pHead;}// List的构造list(){CreateHead();}list(int n, const T& value = T()){CreateHead();while (n--){push_back(value);}}template <class Iterator>list(Iterator first, Iterator last){CreateHead();while (first != last){push_back(*first);first++;}}list(const list<T>& l){CreateHead();PNode cur = l._pHead -> _pNext;while (cur != l._pHead){push_back(cur->_val);cur = cur->_pNext;}}list<T>& operator=(const list<T> l){for (const_iterator it = l.begin(); it != l.end(); it++){push_back(*it);}return *this;}~list(){clear();delete _pHead;_pHead = nullptr;}// List Iteratoriterator begin(){return iterator(_pHead->_pNext);}iterator end(){return iterator(_pHead); // 最后一个节点的next就是head}const_iterator begin() const{return const_iterator(_pHead->_pNext);}const_iterator end() const{return const_iterator(_pHead);}// List Capacitysize_t size()const{size_t count = 0;for (const_iterator it = begin(); it != end(); it++){count++;}return count;}bool empty()const{return _pHead->_pNext == _pHead;}// List AccessT& front(){return _pHead->_pNext->_val;}const T& front()const{return _pHead->_pNext->_val;}T& back(){return _pHead->_pPre->_val;}const T& back()const{return _pHead->_pPre->_val;}// List Modifyvoid push_back(const T& val) { insert(end(), val); }void pop_back() { erase(--end()); }void push_front(const T& val) { insert(begin(), val); }void pop_front() { erase(begin()); }// 在pos位置前插入值为val的节点iterator insert(iterator pos, const T& val){PNode cur = pos._pNode;PNode pre = cur->_pPre;PNode newnode = new Node(val);newnode->_pPre = pre;newnode->_pNext = cur;pre->_pNext = newnode;cur->_pPre = newnode;return iterator(newnode);}// 删除pos位置的节点，返回该节点的下一个位置iterator erase(iterator pos){PNode cur = pos._pNode;PNode pre = cur->_pPre;PNode nxt = cur->_pNext;pre->_pNext = nxt;nxt->_pPre = pre;delete cur;return iterator(nxt);}void clear(){iterator cur(_pHead->_pNext);while (cur != end()){cur = erase(cur);}}private:PNode _pHead;};
};

测试文件，test_my_list.cpp文件

#include"my_list.h"
using namespace tr;// 打印列表元素的函数
template<class T>
void printList(const list<T>& ls) {for (auto it = ls.begin(); it != ls.end(); ++it) {std::cout << *it << " ";}std::cout << std::endl;
}void testList() {// 测试默认构造函数list<int> ls1;std::cout << "Testing default constructor: ";printList(ls1);// 测试带参数的构造函数list<int> ls2(5, 10);std::cout << "Testing constructor with n and value: ";printList(ls2);// 测试迭代器构造函数list<int> ls3(ls2.begin(), ls2.end());std::cout << "Testing constructor with iterators: ";printList(ls3);// 测试拷贝构造函数list<int> ls4(ls3);std::cout << "Testing copy constructor: ";printList(ls4);// 测试赋值运算符list<int> ls5;ls5 = ls4;std::cout << "Testing assignment operator: ";printList(ls5);// 测试 push_backls5.push_back(20);std::cout << "Testing push_back: ";printList(ls5);// 测试 push_frontls5.push_front(5);std::cout << "Testing push_front: ";printList(ls5);// 测试 pop_backls5.pop_back();std::cout << "Testing pop_back: ";printList(ls5);// 测试 pop_frontls5.pop_front();std::cout << "Testing pop_front: ";printList(ls5);// 测试 insertauto it = ls5.begin();++it;ls5.insert(it, 15);std::cout << "Testing insert: ";printList(ls5);// 测试 eraseit = ls5.begin();++it;ls5.erase(it);std::cout << "Testing erase: ";printList(ls5);// 测试 clearls5.clear();std::cout << "Testing clear: ";printList(ls5);// 测试 size 和 emptystd::cout << "Size after clear: " << ls5.size() << std::endl;std::cout << "Is empty after clear: " << (ls5.empty() ? "Yes" : "No") << std::endl;
}int main() {testList();return 0;
}

---

🌈我的分享也就到此结束啦🌈
要是我的分享也能对你的学习起到帮助，那简直是太酷啦！
若有不足，还请大家多多指正，我们一起学习交流！
📢公主，王子：点赞👍→收藏⭐→关注🔍
感谢大家的观看和支持！祝大家都能得偿所愿，天天开心！！！