目录:
list的深度剖析及模拟实现
list底层是双向循环链表 ------而实现list最重要的就是迭代器类的实现 下面我们会重点学习迭代器
list整体接口函数罗列
//模拟实现list底层---全部功能
namespace std
{//结点类模拟实现template<class T>struct list_node{//构造函数list_node(cosnt T& value = T()):_val(value), _prev(nullptr), _next(nullptr){}//成员变量list_node<T>* _prev;//前驱指针list_node<T>* _next;//后继指针T _val;};//模拟实现list迭代器template<class T,class Ref,class Ptr>class _list_iterator{typedef list_node<T> Node;typedef _list_iterator<T, Ref, Ptr> self;_list_iterator(Node* pnode);//构造函数//各种运算符重载self operator++();//前++self operator--();self operator++(int);//后置++self operator--(int);bool operator==(const self& s)const;bool operator!=(const self& s)const;Ref operator*();//返回的是引用Ptr operator->();//返回的是指针//成员变量Node* _pnode;};//模拟实现listtemplate<class T>class list{public:typedef list_node<T> Node;typedef _list_iterator<T, T&, T*> iterator;typedef _list_iterator<T, const T&, const T*> const_iterator;//默认成员函数list();list(const list<T>& lt);//拷贝构造函数list<T>& operator=(const list<T>& lt);~list();//有关迭代器相关函数iterator begin();iterator end();const_iterator begin()const;const_iterator end()const;//访问相关容器T& front();T& back();const T& front()const;const T& back()const;//对容器操作函数void insert(iterator pos, const T& x);void push_back(const T& x);void pop_back();void push_front(const T& x);void pop_front();iterator erase(iterator pos);//删除pos位置的迭代器,返回pos->next迭代器//其他操作void clear();bool empty()const ;size_t size()const;void resize(size_t n, const T& value = T());void swap(list<T>& lt);private:Node* _head;};
}
其他操作与vector和string的实现基本相似,我们重点学习iterator迭代器类
迭代器类的模拟实现
迭代器类存在的意义
之前模拟实现string和vector的时候为什么就没有实现迭代器类呢,为什么要在list中实现迭代器类呢?
1.因为在string和vector对象都是将数据存储在了一块连续的内存空间中,我们通过指针进行自增,自减以及解引用等操作,就可以对相应位置的数据进行一系列的操作,string和vector中的迭代器都是原生指针。
1.但是对于list来说,list的底层实现是链表,**我们都知道链表中各个节点在内存中的位置都是随机的,不是连续的,**所以我们不能仅仅通过节点指针的自增、自减以及解引用等等操作来对相应的节点进行操作。
2.所以迭代器的意义是,让使用者可以不必关心容器的底层实现,可以用简单统一的方式对容器内的数据进行访问。
3.C++中最厉害的是什么,就是封装和对各种操作符进行重载。重载之后呢,使得结点指针的各种操作就和普通指针一样了。
1、为什么模板参数那里是三个参数呢?为什么不是一个呢
然后在list的模拟实现中,我们typedef了两个迭代器类型,分别是普通迭代器和const迭代器
这里我们就可以看出Ref是T&类型,Ptr是T*类型
当我们使用迭代器的时候,编译器就会实例化出一个迭代器对象,根据需要分为普通迭代器对象和const迭代器对象。
如果该迭代器类不设计三个模板参数的话,就不能很好的区分普通迭代器和const迭代器了。
构造函数
迭代器就是对结点指针进行封装,所以成员变量只有一个,那就是结点指针,构造函数就是根据结点指针来构造出一个迭代器对象的。
++运算符的重载
++运算符分为前置++和后置++
1.前置++ 就是 将内部指针往后面移动一位,再返回
2.后置++ 就是 将内部指针先拷贝一份–tmp,然后
内部指针再往后移动一位,返回的是tmp指针
– --运算符重载
实现跟++相同
==运算符重载
==运算符比较两个迭代器时候,我们实际上是想知道的是这两个迭代器是否是同一个位置的迭代器,所以呢,我们直接比较两个迭代器的指针指向即可。
!=运算符重载
!=运算符比较两个结点指针的指向即可.
*运算符重载
*运算符 实际上是解引用结点指针的数据
->运算符重载
->运算符,我们要返回的是结点所储存数据的地址
list与vector的对比
list模拟实现代码:
//模拟实现list底层---全部功能
namespace std
{//结点类模拟实现template<class T>struct list_node{//构造函数list_node(cosnt T& value = T()):_val(value), _prev(nullptr), _next(nullptr){}//成员变量list_node<T>* _prev;//前驱指针list_node<T>* _next;//后继指针T _val;};//模拟实现list迭代器template<class T,class Ref,class Ptr>class _list_iterator{typedef list_node<T> Node;typedef _list_iterator<T, Ref, Ptr> self;_list_iterator(Node* pnode)//构造函数:_pnode(node){}//各种运算符重载self operator++()//前++{_pnode = _pnode->next;return *this;}self operator++(int)//后置++{self tmp(*this);_pnode = _pnode->next;return tmp;}self operator--()//前置{_pnode = _pnode->prev;return *this;}self operator--(int)//后置{self tmp(*this);_pnode = _pnode->prev;return tmp;}bool operator==(const self& s)const{return _pnode == s._pnode;}bool operator!=(const self& s)const{return _pnode != s._pnode;}Ref operator*()//返回的是引用{return _pnode->_val;}Ptr operator->()//返回的是指针{return &_pnode->_val;}//成员变量Node* _pnode;};//模拟实现listtemplate<class T>class list{public:typedef list_node<T> Node;typedef _list_iterator<T, T&, T*> iterator;typedef _list_iterator<T, const T&, const T*> const_iterator;//默认成员函数list(){_head = new Node;_head->prev = _head;_head->next = _head;}list(const list<T>& lt)//拷贝构造函数{_head = new Node;_head->prev = _head;_head->next = _head;for (const auto& e : lt){push_back(e);}}//=运算符重载list<T>& operator=(const list<T>& lt){if (this != <)//避免给自己自赋值{clear();for (auto& e : lt){push_back(e);//将lt中的每个数据放push}}return *this;}~list(){clear();//全部清空delete _head;//删掉头结点_head = nullptr;}//有关迭代器相关函数iterator begin(){return iterator(_head->next);}iterator end(){return iterator(_head);}const_iterator begin()const{return const_iterator(_head->next);}const_iterator end()const{return const_iterator(_head);}//访问相关容器T& front(){return *begin();}T& back(){return *(--end());}const T& front()const{return *begin();}const T& back()const{return *(--end());}//对容器操作函数void insert(iterator pos, const T& x){assert(pos);//先检查pos迭代器是否合理//插入 只要知道前一个指针就行prevNode* cur = pos._pnode;//迭代器pos处的结点指针Node* prev = cur->prev;//相当于pos前一个结点指针Node* newNode = new Node(x);//创建结点//插入结点操作newNode->next = cur;cur->prev = newNode;newNode->prev = prev;prev->next = newNode;}iterator erase(iterator pos)//删除pos位置的迭代器,返回pos->next迭代器{assert(pos);//检测pos迭代器的合理性//删除一个结点,必须知道该节点的前后两个结点Node* move = pos._pnode;Node* prev = move->prev;Node* next = move->next;delete move;//删除move结点//建立prev与next之间的双向关系prev->next = next;next->prev = prev;return iterator(next);//返回pos的下一个迭代器}void push_back(const T& x){insert(end(), x);}void pop_back(){erase(--end());//删除头结点的前一个结点}void push_front(const T& x){insert(begin(), x);}void pop_front(){erase(begin());}//其他操作void clear(){//遍历每一个结点然后删除iterator ir = begin();while (ir != end())//逐个删除结点 只保留头结点{ir = erase(ir);}}bool empty()const{return begin() == end();//判断是否只有头结点}size_t size()const{size_t sz = 0;iterator it = begin();while (it != end()){sz++;it++;}return sz;}void resize(size_t n, const T& value = T()){size_t len = size();//比较n和len的值if (len <= n){while (n - len){push_back(value);len++;}}else //(len>n){while (len-n){pop_back();len--;}}}void swap(list<T>& lt){::swap(_head,lt._head);//交换两个容器当中的头指针即可}private:Node* _head;};
}
如果错误,多多指教!