list模拟实现

目录

节点结构

构造函数

insert

erase

push_back

push_front

pop_front

pop_back

拷贝构造

析构函数

赋值重载

正向迭代器实现

clear

反向迭代器实现

测试list

附完整代码

---

参照数据结构篇: 带头双向循环链表

节点结构

namespace dck
{template <class T>struct list_node{T _data;list_node<T> *_next;list_nodce<T> *_prev;list_node(const T &x = T()): _data(x), _next(nullptr), _prev(nullptr){}};template <class T>class list{typedef list_node<T> Node;private:Node *_head;  // 带哨兵位的头节点指针size_t _size; // 链表的节点个数};
}

构造函数

void empty_init()
{_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;
}// 构造函数
list()
{empty_init();
}

insert

iterator insert(iterator pos, const T &val)
{Node *cur = pos._node; // 获取原生指针Node *newnode = new Node(val);Node *prev = cur->_prev;prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;++_size;return iterator(newnode);
}

erase

iterator erase(iterator pos)
{Node *cur = pos._node;Node *prev = cur->_prev;Node *next = cur->_next;delete cur;prev->_next = next;next->_prev = prev;_size--;return iterator(next);
}

push_back

void push_back(const T &x)
{insert(end(), x);
}

push_front

void push_front(const T &x)
{insert(begin(), x);
}

pop_front

void pop_front()
{erase(begin());
}

pop_back

void pop_back()
{erase(--end());
}

拷贝构造

list(const list<T> &lt)
{empty_init();for (auto e : lt){push_back(e);}
}

析构函数

~list()
{clear();delete _head;_head = nullptr;
}​

赋值重载

void swap(list<T> &lt)
{std::swap(_head, lt._head);std::swap(_size, lt._size);
}
list<T> &operator=(list<T> lt)
{swap(lt);return *this;
}

正向迭代器实现

● 之前学习的迭代器本质是原生指针，但list的迭代器是对节点指针封装的类，因为迭代器提供的统一操作是++/--来访问前一个或者后一个节点，但是list是链表，因此我们要将++/--实现成类的运算符重载函数，就可以让++/--实现访问前一个/后一个节点的效果

● 由于正向普通迭代器和正向const迭代器的类型不同，是需要实现两个类的，但我们可以给类添加额外两个模版参数，就可以控制是普通迭代器还是const迭代器

template <class T, class Ref, class Ptr> // 第二个参数是引用，第三个参数是指针
struct __list_iterator                   // 前加_一般表示内部的实现
{typedef list_node<T> Node;typedef __list_iterator<T, Ref, Ptr> self;Node *_node;__list_iterator(Node *node): _node(node){}self &operator++(){_node = _node->_next;return *this;}self operator++(int){self tmp(*this);_node = _node->_next;return tmp;}self &operator--(){_node = _node->_prev;return *this;}self operator--(int){self tmp(*this);_node = _node->_prev;return tmp;}Ref operator*(){return _node->_data;}bool operator!=(const self &s){return _node != s._node;}bool operator==(const self &s){return _node == s._node;}Ptr operator->(){return &_node->_data;}
};

iterator begin()
{return _head->_next;
}const_iterator begin() const
{return _head->_next;
}iterator end()
{return _head;
}const_iterator end() const
{return _head;
}

clear

void clear()
{iterator it = begin();while (it != end()){it = erase(it);}
}

反向迭代器实现

● 反向迭代器可以用正向迭代器去适配，反向迭代器的++/--本质就是正向迭代器的--/++

● 迭代器判断相等和不相等本质是在比较底层的节点指针是否相等

reverse_iterator.h 文件

template<class Iterator, class Ref, class Ptr>
class ReverseIterator
{
public:typedef ReverseIterator<Iterator, Ref, Ptr> Self;ReverseIterator(Iterator it):_it(it){}//前置++Self& operator++(){--_it;return *this;}//后置++Self operator++(int){Self tmp(*this);--_it;return tmp;}Ref operator*(){//自己实现//return *_it;}Ptr operator->(){//自己实现return _it.operator->();}bool operator!=(const Self& s){return _it != s._it;}private:Iterator _it;
};

list.h 文件

template <class T>
class list
{typedef list_node<T> Node;public:typedef __list_iterator<T, T &, T *> iterator;                                        // 非const迭代器typedef __list_iterator<T, const T &, const T *> const_iterator;                      // const迭代器typedef ReverseIterator<iterator, T &, T *> reverse_iterator;                         // 非const反向迭代器typedef ReverseIterator<const_iterator, const T &, const T *> const_reverse_iterator; // const反向迭代器reverse_iterator rbegin(){return iterator(--end()); // 自己实现的}reverse_iterator rend(){return iterator(end()); // 自己实现的}const_reverse_iterator rbegin() const{return const_iterator(--end()); // 自己实现的}const_reverse_iterator rend() const{return const_iterator(end()); // 自己实现的}
}

而库中的实现和我们不太一样，不一样的地方在于库中反向迭代器的rbegin与rend位置和我们自己写的不一样，下图rbegin和rend的位置是库中的实现，是呈现对称结构的，而库中迭代器解引用访问的是前一个数据，也就是先让原生指针--, 然后解引用访问数据! 

reverse_iterator.h 文件

template<class Iterator, class Ref, class Ptr>
class ReverseIterator
{
public:typedef ReverseIterator<Iterator, Ref, Ptr> Self;ReverseIterator(Iterator it):_it(it){}//前置++Self& operator++(){--_it;return *this;}//后置++Self operator++(int){Self tmp(*this);--_it;return tmp;}Ref operator*(){//库中的Iterator cur = _it;return *(--cur);}Ptr operator->(){//库中的return &(operator*());}bool operator!=(const Self& s){return _it != s._it;}private:Iterator _it;
};

list.h 文件

template <class T>
class list
{
public:typedef __list_iterator<T, T &, T *> iterator;                                        // 非const迭代器typedef __list_iterator<T, const T &, const T *> const_iterator;                      // const迭代器typedef ReverseIterator<iterator, T &, T *> reverse_iterator;                         // 非const反向迭代器typedef ReverseIterator<const_iterator, const T &, const T *> const_reverse_iterator; // const反向迭代器reverse_iterator rbegin(){return iterator(end()); // 库中的}reverse_iterator rend(){return iterator(begin()); // 库中的}const_reverse_iterator rbegin() const{return const_iterator(end()); // 库中的}const_reverse_iterator rend() const{return const_iterator(begin()); // 库中的}
};

测试list

#include <iostream>
#include "list.h"
using namespace std;void print(const dck::list<int> &lt)
{dck::list<int>::const_iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";it++;}cout << endl;
}void printReverse(const dck::list<int> &lt)
{dck::list<int>::const_reverse_iterator it = lt.rbegin();while (it != lt.rend()){cout << *it << " ";it++;}cout << endl;
}void test1()
{dck::list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_front(3);lt.push_front(4);print(lt);lt.pop_back();lt.pop_front();print(lt);
}void test2()
{dck::list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.insert(++lt.begin(), 10);print(lt);lt.erase(++lt.begin());print(lt);
}void test3()
{dck::list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);printReverse(lt);
}void test4()
{dck::list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);dck::list<int> lt1(lt); print(lt);dck::list<int> lt2;lt2.push_back(10);lt2.push_back(20);lt2.push_back(30);lt2.push_back(40);lt2 = lt; print(lt2);
}int main()
{test1();test2();test3();test4();return 0;
}

