本文是对之前list类的模拟实现的重制。

整体框架

namespace YCB
{//模拟实现list当中的结点类template<class T>struct _list_node{_list_node(const T& val = T()); T _val;                _list_node<T>* _next;   _list_node<T>* _prev;  };//list迭代器template<class T, class Ref, class Ptr>struct _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);iterator erase(iterator pos);void push_back(const T& x);void pop_back();void push_front(const T& x);void pop_front();//其他函数size_t size() const;void resize(size_t n, const T& val = T());void clear();bool empty() const;void swap(list<T>& lt);private:node* _head; //指向链表头结点的指针};
}

Alloc内存池

以后详细谈

template <class T, class Alloc = alloc>class list {typedef __list_node<T> list_node;typedef list_node* link_type;}
void empty_initialize() { node = get_node();node->next = node;node->prev = node;
}link_type get_node() { return list_node_allocator::allocate(); }
//内存池来的，用定位new显式调用构造函数和析构函数
link_type create_node(const T& x) {link_type p = get_node();__STL_TRY {construct(&p->data, x);}__STL_UNWIND(put_node(p));return p;
}

iterator类

iterator的意义

为什么需要iterator？

前面在模拟string和vector并没有一定要求一个迭代器。

string和vector对象都将其数据存储在了一块连续的内存空间，我们通过指针进行自增、自减以及解引用等操作，就可以对相应位置的数据进行一系列操作，因此string和vector当中的迭代器就是原生指针。

但是list不行。

因此链表不连续，下一个位置不是要的数据位置，所以不能直接++，而像原生指针一样只有直接++就不行。

即结点的指针原生行为不满足迭代器定义，那么使用迭代器通过类去封装结点的指针重载运算符来控制，使得可以像使用string和vector当中的迭代器一样的方式使用list当中的迭代器。

比如我们进行想++实际背后进行的是next操作。

比如遍历链表头到尾，iterator的begin()和end()实际封装的是下图中的样子。

void test_list1()
{list<int>lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);list<int>::iterator it=lt.begin();//调用默认的浅拷贝while(it!=lt.end()){cout<<*it<<" ";it++;}cout<<endl;for(auto e:lt){//按照stl的标准把begin()和end()替换了cout<<e<<" ";}cout<<endl;
}  

• [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-tvpuF2ix-1643207276408)(list类的模拟实现.assets/image-20211001153207318.png)]

iterator的实现

operator=&&拷贝析构

iterator拷贝和析构以及operator=怎么处理？

• 采用浅拷贝
  • 只要让迭代器能访问实际的空间即可。
• 析构不写
  • 链表的结点归链表管，不然迭代器每次出来结束就给删除了

void test_list1()
{list<int>lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);list<int>::iterator it=lt.begin();//调用默认的浅拷贝
}

iterator的三个模板参数

既然如此可以按照定义自己实现迭代器。

但是对于如下一个场景:

void PrintList(const List<int>& lt){list<int>::iterator it =lt.begin();//没有const begin()//能提供iterator begin() const 来处理吗？while(it!=lt.end()){*it+=1;cout<<*it<<" "; ///上面这种方式发现可以const可以修改了！！++it;}cout<<endl;
}
void test_list5()
{list<int>lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);PrintList(lt1);
}

考虑一个问题：const对象的迭代器访问和普通对象的迭代器访问如何实现

 template<class T>
