list(二) （list模拟实现）

首先进行大框架  先写基本的结点类  有data next  prev

	template<class T>class ListNode//或者使用struct 就不用在写public声明公有{public://这里不仅仅是成员函数 成员变量也要公有化 ListNode<T>*  _next;ListNode<T>*  _prev;T _data;}

之后是链表list类的构造

template<class T>
class list
{typedef ListNode<T> Node;
public:list(){_head = new Node;_head->_next = _head;_head->_prev = _head;}
private:Node* _head;
};

私有成员是节点类型的指正 会在构造时指向我们的头节点

这里 我们创建的列表是带头双向循环链表  所以在初始化时让头节点的next 和prev指向自己  

接下来要模拟尾差 push_back  带头双向循环链表  是创建一个新节点  然后让新节点的prev指向尾节点  尾结点的next指向新节点 新节点的next指向头节点 头节点的prev指向新节点  

void push_back(const T& x)
{Node* newnode = new Node(x);Node* tail = _head->_prev;tail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;}

这里由于是双向带头循环链表 所以我们的尾节点就是头节点的prev指向的结点 所以我们不需要手动更新尾节点的位置  每次插入完成后 新节点会自动成为尾节点

这里在测试时会出现一些问题

1.按需实例化  那就是一些类和函数的一些语法问题 在没有被调用时系统不会检查报错 只有使用时实例化模版 这是才会报错

2.在上面的节点类中我们只写了成员函数而没有写构造函数 需要补充

3.关于私有公有的问题  我们的类在默认情况下是私有的  只有public下才能允许外界访问  而struct在默认情况下是全部共有的

template<class T>
class ListNode//或者使用struct 就不用在写public声明公有
{
public:
//这里不仅仅是成员函数 成员变量也要公有化 ListNode<T>*  _next;ListNode<T>*  _prev;T _data;ListNode(const T& data )//这里也可以用匿名对象写成全缺省: _next(nullptr), _prev(nullptr), _data(data) {}};	

这里我们上面的list在构造时并没有在头结点进行初始化赋值 而我们的push_bcak函数对新节点创立时进行了赋值  所以为了保持一致  要对头结点创建时进行赋值 也就是要有一个缺省值  但是这里不能给0  因为date 是T类型的  有可能是double 有可能是string  不能使用0赋值

那我们应该如何赋值给头结点呢 可以考虑给匿名对象

也可以在结点创建处参数写成全缺省

template<class T>
class ListNode//或者使用struct 就不用在写public声明公有
{
public:
//这里不仅仅是成员函数 成员变量也要公有化 ListNode<T>*  _next;ListNode<T>*  _prev;T _data;ListNode(const T& data = T() )//这里也可以用匿名对象写成全缺省: _next(nullptr), _prev(nullptr), _data(data) {}};	

这时进行测试

void list1()//在没有没有实例化以前检查是没有意义的 因为细节不会检查模版 只有实例化以后才会被检查
{//按需实例化 在没有实例化之前不会检查细节 同时只有调用这部分才会检查这部分（除了一些大的语法错误）在没实例化之前不会检查其对应部分list<int> l1;//不调用 就不实例化这个成员函数l1.push_back(1);l1.push_back(2);l1.push_back(1);l1.push_back(5);l1.push_back(10);l1.push_back(15);
}

这时push_back就可以正常使用了

接下来要模拟list迭代器  

迭代器++要到达下一个位置 但是这里的list节点不符合  list节点可以通过next指向到达下一个结点  

所以可以通过重载++实现迭代器模拟

template<class T>
class ListIterator//这里也存在私有的问题 需要使用public
{
public://这里也不用太担心公有化访问的 问题 不同的编译器下底层实现的代码是不同的 也就是名字不一定相同 同时正常一般是直接回调用迭代器 不会直接访问类成员typedef ListNode<T> Node;typedef ListIterator<T> Self;Node* _node;ListIterator(Node* node):_node(node){}//这个迭代器要不要写析构 不要  这个迭代器指向的空间是链表的 不希望被析构//这里也不需要拷贝构造 因为这里需要的就是浅拷贝 所以默认生成的拷贝构造就够用  所以默认生成的浅拷贝也是有些意义的 并不是完全没意义T& operator * () //每个类都能重载运算符 当重载号运算符之后就能控制一个类的行为{return _node->_data;}Self& operator ++(){_node = _node->_next;return *this;}
bool operator !=(const Self& it)
{return _node != it._node;
} 
};

这里迭代器的模拟重新使用了一个类来进行重载  这里的类成员就是一个结点指针  构造是对结点指针进行初始化构造   在一般的迭代器循环中 最常用到的是++  解引用   ！=   三个重载   这里先谢了这三个   这里的所有成员变量和函数 都是需要的  所以设置为公有public

实现这个类之后  在list类中typedef  iterator   这里为什么不直接使用listIterator  这是为了统一名称  

使代码使用更加流畅   同时在list类中实现  begin（）  end（） 成员函数

template<class T>
class list
{typedef ListNode<T> Node;public:
typedef ListIterator<T > iterator; //每个类都要使用iterator去规范迭代器  这样每个容器使用的都是iterator 这样使用起来方便 成本较低iterator begin()
{/*iterator it(_head->_next);return it;*/ //定义有名对象不如定义匿名对象return iterator(_head -> _next);
}
iterator end()
{return iterator (_head);
}list(){_head = new Node;_head->_next = _head;_head->_prev = _head;}void push_back(const T& x)
{Node* newnode = new Node(x);Node* tail = _head->_prev;tail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;}private:Node* _head;
};

这里对于内置类型无法重载运算符 只有自定义类型才能重载运算符

