std::list的模拟实现

* * * 在C++中list实际上是一个双向带头循环链表，所以list是不支持随机访问的。list的迭代器类型是双向迭代器，与string和vector不同的是，list不是简单的指针，list的迭代器是类。此处本文将会详细讲解。 * * *

list的成员变量

list的成员变量是指向哨兵位节点的指针，通过定义ListNode类来实现节点的定义及使用。注意：此处使用struct来声明ListNode而不用class的原因是：struct默认权限是public而private的默认权限是private，直接用struct可以让类外直接访问。 template struct ListNode { //初始化节点 ListNode(const T& val=T()) :_val(val) ,_next(this) ,_prev(this) {} T _val; ListNode* _next; ListNode* _prev; }; template class list { public: typedef ListNode ListNode; private: ListNode* _phead; }; * * *

list的迭代器

list底层是节点所以list是不支持随机访问的，因此不能简单的对指针++或– 来实现对迭代器的左移和右移。list迭代器底层也是一个类，这个类用来存放当前节点。重载++，–等等迭代器的基本功能。

迭代器的定义

此处的模板并不完善，后面还要添加其他模板。 //创建list迭代器 template struct list_iterator { typedef ListNode ListNode; typedef list_iterator list_iterator; //构造函数 list_iterator(ListNode* node = nullptr) :_node(node) {} ListNode* _node; };

迭代器*和->

//重载解引用* T& operator*() { return _node->_val; } //重载-> T* operator->() { return &(operator*); //此处直接调用*运算符重载来实现取地址 } 注意：此处需要考虑只有读取权限的const_iterator不能对解引用的数据进行修改，所以再使用T&和T*是明显不够的。 因此需要添加模板参数来实现const_iterator。 template //用ref来代替T&和const T&，同理用Ptr来代替T*和const T* typedef list_iterator Self; //重载解引用* Ref operator*() { return _node->_val; } //重载-> Ptr operator->() { return &(operator*); //此处直接调用*运算符重载来实现取地址 } 在list的类中iterator和const_iterator的声明如下； typedef list_iterator iterator; typedef list_iterator const_iterator;

迭代器的++和–

typedef list_iterator Self; //重载++,非const类型 Self operator++() { _node = _node->_next; return *this; } //重载–，非const类型 Self operator–() { _node = _node->_prev; return *this; } //重载++,const类型 Self operator++()const { _node = _node->_next; return *this; } //重载–，const类型 Self operator–()const { _node = _node->_prev; return *this; } 此处前置++和–就不展示了。

迭代器的==和!=

//重载== bool operator==(const Self& it) { return _node == it._node; } //重载!= bool operator!=(const Self& it) { return !(*this==it); //此处直接调用== } * * *

迭代器代码汇总

//创建list迭代器 template //用ref来代替T&和const T&，同理用Ptr来代替T*和const T* struct list_iterator { typedef ListNode ListNode; typedef list_iterator Self; //构造函数 list_iterator(ListNode* node = nullptr) :_node(node) {} //重载++,非const类型 Self operator++() { _node = _node->_next; return *this; } //重载–，非const类型 Self operator–() { _node = _node->_prev; return *this; } //重载++,const类型 Self operator++()const { _node = _node->_next; return *this; } //重载–，const类型 Self operator–()const { _node = _node->_prev; return *this; } //重载解引用* Ref operator*() { return _node->_val; } //重载-> Ptr operator->() { return &(operator*); //此处直接调用*运算符重载来实现取地址 } //重载== bool operator==(const Self& it) { return _node == it._node; } //重载!= bool operator!=(const Self& it) { return !(*this==it); //此处直接调用== } ListNode* _node; }; * * *

list的成员函数

template class list { public: typedef ListNode ListNode; typedef list_iterator iterator; typedef list_iterator const_iterator; private: ListNode* _phead; }; * * *

迭代器的begin和end

//begin函数，非const类型 iterator begin() { return _phead->_next; //此处使用了隐式类型转化，将ListNode*转化为了iterator } //end函数，非const类型 iterator end() { return _phead; } //begin函数，const类型 const_iterator begin()const { return _phead->_next; } //end函数，const类型 const_iterator end()const { return _phead; } * * *

构造函数

无参构造

//构造函数，无参初始化 list() :_phead(new ListNode) //此处需要创建哨兵位，交给ListNode的构造函数 {}

迭代器构造

此处偷懒直接调用了push_back尾插函数。

//迭代器构造函数

template

list(const T* first, const T* last)

_phead(new ListNode) //还是创建哨兵位 { while (first != last) { push_back(*first); ++first; } }

n的val构造

//用n个val构造 list(size_t n, const T& val) :_phead(new ListNode) { while (n–) { push_back(val); } }

拷贝构造

//拷贝构造

list(const list& l)

_phead(new ListNode) { for (auto& e : l) //范围for遍历原链表 { push_back(e); } } * * *

尾插和头插

尾插即创建新节点，对原有节点的指针进行修改。 //尾插 void push_back(const T& val) { ListNode* newnode = new ListNode(val); newnode->_next = _phead; newnode->_prev = _phead->_prev; _phead->_prev->_next = newnode; _phead->_prev = newnode; } //头插 void push_front(const T& val) { ListNode* newnode = new ListNode(val); newnode->_next = _phead->_next; newnode->_prev = _phead; _phead->_next->_prev = newnode; _phead->_next = newnode; } * * *

尾删和头删

删除就是记录需要删除的节点位置将其前后节点指向改变即可。 //尾删 void pop_back() { ListNode* del = _phead->_prev; del->_prev->_next = _phead; _phead->_prev = del->_prev; delete[] del; } //头删 void pop_front() { ListNode* del = _phead->_next; del->_next->_prev = _phead; _phead->_next = del->_next; delete[] del; } * * *

指定位置插入，删除

通过迭代器实现指定位置的插入和删除。指定位置插入会返回插入节点的迭代器；指定位置删除会返回删除位置的下一个迭代器。 //指定位置之前插入 iterator insert(iterator it, const T& val) { ListNode* newnode = new ListNode(val); ListNode* cur = it._node; newnode->_next = cur; newnode->_prev = cur->_prev; cur->_prev->_next = newnode; cur->_prev = newnode; return newnode; } //指定位置删除 iterator erase(iterator it) { ListNode* del = it._node; ListNode* cur = del->_next; del->_prev->_next = cur; cur->_prev = del->_prev; return cur; } * * *

swap交换

此处为了实现swap(l1,l2)，而不是l1.swap(l2)，需要使用友元函数而不是成员函数。 注意：编译器在解析友元函数的时候无法正确的匹配外部声明的模板函数，此时就需要在声明的时候也加上模板参数。 template friend void swap(list& l1, list& l2); template void swap(list& l1, list& l2) { std::swap(l1._phead, l2._phead); } * * *

clear

list::clear函数的作用是清空有效节点，只保留哨兵位。注意：清空节点之后还要将哨兵位指向本身。 void clear() { ListNode* cur = _phead->_next; while (cur != _phead) { ListNode* del = cur; cur = cur->_next; delete[] del; } //清空数据之后，将哨兵位指向哨兵位 _phead->_next = _phead; _phead->_prev = _phead; } * * *

返回首节点和尾节点

返回首尾节点的值。 //非const类型 T& front() { return _phead->_next->_val; } T& back() { return _phead->_prev->_val; } //const类型 const T& front()const { return _phead->_next->_val; } const T& back()const { return _phead->_prev->_val; } * * *

返回链表长度

//返回链表长度 size_t size() { ListNode* cur = _phead->_next; size_t sz = 0; while (cur != _phead) { cur = cur->_next; ++sz; } return sz; }

判空

//链表是否为空 bool empty() { return _phead == _phead->_next; } * * *

赋值运算符重载

进行赋值的是否需要先将原链表的所有数据清空。 //赋值运算符重载 list& operator=(const list& l) { clear(); ListNode* cur = l._phead->_next; while (cur != l._phead) { push_back(cur->_val); cur = cur->_next; } return *this; }