目录

• 1.迭代器和原生指针的区别
• 2.拷贝构造，析构和赋值重载是否需要我们自己实现？
• 3.list中的const的模拟实现
• 4.->的相关问题
• 5.insert和erase的迭代器失效问题
• 6.构造函数的一个问题
• 7.代码实现

1.迭代器和原生指针的区别

void f(){Node* pnode = _head->_next;iterator it = _head->_next;*pnode;*it;++pnode;++it;}

Node*原生指针和一个迭代器对象，他们占用空间是一样大的，都是4byte并且存的值也是一样的。但是对他们使用运算符的意义和结果是不一样的。

2.拷贝构造，析构和赋值重载是否需要我们自己实现？

迭代器是借助节点的指针访问修改链表
节点属于链表，不属于迭代器，所以他不管释放
都不需要自己实现，默认生成的即可

原因分析：
你将一个迭代器去拷贝构造成另外一个迭代器，是需要浅拷贝还是深拷贝？
浅拷贝，所以就不需要。

3.list中的const的模拟实现

const对于我们的要求来说，只需要满足只读不写就可以了
他的一些常规操作和我们实现的普通类型是一样的

我们参考list的源代码，我们可以使用模板参数来进行实现
代码请见下面list实现

4.->的相关问题

struct Date{int _year;int _month;int _day;Date(int year = 1, int month = 1, int day = 1):_year(year), _month(month), _day(day){}};void test_list2(){list<Date> lt;lt.push_back(Date(2022, 3, 12));lt.push_back(Date(2022, 3, 13));lt.push_back(Date(2022, 3, 14));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;}

先说结果，但是为什这样可以？

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

it->_year相当于 it.operator->()
返回的是Date*
Date* 访问_year 应该是it->->_year
但是这样写的话，运算符可读性太差
所以这里编译器进行了优化，省略了一个->
素有类型只要想重载->都是这样的，都会优化。省略一个->

5.insert和erase的迭代器失效问题

// 这里insert以后，pos是否失效？不失效iterator insert(iterator pos, const T& x){Node* cur = pos._node;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以后，pos是否失效？一定失效// 节点删除了，迭代器也就失效了iterator erase(iterator pos){assert(pos != end());Node* prev = pos._node->_prev;Node* next = pos._node->_next;delete pos._node;prev->_next = next;next->_prev = prev;return iterator(next);}

延伸：
vector的erase之后迭代器会不会失效？
vector她erase后，说不定空间会缩容，所以可能会失效

6.构造函数的一个问题

list(size_t n, const T& val = T()){_head = new Node();_head->_next = _head;_head->_prev = _head;for (size_t i = 0; i < n; ++i){push_back(val);}}

当我们构造:

   // list lt2(5, 1);   时？就会出现问题，因为：

template<class InputIterator>list(InputIterator first, InputIterator last){_head = new Node();_head->_next = _head;_head->_prev = _head;while (first != last){push_back(*first);++first;}}

1 是int类型，int不能解引用

7.代码实现

reverse_iterator.h

#pragma once  namespace sakeww{// // Iterator是哪个容器的迭代器，reverse_iterator就可以// 适配出哪个容器的反向迭代器，复用的体现template <class Iterator, class Ref, class Ptr>class reverse_iterator{typedef reverse_iterator<Iterator, Ref, Ptr> self;//typedef typename Iterator::Ref Ref;//typedef typename Iterator::Ptr Ptr;//凡是要取一个模板的内嵌类型，就要加typename，//告诉编译器后面的是类型，先让他过，现在去找他的类型是找不到的//等着类模板实例化了再去找他的具体类型public:reverse_iterator(Iterator it):_it(it){}typename Iterator::reference operator*(){//我们理解的实现//return *_it;//源码实现Iterator prev = _it;return *--prev;}typename Iterator::pointer operator->(){return &operator*();}self& operator++(){--_it;return *this;}self& operator--(){++_it;return *this;}bool operator!= (const self& rit) const{return _it != rit._it;}private:Iterator _it;};}

list.h(内含部分测试用例)