	void list1()//在没有没有实例化以前检查是没有意义的 因为细节不会检查模版 只有实例化以后才会被检查{//按需实例化 在没有实例化之前不会检查细节 同时只有调用这部分才会检查这部分（除了一些大的语法错误）在没实例化之前不会检查其对应部分list<int> l1;//不调用 就不实例化这个成员函数l1.push_back(1);l1.push_back(2);l1.push_back(1);l1.push_back(5);l1.push_back(10);l1.push_back(15);list<int>::iterator it = l1.begin();while (it != l1.end()){cout << *it << " ";++it;}cout << endl;}

这里可以看到我们的初代迭代器是可以正常运行的

接下来我们继续通过重载的方式对迭代器进行进一步的完善  

template<class T>
class ListIterator//这里也存在私有的问题 需要使用public
{
public://这里也不用太担心公有化访问的 问题 不同的编译器下底层实现的代码是不同的 也就是名字不一定相同 同时正常一般是直接回调用迭代器 不会直接访问类成员typedef ListNode<T> Node;typedef ListIterator<T> Self;Node* _node;ListIterator(Node* node):_node(node){}//这个迭代器要不要写析构 不要  这个迭代器指向的空间是链表的 不希望被析构//这里也不需要拷贝构造 因为这里需要的就是浅拷贝 所以默认生成的拷贝构造就够用  所以默认生成的浅拷贝也是有些意义的 并不是完全没意义T& operator * () //每个类都能重载运算符 当重载号运算符之后就能控制一个类的行为{return _node->_data;}Self& operator ++(){_node = _node->_next;return *this;}Self& operator --()
{_node = _node->_prev;return *this;
}Self  operator ++(int)//这里是后置加加 参数中有int用来与前置++作区分
{Self tmp(*this);//这里返回的是加加之前的值的 所以需要提前保存一下_node = _node->_next;return *tmp;
}Self  operator --(int)
{Self tmp(*this);_node = _node->_prev;return *tmp;
}bool operator !=(const Self& it)
{return _node != it._node;
} bool operator ==(const Self& it)
{return _node == it._node;
}};

这里注意前置 与后置的 区别 前置返回的是引用的self  而后置则不引用直接返回self  同时为了区分前置和后置 在后置函数的括号中加了int   同时++是向下一个next移动  而--则是像下一个prev移动

这里要不要重载+和-  是不要的  因为+ 和-的效率非常低  如果要加10 那么就要向前走十次  

即便是在std库中也是没有重载+和-的

这里迭代器类是不需要析构函数的  这里并不希望迭代器释放   这里也不要写深拷贝构造 这里默认拷贝构造 和默认析构就够用

这里也支持修改 支持迭代器也就支持范围for

void list1()//在没有没有实例化以前检查是没有意义的 因为细节不会检查模版 只有实例化以后才会被检查
{//按需实例化 在没有实例化之前不会检查细节 同时只有调用这部分才会检查这部分（除了一些大的语法错误）在没实例化之前不会检查其对应部分list<int> l1;//不调用 就不实例化这个成员函数l1.push_back(1);l1.push_back(2);l1.push_back(1);l1.push_back(5);l1.push_back(10);l1.push_back(15);list<int>::iterator it = l1.begin();while (it != l1.end()){*it += 10;cout << *it << " ";++it;}cout << endl;for (auto e : l1){cout << e << " ";}cout << endl;
}

这里对迭代器进行进一步的加工

如果存在自定义类型pos类的链表来进行遍历

struct pos//这里需要提供默认构造
{int _row;int _col;pos(int row = 0, int col= 0)//这里写成全缺省提供默认构造:_row(row), _col(col){}
};

这是pos类的结构

可见一个pos中分别有横纵坐标

void list2()
{list<pos> l1;l1.push_back(pos(100,100));l1.push_back(pos(200, 200));l1.push_back(pos(300, 100));list<pos>::iterator it = l1.begin();while(it != l1.end()){cout << *it << " ";++it;}cout << endl;
}

这时我们的代码是无法正常运行的

正常运行的方法一  通过.来获取成员变量

void list2()
{list<pos> l1;l1.push_back(pos(100,100));l1.push_back(pos(200, 200));l1.push_back(pos(300, 100));list<pos>::iterator it = l1.begin();while(it != l1.end()){cout << (*it)._row << ":" << (*it). _col << endl;++it;}cout << endl;
}

方法2 也可以使用箭头->

void list2()
{list<pos> l1;l1.push_back(pos(100,100));l1.push_back(pos(200, 200));l1.push_back(pos(300, 100));list<pos>::iterator it = l1.begin();while(it != l1.end()){cout << it->_row << ":" << it-> _col << endl;++it;}cout << endl;
}

但是想要使用箭头 我们就需要再迭代器的类中重载->

