list的模拟实现

目录

一、构造和扩容机制

二、普通迭代器

三、const迭代器

四、tip

---

有了前面vetcor的基础呢，我们在学习和使用list上就更加的方便快捷，浅显易懂了，所以相似的部分我就不做过多的言语阐述了，在使用方面呢，大家可以学习我之前看的c++网站，和vector和string的使用都是差不多的，重点要放在list的迭代器部分

一、构造和扩容机制 template <class T> class list { typedef list_node<T> Node; public: void empty_init() { _head = new Node; _head->_next = _head; _head->_prev = _head; } list() { empty_init(); } void push_back(const T&val) { Node* tail = _head->_prev; Node* newnode = new Node(val); tail->_next = newnode; newnode->_prev = tail; newnode->_next = _head; _head->_prev = newnode; } private: Node* _head;

空初始化的时候我们也需要构造，所以缺省值我们给一个匿名对象进行初始化，这个我们在vector的模拟实现里面有重点说到

template <class T> struct list_node { T _data; list_node<T>* _next; list_node<T>* _prev; list_node(const T& data=T()) :_data(data) ,_next(nullptr) ,_prev(nullptr) { } }; 二、普通迭代器 void listtest1() { list<int> l; l.push_back(1); l.push_back(2); l.push_back(3); l.push_back(4); list<int>::iterator it = l.begin(); while (it != l.end()) { cout << *it << " "; ++it; } }

这里我们还没有实现迭代器

这是一个带头双向循环链表，我们结合迭代器来看，由于它是一个结构体，我们解引用并不能得到它的数据，++it也不能得到向后走，！=也判断不了end（），因为里面存在着数据和前后指针，这时候我们就要运算符重载和封装这里

这里我们为什么不用class来写那个list_node 呢因为你写class就要把它定义成友元，而这里我们是要把这个类的权限全部开放所以我们定义成struct

template <class T> struct list_iterator { typedef list_node<T> Node; typedef list_iterator<T> self; Node* _node; list_iterator(Node* node) :_node(node) { } self& operator++() { _node = _node->_next; return *this; } T& operator*() { return _node->_data; } bool operator!=(const self&s) { return _node != s._node; } };

 我们来阐述一下这里的行为，我们封装了一个Node，实例化了一个对象，写出构造函数，++让里面的指针++返回这个Node的下一个位置的引用，下面也是类似，就是指针完成不了的事情我们通过间接的方式来让类完成

typedef list_iterator<T> iterator; iterator begin() { return _head->_next; } iterator end() { return _head; }

这里begin和end返回指着可以的原因是单参数的构造支持隐式类型的转换

这里重要的就是封装，封装屏蔽了底层差异和实现细节，提供统一访问修改遍历方式

这算是一种模拟指针的行为

我们简化了这里的接口，list_iterator封装了链表节点的指针，通过重载一系列运算符，用户可以像指针一样遍历链表，而不必关心节点如何连接

这里我们先封装一个简单的 

先把其他的架子实现出来

首先是删除

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

删除这里会涉及迭代器失效的问题，有关于迭代器失效可以看一下我vector里面有详细的写，总而言之就是这里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; return iterator(newnode); }

一般来说这里的insert不会发生迭代器失效，但是库里面有写，而且可以和上面统一一下

这样子我们的头插头删尾插尾删就可以复用这里的

void push_back(const T&val) { insert(end(), val); } void push_front(const T& val) { insert(begin(), val); } void pop_back(const T& val) { erase(end(), val); } void pop_front(const T& val) { erase(begin(), val); } void clear() { iterator it = begin(); while (it != end()) { it = erase(it); } }

这个时候我们上面的删除迭代器就派上用场了，删除完我们返回下一个迭代器位置就行了

我们的析构就可以套用这个clear了

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

接下来我们来实现一下拷贝构造

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

这里不用const原因是因为e不是const对象，等下我们实现了const迭代器就可以实现了

再让我们实现一下赋值

首先是传统写法

//lt3=lt1 //list<T>& operator=(list<T>& l) //{ // if (this != &l) // { // clear(); // for (auto e : lt) // { // push_back(e); // } // } //}