struct _list_iterator{T& operator*(){return _pnode->val;  }//控制读写const T& operator*(){return _pnode->val;  }
};
template<class T>class list{typedef _list_node<T> node;public:typedef _list_iterator<T> iterator;///只能读不能写。如何_list_iterator中如何控制读写typedef _list_iterator<T> const_iterator;///但是此时并不是说const_iterator不是本身是一个const迭代器,};

上述代码并不能实现const iterator的实际效果。

• 如何控制const _list_iterator 的只能读写。
  • 首先const T& operator*() 返回
  • 而且当前情况下的const_iterator并不能调到_list_iterator的const T& operator*。因为const T& operator*和T& operator并不能构成重载关系。
  • 其次const List<int> & lt的lt是const的。这里的iterator it本身不是const，是类型名称带了一个const。

一种方式是定义一个新的类型(struct)_list_const_iterator const_iterator。在新的类里面将函数的operator操作以const形式返回。

这种方式虽然可以但是普通迭代器和const迭代器有大量冗余，并不是好的复用。

以下代码为上述代码的相对完整版。

namespace YCB{template<class T>struct _list_node{_list_node(const T& val = T() )///这里的默认值这样处理也可以，或者下面传入的时候传一个默认的构造:_val(val),_prev(nullptr),_next(nullptr){ }T _val;_list_node<T>* _next;_list_node<T>* _prev;};template<class T>struct _list_iterator{typedef _list_node<T> node;typedef _list_iterator<T> self;node* _pnode;///封装的结点的指针_list_iterator(node* pnode):_pnode(pnode){}T& operator*(){return _pnode->val;  }//可读写T& operator*(){return _pnode->val;  }bool operator!=(const self& s) const{return _pnode !=s._pnode;}Ptr operator->(){return &_pnode->val;}//++it ->it.operator++(&it)self& operator++(){_pnode = _pnode->_next;return *this;}self& operator--(){_pnode = _pnode->_prev;return *this;}// it++ -> it.operator(&it,0)self operator++(int){self tmp(*this);_pnode=_pnode->_next;return tmp;}self operator--(int){self tmp(*this);_pnode=_pnode->_prev;return tmp;}template<class T>struct const_list_iterator{typedef _list_node<T> node;typedef _list_iterator<T> self;node* _pnode;///封装的结点的指针_list_iterator(node* pnode):_pnode(pnode){}//控制读写const T& operator*(){return _pnode->val;  }bool operator!=(const self& s) const{return _pnode !=s._pnode;}const Ptr operator->() {return &_pnode->val;}//++it ->it.operator++(&it)const self& operator++(){_pnode = _pnode->_next;return *this;}const self& operator--(){_pnode = _pnode->_prev;return *this;}// it++ -> it.operator(&it,0)self operator++(int){self tmp(*this);_pnode=_pnode->_next;return tmp;}self operator--(int){self tmp(*this);_pnode=_pnode->_prev;return tmp;}template<class T>class list{typedef _list_node<T> node;public:typedef _list_iterator<T> iterator;///只能读不能写。如何_list_iterator中如何控制读写typedef _list_iterator<T> const_iterator;///但是此时并不是说const_iterator不是本身是一个const迭代器,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;}list(){_head = new node(T());//也可以这样处理_head->_next=_head;_head->_prev=_head;}iterator erase(iterator pos){assert(pos->_pnode);assert(pos->_pnode->next!=pos->_node);node* prev=pos->_pnode->prev;node* next=pos->_pnode->next;delete pos->_pnode;prev->next=next;next->prev=prev; return iterator(next);//返回下一个位置的迭代器}private:node* _head;}
}

此时我们可以去参考库的实现，可以发现库里面实现的类里面是三个模板参数，原因何在？

源码采用通过多用两个模板参数把要重写一个const iterator类省去了。

当我们调用的const_iterator的时候就可以把对应operator*和operator->的返回值控制成const版本了。

所以最后的做法：

template<class T,class Ref,class Ptr>
struct _list_iterator{public:typedef _list_node<T> node;typedef _list_iterator<T,Ref,Ptr> self;node* _pnode;///封装的结点的指针_list_iterator(node* pnode):_pnode(pnode){}Ref operator*(){return _pnode->val;}Ptr operator->(){return &_pnode->_val;}
}
template<class T,class Ref,class Ptr>
class list{typedef _list_iterator<T,T&,T*> iterator;typedef _list_iterator<T,const T&,const T*> const_iterator;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;}
}

operator->的编译器省略

class Date{public:int _year=0;int _month=0;int _day=1;
}
void test_list2(){list<Date> lt;lt.push_back(Date());lt.push_back(Date());lt.push_back(Date());list<Date>::iterator it=lt.begin();while(it!=lt.end()){cout<<(*it)._year<<" "<<(*it)._month<<" "<<(*it)._day<<endl;cout<<it->_year<<" "<<it->_month<<" "<<it->_day<<endl; it++;}cout<<endl; 
}

对于->运算符的重载，我们直接返回结点当中所存储数据的地址即可。

Ptr operator->(){return &_pnode->_val;
}

但是我们看到返回值是一个地址。

那么使用it->_year 实际上是 it.operator->(_year) [返回值是Date* /T *] ,返回值是一个指针。

对于指针变量来说严格来说还有一个箭头才能输出Date类里的成员_year。

即it->->_year。

但是两个箭头，程序的可读性很差，所以编译器做了特殊识别处理，为了可读性，省略了一个箭头

所以调用都是一个->即可。

List的拷贝构造析构等

        list(){_head = new node(T());//也可以这样处理_head->_next=_head;_head->_prev=_head;}///法一就是for循环operator=赋值list(const list<T>& lt){_head=new node;_head->_next=_head;_head->_prev=_head;for(const auto&e : lt){///这里是调用了operator=给epush_back(e);}}//传统版本list<T>& operator=(const list<T>& lt){if(this!=&lt){clear();//留下哨兵位for(const auto&e :lt){push_back(e);}}return *this;}		//现代版本list<T>& operator=(list<T> lt){swap(_head,lt._head);return *this;}~list(){clear();delete _head;_head=nullptr;}void clear(){iterator it=begin();while(it!=end()){it=erase(it);///注意不能++，erase会返回下一个位置//erase(it++);}}

测试场景:

void test_vector3(){list<int>lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);while(lt!=end()){cout<<*lt<<" ";}cout<<endl;list<int>lt2(lt);//默认生成的浅拷贝while(lt2!=end()){cout<<*lt2<<" ";}cout<<endl;list<int>lt3;lt3.push_back(10);lt3.push_back(20);lt2=lt3;while(lt2!=end()){cout<<*lt2<<" ";}cout<<endl;while(lt3!=end()){cout<<*lt3<<" ";}cout<<endl;
}

list接口的基本实现

namespace YCB{template<class T>struct _list_node{_list_node(const T& val = T() )///这里的默认值这样处理也可以，或者下面传入的时候传一个默认的构造:_val(val),_prev(nullptr),_next(nullptr){ }T _val;_list_node<T>* _next;_list_node<T>* _prev;};template<class T,class Ref,class Ptr>struct _list_iterator{typedef _list_node<T> node;typedef _list_iterator<T,Ref,Ptr> self;node* _pnode;///封装的结点的指针_list_iterator(node* pnode):_pnode(pnode){}Ref operator*(){return _pnode->val;  }Ptr operator*(){return _pnode->val;  }bool operator!=(const self& s) const{return _pnode !=s._pnode;}Ptr operator->(){return &_pnode->val;}//++it ->it.operator++(&it)self& operator++(){_pnode = _pnode->_next;return *this;}self& operator--(){_pnode = _pnode->_prev;return *this;}// it++ -> it.operator(&it,0)self operator++(int){self tmp(*this);_pnode=_pnode->_next;return tmp;}self operator--(int){self tmp(*this);_pnode=_pnode->_prev;return tmp;}};template<class T>class list{typedef _list_node<T> node;public:typedef _list_node<T> node;typedef _list_iterator<T, T&, T*> iterator;typedef _list_iterator<T, const T&, const T*> const_iterator;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;}list(){_head = new node(T());//也可以这样处理_head->_next=_head;_head->_prev=_head;}void push_back(){node* newnode=new node(x);node* tail=_head->_prev;newnode->_prev=tail;newnode->next=_head;tail->next=newnode;_head->_prev=newnode;}void insert(iterator pos,const T&x){node* cur=pos->_pnode;node* prev=cur->prev;node* newnode=new Node(x);prev->next=newcode;newcode->prev=prev;newcode->next=cur;cur->prev=newcode;}iterator erase(iterator pos){assert(pos->_pnode);assert(pos->_pnode->next!=pos->_node);node* prev=pos->_pnode->prev;node* next=pos->_pnode->next;delete pos->_pnode;prev->next=next;next->prev=prev; return iterator(next);//返回下一个位置的迭代器}void push_back(const T&x){insert(end(),x);}void push_front(const T&x){insert(begin(),x);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}bool empty() const{return begin()==end();}//效率很低，放个变量在private里记录就行。stl后面版本实现了size_t size(){size_t sz=0;iterator it=begin();while(it!=end()){++sz;++it;}return sz;}private:node* _head;};
};

string，vector，list的迭代器

对于string和vector来说物理空间连续

• string::iterator ——>char*

• vector::iterator——>T*

而对于list来说物理空间不连续

假如用原生指针，Node*，解引用获得的不是值（是结点），++也不是跳到下一个元素。——>原生指针已经无法完成迭代器的功能。

_list_iterator去封装Node*，重载这个类的operator *，operator++等等运算符，去模拟像指针一样的行为。

有了这样的方式，不关心容器底层的结构到底是数组还是链表还是树形结构等等。用统一的方式封装了隐藏了底层的细节。——迭代器的价值

Container::iterator it=con.begin();
while(it!=con.end())
{*it;it++;
}

• 迭代器遍历使用!=end()，既可以满足之前的顺序表，也可以满足现在的链表以及之后的stl
• 对于迭代器采用的拷贝模式，因为想要指向空间即可，采用默认的浅拷贝。同时不析构，因为析构应是归list管的而不是迭代器管的。（不然每次开那么多迭代器数据就没了）