	template<class T>class ListIterator//这里也存在私有的问题 需要使用public{public://这里也不用太担心公有化访问的 问题 不同的编译器下底层实现的代码是不同的 也就是名字不一定相同 同时正常一般是直接回调用迭代器 不会直接访问类成员typedef ListNode<T> Node;typedef ListIterator<T> Self;Node* _node;ListIterator(Node* node):_node(node){}//这个迭代器要不要写析构 不要  这个迭代器指向的空间是链表的 不希望被析构//这里也不需要拷贝构造 因为这里需要的就是浅拷贝 所以默认生成的拷贝构造就够用  所以默认生成的浅拷贝也是有些意义的 并不是完全没意义T& operator * () //每个类都能重载运算符 当重载号运算符之后就能控制一个类的行为{return _node->_data;}T* operator ->(){return &_node->_data;}Self& operator ++(){_node = _node->_next;return *this;}Self& operator --(){_node = _node->_prev;return *this;}Self  operator ++(int)//这里是后置加加 参数中有int用来与前置++作区分{Self tmp(*this);//这里返回的是加加之前的值的 所以需要提前保存一下_node = _node->_next;return *tmp;}Self  operator --(int){Self tmp(*this);_node = _node->_prev;return *tmp;}bool operator !=(const Self& it){return _node != it._node;}bool operator ==(const Self& it){return _node == it._node;}};

这时代码就可以自由使用

这里访问的其实有两箭头   :cout<< it .operator-> ()-> _row <<" :"<< it.operator->() ->_col;

第一个箭头返回 pos*  第二个箭头访问成员变量

但是为了美观 就省略为了一个箭头

const迭代器问题

这里先写一个func函数用来使用const迭代器进行遍历

void func(const list<int>&it)
{ list<int>::iterator it1 = it.begin();while (it1 != it.end()){cout << *it1 << " ";++it1;}cout << endl;
}

这里普通迭代器显然是无法使用 需要const迭代器  不能直接使用const修饰iterator  因为const迭代器类似于const指针  const迭代器的目的是想要迭代器指向的内容不能修改 而迭代器本身是可以修改的   直接使用const无法达到效果   

而想要迭代器指向的内容无法修改的核心是通过控制operator * 和 operator->返回的内容不能修改

而这里想要修改 就需要一个新的类 它与普通的迭代器类大体相似 但在一些关键地方上不同

template<class T>
class constListIterator//这里也存在私有的问题 需要使用public
{
public://这里也不用太担心公有化访问的 问题 不同的编译器下底层实现的代码是不同的 也就是名字不一定相同 同时正常一般是直接回调用迭代器 不会直接访问类成员typedef ListNode<T> Node;typedef constListIterator<T> Self;Node* _node;constListIterator(Node* node):_node(node){}//这个迭代器要不要写析构 不要  这个迭代器指向的空间是链表的 不希望被析构//这里也不需要拷贝构造 因为这里需要的就是浅拷贝 所以默认生成的拷贝构造就够用  所以默认生成的浅拷贝也是有些意义的 并不是完全没意义const T& operator * () //每个类都能重载运算符 当重载号运算符之后就能控制一个类的行为{return _node->_data;}const T* operator ->(){return &_node->_data;}Self& operator ++(){_node = _node->_next;return *this;}Self& operator --(){_node = _node->_prev;return *this;}Self  operator ++(int)//这里是后置加加 参数中有int用来与前置++作区分{Self tmp(*this);//这里返回的是加加之前的值的 所以需要提前保存一下_node = _node->_next;return *tmp;}Self  operator --(int){Self tmp(*this);_node = _node->_prev;return *tmp;}bool operator !=(const Self& it){return _node != it._node;}bool operator ==(const Self& it){return _node == it._node;}};

这里我们只修改类的名字为constiterator  同时对operator* 和operator->返回进行const修饰

同时在list类中 也要加入相对应的const_iterator别名  同时添加const迭代器使用begin和end成员函数

template<class T>
class list
{typedef ListNode<T> Node;public:typedef ListIterator<T > iterator; //每个类都要使用iterator去规范迭代器  这样每个容器使用的都是iterator 这样使用起来方便 成本较低typedef constListIterator<T> const_iterator;iterator begin(){/*iterator it(_head->_next);return it;*/ //定义有名对象不如定义匿名对象return iterator(_head->_next);}iterator end(){return iterator(_head);}const_iterator begin() const{/*iterator it(_head->_next);return it;*/ //定义有名对象不如定义匿名对象return const_iterator(_head->_next);}const_iterator end()  const{return const_iterator(_head);}list(){_head = new Node;_head->_next = _head;_head->_prev = _head;}void push_back(const T& x){Node* newnode = new Node(x);Node* tail = _head->_prev;tail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;}private:Node* _head;
};

这里进行测试

void func(const list<int>& it)
{list<int>::const_iterator it1 = it.begin();while (it1 != it.end()){cout << *it1 << " ";++it1;}cout << endl;
}void list3()
{list<int> l1;l1.push_back(1);l1.push_back(2);l1.push_back(1);func(l1);}

const迭代器已经可以正常运行

一个const迭代器 和一个普通的迭代器 两者之间非常的冗余 而且有很大的相似程度 这里我们可以用一个类来同时实现两个迭代器的功能

可以通过增加模版参数来实现

template<class T, class ref, class ptr>
class ListIterator//这里也存在私有的问题 需要使用public
{
public://这里也不用太担心公有化访问的 问题 不同的编译器下底层实现的代码是不同的 也就是名字不一定相同 同时正常一般是直接回调用迭代器 不会直接访问类成员typedef ListNode<T> Node;typedef ListIterator<T,ref,ptr> Self;Node* _node;ListIterator(Node* node):_node(node){}//这个迭代器要不要写析构 不要  这个迭代器指向的空间是链表的 不希望被析构//这里也不需要拷贝构造 因为这里需要的就是浅拷贝 所以默认生成的拷贝构造就够用  所以默认生成的浅拷贝也是有些意义的 并不是完全没意义ref operator * () //每个类都能重载运算符 当重载号运算符之后就能控制一个类的行为{return _node->_data;}ptr operator->() {return & _node->_data;}Self& operator ++(){_node = _node->_next;return *this;}Self& operator --(){_node = _node->_prev;return *this;}Self  operator ++(int)//这里是后置加加 参数中有int用来与前置++作区分{Self tmp(*this);//这里返回的是加加之前的值的 所以需要提前保存一下_node = _node->_next;return *tmp;}Self  operator --(int){Self tmp(*this);_node = _node->_prev;return *tmp;}bool operator !=(const Self& it){return _node != it._node;} bool operator ==(const Self& it){return _node == it._node;}
};

同时在list类中typedef时分别用不用的参数类型来使用不同的迭代器功能  通过模版参数 给不同的模版参数 让编译器来给我们写两个类（实例化）

typedef ListIterator<T ,T&,T*> iterator; //每个类都要使用iterator去规范迭代器  这样每个容器使用的都是iterator 这样使用起来方便 成本较低
//初始化
typedef ListIterator<T,const T&,const T*> const_iterator;
//typedef ListIterator<const T> const_iterator; 这种写法是不可取的 当这样写时虽然迭代器中的符合const迭代器的要求 但是我们链表中的Node是还是T 而迭代器中的是const T 在两者类型不用 实参是无法传给形参的

这样测试用例也是可以正常运行

最后在来模拟一下insert 和erase 

链表的insert 通过 对pos位置的结点 和 pos位置的prev指向节点之间插入一个新节点

这里创立prev节点 和cur节点 指针     prev指向cur指向节点的prev指向节点  cur指向pos位置的节点    同时有newnode作为新插入节点的指针  首先prev节点的next指向newnode  newnode节点的prev指向prev节点  newnode节点的next指向cur的结点  cur节点的prev 指向newnode节点

这时就插入成功了 

且这里的insert是没有迭代器失效的 但是库中仍然给了返回值

iterator insert (iterator pos , const T&x)
{Node* cur = pos._node;//这里pos指向的迭代器没有改变 所以没有失效  但是库中仍然返回了一个值 Node* prev = cur->_prev;Node* newnode = new Node(x);prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;return iterator(newnode);
}

erase函数则是通过创建 prev和next指针分别指向 pos位置上一个节点 和下一个结点来进行连接

同时将now指向的pos位置的节点通过delete进行删除  这里存在迭代器失效  且只有pos位置的迭代器失效 其他位置正常  这里通过给返回值返回删除前下一个位置 来更新迭代器  这里通过断言 防止将头结点删掉

iterator erase(iterator pos)//这里存在迭代器失效的问题 
{assert(pos != end());Node* now = pos._node;Node* prev = now->_prev;Node* next = now->_next;prev->_next = next;next->_prev = prev;delete now;return iterator(next);
}

之后通过代码复用 通过insert 和erase可以快速写出 push_back  push_front  pop_back pop_front

void push_back(const T& x)
{/*Node* newnode = new Node(x);Node* tail = _head->_prev;tail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;*/insert(end(),x);
}
void pop_back()//持续的删除是有可能会将哨兵位给删掉的 所以要加断言  断言在erase函数
{erase(--end());
}void push_front(const T& x)
{insert(begin(),x);
}
void pop_front()
{erase(begin());
}

接下来要写拷贝构造和析构函数 

在我们现在的代码上写拷贝测试是没有问题的 那是因为我们没有写析构函数  有了析构以后 由于是默认生成的浅拷贝 就会发生两次析构同一片空间的情况 从而报错

这里我们先写一个clear函数 在通过对clear函数进行复用 实现析构函数  这里clear函数就是通过一次次erase删除并且更新迭代器  最后将整个链表有效元素清除干净

void clear()
{auto it = begin();while (it != end()){it = erase(it);//这里erase返回的是删除前pos位置的下一个位置 所以不需要++}
}

传统链表的析构方式就是一个节点一个节点的释放

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

最后再讲头节点也删除  将头结点指针指向空  完成析构

这时由于有了析构函数 而且没有写自己拷贝构造 那么这时就会报错 因为会析构两次

	void list4(){list<int> l1;l1.push_back(1);l1.push_back(2);l1.push_back(1);func(l1);list<int> l2(l1);//这里使用的是浅拷贝 是系统默认的拷贝构造 这里没有报错 是因为这里没有写析构函数 l1.push_back(10);//这里在l1中插入10 结果打印l2会出现10 说明浅拷贝 两者指向一个空间中func(l1);func(l2);}

这里我们就需要写自己的深拷贝构造

void empty_init()//这里想要直接复用 就需要有一个哨兵位头结点
{_head = new Node();_head->_next = _head;_head->_prev = _head;}//拷贝构造
list(const list<T>& it)//这里本来需要一个结点一个结点深拷贝 但是通过空初始化获得哨兵位头节点 就可以直接进行尾插深拷贝
{empty_init();//创建哨兵位头结点 空初始化for (const auto& e : it)//这里本质上就是e迭代器 并将*it赋值给e 这里的如果T是int之类的内置类型是无所谓的 但是如果是自定义类型 这是就会发生深拷贝 这样会造成损耗{push_back(e); }
}
list()
{empty_init();
}

这里无论是普通构造 还是拷贝构造 我们都要创建头结点 所以将头结点创建写成一个单独的empty_init函数 之后复用   拷贝构造在创建好头节点后 就开始遍历要拷贝的链表 将其节点一个个尾插进入当前的头结点 完成深拷贝

这时我们的代码就能正常运行了

这里使用范围for的时候 如果无法确定其类型  那么保险起见最好加引用

for(const auto & e : lt)

赋值构造

list<T>& operator=(list<T> it)//这里是传值传参 所以这里的it就是右边的深拷贝 可以直接交换
{swap(_head,it._head);return *this;
}

通过传值传参 参数的深拷贝与this指指针进行交换  直接完成赋值

在我们没有写initializer_list构造之前  下面的测试是无法通过的

void list5()
{list<int>l1 = { 1,2,3,4,5,8,9,7 };//链表真正重要的地方就是迭代器func(l1);
}

initializer_list构造

	list(initializer_list<T> il)//这里可以不用加引用 原因是initializer可以直接把值给他 相当于一个数组 initializer有两个指针 一个指向数组开头 一个指向结尾{empty_init(); //构造都要先把哨兵位头节点弄出来for (const auto &e :il){push_back(e);}}

这里我们创建好头节点之后就通过对要插入的内容进行遍历同时一次次尾插进行当前链表  

这样我们的代码就可以正常运行了