现代写法

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

交换头节点的指针就可以了

为了不让有的人去获取这个链表的size时时间复杂度是o(n)，我们添加一个szie在private那里，在初始化那里给上0，insert那里++，erase那里--就好了

void swap(list<T>& l) { std::swap(_head, l._head); std::swap(_size, l._size); }

我们再来看一下后置++

self operator++(int) { self tmp(*this); _node = _node->_next; return tmp; } self operator--(int) { self tmp(*this); _node = _node->_prev; return tmp; } bool operator==(const self& s) { return _node == s._node; }

迭代器是不需要实现析构函数的，因为它不需要把那个节点给带走，你可以访问节点，但是不能带走不属于它的节点

为了支持自定义类型的实例化访问我们还需要实现->

T* operator->() { return &_node->_data; }

三、const迭代器 template <class T> struct list_const_iterator { typedef list_node<T> Node; typedef list_const_iterator<T> self; Node* _node; list_const_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; } const T& operator*() { return _node->_data; } const T* operator->() { return &_node->_data; } bool operator!=(const self& s) { return _node != s._node; } bool operator==(const self& s) { return _node == s._node; } }; typedef list_const_iterator<T> const_iterator; const_iterator begin() const { return _head->_next; } const_iterator end() const { return _head; } void print_list(const list<int>& l) { list<int>::const_iterator it = l.begin(); while (it != l.end()) { cout << *it << " "; ++it; } }

这个const_iterator不是const iterator的类型，指针本身可以被修改，但是指针指向的内容不能被修改

那我们这里写成两个能不能复用一下搞成一个呢，我们看一下库里面的

同一个类模板，实例化参数不同，就是完全不同的类型

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; } Ptr* operator->() { return &_node->_data; } bool operator!=(const self& s) { return _node != s._node; } bool operator==(const self& s) { return _node == s._node; } }; typedef list_iterator<T,T&,T*> iterator; typedef list_iterator<T,const T&,const T*> const_iterator;

 我们定义了两个类，我们也不知道这是什么类，留给后面来定义，只知道Ref相当于&类型的，Ptr代表*类型的，

Ref & operator*() { return _node->_data; } Ptr* operator->() { return &_node->_data; }

比如说当我们实例化int的时候，普通对象先传给T&，再把T&传给Ref，Ref就可以实例化出来这个类进行使用，定义了一个const对象就实例化出来一个const的类出来，看似是一个类，在当你实例化普通和const对象的时候其实是两个类

四、tip template<class T> void print_list(const list<T>& l) { list<T>::const_iterator it = l.begin(); while (it != l.end()) { cout << *it << " "; ++it; } for (auto e : l) { cout << e << " "; }cout << endl; } void listtest3() { list<int> l; l.push_back(1); l.push_back(2); l.push_back(3); l.push_back(4); print_list(l); }

 这段代码我们会发现编译不通过

template<typename T> void print_list(const list<T>& l) { typename list<T>::const_iterator it = l.begin(); while (it != l.end()) { cout << *it << " "; ++it; } for (auto e : l) { cout << e << " "; }cout << endl; }

改成这样就可以了，因为你list里面是模板，模板又没有实例化，编译器不敢去类里面找，去里面找也没有实例化，其次是你const_iterator是静态成员变量还是内嵌类型不知道，编译器分不清，前面加一个typename就是告诉编译器这里是一个类型，等list<t>实例化，再去实例化类型里面去找

那我们这个print如果想针对所有容器怎么办

template<typename Container> void print_container(const Container& l) { typename Container::const_iterator it = l.begin(); while (it != l.end()) { cout << *it << " "; ++it; } for (auto e : l) { cout << e << " "; }cout << endl; } void listtest3() { vector<string> v; v.push_back("11111111111"); v.push_back("11111111111"); v.push_back("11111111111"); v.push_back("11111111111"); print_container(v); } }

和上面是一样的玩法，把实例化这个类型传给了container

模板实现了泛型编程，把我们本来干的活交给了编译器

好了list就到这里结束了，接下来是栈和队列，写的不好的地方欢迎大家指出