附完整代码

reverse_iterator.h

//用正向迭代器适配方向迭代器
template<class Iterator, class Ref, class Ptr>
class ReverseIterator
{
public:typedef ReverseIterator<Iterator, Ref, Ptr> Self;ReverseIterator(Iterator it):_it(it){}//前置++Self& operator++(){--_it;return *this;}//后置++Self operator++(int){Self tmp(*this);--_it;return tmp;}Ref operator*(){//库中的Iterator cur = _it;return *(--cur);}Ptr operator->(){//库中的return &(operator*());}bool operator!=(const Self& s){return _it != s._it;}private:Iterator _it;
};

list.h

#include <iostream>
using namespace std;
#include "reverse_iterator.h"namespace dck
{template <class T>struct list_node{T _data;list_node<T> *_next;list_node<T> *_prev;list_node(const T &x = T()): _data(x), _next(nullptr), _prev(nullptr){}};template <class T, class Ref, class Ptr> // 第二个参数是引用，第三个参数是指针struct __list_iterator                   // 前加_一般表示内部的实现{typedef list_node<T> Node;typedef __list_iterator<T, Ref, Ptr> self;Node *_node;__list_iterator(Node *node): _node(node){}self &operator++(){_node = _node->_next;return *this;}self operator++(int){self tmp(*this);_node = _node->_next;return tmp;}self &operator--(){_node = _node->_prev;return *this;}self operator--(int){self tmp(*this);_node = _node->_prev;return tmp;}Ref operator*(){return _node->_data;}bool operator!=(const self &s){return _node != s._node;}bool operator==(const self &s){return _node == s._node;}Ptr operator->(){return &_node->_data;}};// list的实现template <class T>class list{typedef list_node<T> Node;public:typedef __list_iterator<T, T &, T *> iterator;                   // 非const迭代器typedef __list_iterator<T, const T &, const T *> const_iterator; // const迭代器typedef ReverseIterator<iterator, T &, T *> reverse_iterator;                         // 非const反向迭代器typedef ReverseIterator<const_iterator, const T &, const T *> const_reverse_iterator; // const反向迭代器reverse_iterator rbegin(){return iterator(end()); // 库中的}reverse_iterator rend(){return iterator(begin()); // 库中的}const_reverse_iterator rbegin() const{return const_iterator(end()); // 库中的}const_reverse_iterator rend() const{return const_iterator(begin()); // 库中的}iterator begin(){return _head->_next;}const_iterator begin() const{return _head->_next;}iterator end(){return _head;}const_iterator end() const{return _head;}void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}// 构造函数list(){empty_init();}// 清空数据void clear(){iterator it = begin();while (it != end()){it = erase(it);}}// 拷贝构造 --- 一个节点一个节点尾插即可list(const list<T> &lt){empty_init();for (auto e : lt){push_back(e);}}void swap(list<T> &lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}//赋值重载list<T> &operator=(list<T> lt){swap(lt);return *this;}// 析构函数~list(){clear();delete _head;_head = nullptr;}void push_back(const T &x){insert(end(), x);}void push_front(const T &x){insert(begin(), x);}void pop_front(){erase(begin());}void pop_back(){erase(--end());}// 在pos之前插入节点iterator insert(iterator pos, const T &val){Node *cur = pos._node; // 获取原生指针Node *newnode = new Node(val);Node *prev = cur->_prev;prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;++_size;return iterator(newnode);}// 删除pos位置的节点, 返回下一个位置的迭代器iterator erase(iterator pos){Node *cur = pos._node;Node *prev = cur->_prev;Node *next = cur->_next;delete cur;prev->_next = next;next->_prev = prev;_size--;return iterator(next);}size_t size(){return _size;}private:Node *_head;  // 带哨兵位的头节点指针size_t _size; // 链表的节点个数};
}