#include"reverse_iterator.h"namespace sakeww{template<class T>struct ListNode{ListNode* _next;ListNode* _prev;T _data;ListNode(const T& data = T()):_next(nullptr), _prev(nullptr), _data(data){}};template<class T, class Ref, class Ptr>struct __list_iterator{typedef ListNode<T> Node;typedef __list_iterator<T, Ref, Ptr> self;typedef Ref reference;typedef Ptr pointer;//typedef __list_iteratorNode* _node;__list_iterator(Node* x):_node(x){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}// ++itself& operator++(){_node = _node->_next;return *this;}// it++self operator++(int){self tmp(*this);_node = _node->_next;return tmp;}// --itself& operator--(){_node = _node->_prev;return *this;}// it--self operator--(int){self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const self& it) const{return _node != it._node;}bool operator==(const self& it) const{return _node != it._node;}};template<class T>class list{typedef ListNode<T> Node;public:typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;typedef reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;typedef reverse_iterator<iterator, T&, T*> reverse_iterator;reverse_iterator rbegin(){return reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}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;_head->_next = _head;_head->_prev = _head;}// list lt1(5, Date(2022, 3, 15)); // list lt2(5, 1);list(int n, const T& val = T()){_head = new Node();_head->_next = _head;_head->_prev = _head;for (int i = 0; i < n; ++i){push_back(val);}}list(size_t n, const T& val = T()){_head = new Node();_head->_next = _head;_head->_prev = _head;for (size_t i = 0; i < n; ++i){push_back(val);}}template<class InputIterator>list(InputIterator first, InputIterator last){_head = new Node();_head->_next = _head;_head->_prev = _head;while (first != last){push_back(*first);++first;}}// lt2(lt1)list(const list<T>& lt){_head = new Node();_head->_next = _head;_head->_prev = _head;list<T> tmp(lt.begin(), lt.end());std::swap(_head, tmp._head);}// lt2 = lt1list<T>& operator=(list<T> lt){std::swap(_head, lt._head);return *this;}//lt2(lt1)传统写法//list(const list& lt)//{//_head = new Node();//_head->_next = _head;//_head->_prev = _head;//for (auto e : lt)//{//push_back(e);//}//} lt2 = lt1传统写法//list& operator=(const list& lt)//{//if (this != &lt)//{//clear();//for (auto e : lt)//{//push_back(e);//}//}//return *this;//}~list(){clear();delete _head;_head = nullptr;}void clear(){/*iterator it = begin();while (it != end()){iterator del = it++;delete del._node;}_head->_next = _head;_head->_prev = _head;*/iterator it = begin();while (it != end()){erase(it++);}}//头插void push_front(const T& x){insert(begin(), x);}void push_back(const T& x){//Node* tail = _head->_prev;//Node* newnode = new Node(x);//tail->_next = newnode;//newnode->_prev = tail;//newnode->_next = _head;//_head->_prev = newnode;insert(end(), x);}//尾删void pop_back(){erase(--end());}//头删void pop_front(){erase(begin());}// 这里insert以后，pos是否失效？不失效iterator insert(iterator pos, const T& x){Node* cur = pos._node;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以后，pos是否失效？一定失效iterator erase(iterator pos){assert(pos != end());Node* prev = pos._node->_prev;Node* next = pos._node->_next;delete pos._node;prev->_next = next;next->_prev = prev;return iterator(next);}private:Node* _head;};void print_list(const list<int>& lt){list<int>::const_iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;}void test1(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);//lt.f();// 访问修改容器list<int>::iterator it = lt.begin();while (it != lt.end()){*it *= 2; // 修改cout << *it << " ";++it;}cout << endl;print_list(lt);}struct Date{int _year;int _month;int _day;Date(int year = 1, int month = 1, int day = 1):_year(year), _month(month), _day(day){}};void test2(){list<Date> lt;lt.push_back(Date(2022, 3, 12));lt.push_back(Date(2022, 3, 13));lt.push_back(Date(2022, 3, 14));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;}void test3(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);list<int> lt2(lt);for (auto e : lt2){cout << e << " ";}cout << endl;list<int> lt3;lt3.push_back(10);lt3.push_back(10);lt3.push_back(10);lt3.push_back(10);lt = lt3;for (auto e : lt){cout << e << " ";}cout << endl;}void test4(){list<Date> lt(5, Date(2022, 3, 15));for (auto e : lt){cout << e._year << "/" << e._month << "/" << e._day << endl;}cout << endl;list<int> lt2(5, 1);for (auto e : lt2){cout << e << " ";}cout << endl;}void test5(){list<int> lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);list<int>::iterator it = lt1.begin();while (it != lt1.end()){//*it *= 2; // 修改cout << *it << " ";++it;}cout << endl;list<int>::reverse_iterator rit = lt1.rbegin();while (rit != lt1.rend()){cout << *rit << " ";++rit;}cout << endl;}}