list模拟实现【引入反向迭代器】

1.适配器

1.1传统意义上的适配器

1.2语言里的适配器

1. 容器适配器，如下：
   
   
2. 迭代器适配器【以下会讲】
3. 函数适配器【以后会讲】

1.3理解

所谓适配器，其实就是通过C++STL泛型编程的特性，使用模板参数实例化出不同的实体供调用者使用。根据传参实例化出不同实体的过程类似实际生活中的适配器【电源适配器可以转换不同伏特的电流供接收者使用】
例如：程序员实现了一个反向迭代器 在使用vector、list、map时可以将本身的正向迭代器传给模板参数
这样不用在每次用一个新的容器时 重复写反向迭代器 通过模板实例化 增强代码复用性

2.list模拟实现【注意看反向迭代器】

2.1 list_frame.h

namespace Apex
{//结点类template<class T>struct list_node{//成员变量T _data;list_node<T>* _next;list_node<T>* _prev;//成员函数//构造函数list_node(const T& data = T());};//迭代器类template<class T, class Ref, class Ptr>struct __list_iterator{typedef list_node<T> Node;typedef __list_iterator<T, Ref, Ptr> iterator;typedef T value_type;typedef Ref reference;typedef Ptr pointer;//成员变量Node* _node;//成员函数//构造函数__list_iterator(Node* node);//解引用运算符重载Ref operator*();//成员访问符重载Ptr operator->();//前置++iterator& operator++();//后置++iterator operator++(int);//前置--iterator& operator--();//后置--iterator operator--(int);//关系运算符bool operator==(const iterator& it);bool operator!=(const iterator& it);};//链表类template<class T>class list{typedef list_node<T> Node;public:typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;typedef __reverse_iterator<iterator, T&, T*> riterator;typedef __reverse_iterator<const_iterator, const T&, const T*> const_riterator;//成员函数//迭代器函数iterator begin();const_iterator begin() const;iterator end();const_iterator end() const;riterator rbegin();const_riterator rbegin() const;riterator rend();const_riterator rend() const;//无参构造函数list();//有参构造函数(初始化n个结点)list(size_t n, const T& val = T());//迭代器构造函数template<class InputIterator>list(InputIterator first, InputIterator last);//清空链表数据void clear();//析构函数~list();//拷贝构造list(const list<T>& lt);//赋值重载list<T>& operator=(list<T> lt);//pos前插入void insert(iterator pos, const T& x);//删除pos处数据iterator erase(iterator pos);//尾插void push_back(const T& x);//头插void push_front(const T& x);//尾删void pop_back();//头删void pop_front();private:Node* _head;};
}

2.2riterator.h

#pragma oncenamespace apex
{template<class Iterator, class Ref, class Ptr>struct __reverse_iterator{Iterator _cp;typedef __reverse_iterator<Iterator, Ref, Ptr> riterator;typedef Iterator value_type;typedef Ref reference;typedef Ptr pointer;//构造函数__reverse_iterator(Iterator it):_cp(it){}//解引用运算符重载Ref operator*(){auto tmp = _cp;return *--tmp;}//成员访问符重载Ptr operator->(){return &(operator*());  //return --_cp.operator->();}//前置++riterator operator++(){--_cp;return *this;}//后置++riterator operator++(int) {riterator tmp(*this);--_cp;return tmp;}//前置--riterator operator--(){++_cp;return *this;}//后置--riterator operator--(int){riterator tmp(*this);++_cp;return tmp;}//关系运算符bool operator==(const riterator& it){return _cp == it._cp;}bool operator!=(const riterator& it){return _cp != it._cp;}};
}

2.3list.h

#include <iostream>
#include <assert.h>
#include "riterator.h"
using namespace std;namespace apex
{//公有类--结点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){}};//迭代器类template<class T, class Ref, class Ptr>struct __list_iterator{typedef list_node<T> Node;typedef __list_iterator<T, Ref, Ptr> iterator;typedef T value_type;typedef Ref reference;typedef Ptr pointer;//成员属性 _nodeNode* _node;//成员函数 //构造函数__list_iterator(Node* node): _node(node){}//解引用运算符重载Ref operator*(){return _node->_data;}//成员访问符重载Ptr operator->(){return &(operator*());//return &_node->_data;}//前置++iterator& operator++()   //__list_iterator<T, Ref, Ptr>& operator++() { } {_node = _node->_next;return *this;}//后置++iterator operator++(int) //__list_iterator<T, Ref, Ptr> operator++(int) { }{iterator tmp(*this);_node = _node->_next;return tmp;}//前置--iterator& operator--(){_node = _node->_prev;return *this;}//后置--iterator operator--(int){iterator tmp(*this);_node = _node->_prev;return tmp;}//关系运算符bool operator==(const iterator& it){return _node == it._node;}bool operator!=(const iterator& it){return _node != it._node;}};//class类--链表template<class T>class list{typedef list_node<T> Node;public:typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;typedef __reverse_iterator<iterator, T&, T*> riterator;typedef __reverse_iterator<const_iterator, const T&, const T*> const_riterator;//迭代器函数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);}//反向迭代器函数riterator rbegin(){return riterator(end());}riterator rend(){return riterator(begin());}const_riterator rbegin() const{return const_riterator(end());}const_riterator rend() const{return const_riterator(begin());}//无参构造函数list(){_head = new Node();_head->_next = _head;_head->_prev = _head;}//有参构造函数(初始化n个结点)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++;}}//清空链表数据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++);}}//析构函数~list(){clear();delete _head;_head = nullptr;}//拷贝构造/*list(const list<T>& lt){_head = new Node();_head->_next = _head;_head->_prev = _head;for (auto e : lt){push_back(e);}}*///拷贝构造pluslist(const list<T>& lt){_head = new Node();_head->_next = _head;_head->_prev = _head;list<T> tmp(lt.begin(), lt.end());swap(_head, tmp._head);}//赋值/*list<T>& operator=(list<T> lt){if (this != &lt){clear();for (auto e : lt){push_back(e);}}return *this;}*///赋值pluslist<T>& operator=(list<T> lt){swap(_head, lt._head);return *this;}//pos前插入void insert(iterator pos, const T& x){//prv new cur/pos nextNode* cur = pos._node;Node* prv = cur->_prev;Node* newnode = new Node(x);//prv连接newprv->_next = newnode;newnode->_prev = prv;//new连接curnewnode->_next = cur;cur->_prev = newnode;}//删除pos处数据iterator erase(iterator pos){assert(pos != end());//prv cur/pos nextNode* cur = pos._node;Node* prv = cur->_prev;Node* next = cur->_next;delete cur;//prv连接nextprv->_next = next;next->_prev = prv;return iterator(next);}// 尾插void push_back(const T& x){/*//创建新结点Node* newnode = new Node(x);//定位尾结点Node* tail = _head->_prev;//tail连接newtail->_next = newnode;newnode->_prev = tail;//new连接headnewnode->_next = _head;_head->_prev = newnode;*/insert(end(), x);}// 头插 void push_front(const T& x){insert(begin(), x);}//尾删void pop_back(){erase(--end());}//头删void pop_front(){erase(begin());}private:Node* _head;};/////打印链表(使用const迭代器)void print_list(const list<int>& lt){list<int>::const_iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";it++;}cout << endl;}// 无参构造  尾插  迭代器 void test_list1(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);//正向迭代器list<int>::iterator it = lt.begin();while (it != lt.end()){*it *= 2;cout << *it << " ";it++;}cout << endl;//反向迭代器list<int>::riterator rit = lt.rbegin();while (rit != lt.rend()){*rit *= 2;cout << *rit << " ";rit++;}cout << endl;}//打印函数void test_list2(){list<int> lt;lt.push_back(2);lt.push_back(4);lt.push_back(6);lt.push_back(8);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 test_list3(){list<Date> lt;lt.push_back(Date(2023, 7, 21));lt.push_back(Date(2023, 7, 22));lt.push_back(Date(2023, 7, 23));list<Date>::iterator it = lt.begin();while (it != lt.end()){cout << it->_year << "-" << it->_month << "-" << it->_day << endl;it++;}cout << endl;}//拷贝构造函数void test_list4(){list<int> lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);list<int> lt2(lt1);for (auto e : lt2)cout << e << " ";}//清空函数void test_list5(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);print_list(lt);lt.clear();print_list(lt);}
}

2.4 vector.h

#pragma once
#include <assert.h>
#include <iostream>
#include "riterator.h"
using namespace std;
namespace apex
{template<class T>//一、vector类class vector{public://迭代器 typedef T* iterator;typedef const T* const_iterator;typedef __reverse_iterator<iterator, T&, T*> riterator;typedef __reverse_iterator<const_iterator, const T&, const T*> const_riterator;//正向迭代器函数iterator begin(){return _start;}const_iterator begin() const{return _start;}iterator end(){return _finish;}const_iterator end() const{return _finish;}//正向迭代器函数riterator rbegin(){return riterator(end());}const_riterator rbegin() const{return const_riterator(end());}riterator rend(){return riterator(begin());}const_riterator rend() const{return  const_riterator(begin());}// 无参构造vector():_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){}// 有参构造//T()：匿名对象vector(size_t n, const T& val = T()):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){reserve(n);for (size_t i = 0; i < n; ++i){push_back(val);}}// 迭代器构造//为什么不直接用iterator？//iterator只能使用vector //再定义一个模板：可以使用多种类型的迭代器template <class InputIterator>vector(InputIterator first, InputIterator last):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){while (first != last){push_back(*first);++first;}}//拷贝构造传统写法1.0/*vector(const vector<T>& v){size_t sz = v.size();_start = new T[sz];//0.size capacity都行：拷贝内容即可 有可能不对拷贝对象操作//1.拷贝的空间是size        对拷贝对象操作  -- 扩容//2.拷贝的空间是capacity  不对拷贝对象操作  -- 空间浪费//memcpy(_start, v._start, sizeof(T) * sz); ==》无法解决vector<vector<int>>//以及下方reserve的问题 使用赋值 -- 自定义类型调用它们各自的赋值重载 -- 实现二层深拷贝for (size_t i = 0; i < sz; ++i){_start[i] = v._start[i];}_finish = _start + sz;_end_of_storage = _start + sz;}*///拷贝构造传统写法1.1/*vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){reserve(v.size());       //reserve开空间for (const auto& e : v)  //const：防止v被改变{push_back(e);}}*/// 拷贝构造高级写法void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){vector<T> tmp(v.begin(), v.end());//迭代器 -- push_back -- reserve -- 二层深拷贝swap(tmp);}// 赋值重载vector<T>& operator=(vector<T> v){swap(v);return *this;}//析构函数~vector(){delete[] _start;_start = _finish = _end_of_storage = nullptr;}//获取capacity的大小(vector没有此变量)size_t capacity() const{return _end_of_storage - _start;}//获取size的大小(vector没有此变量)size_t size() const{return _finish - _start;}// [] 重载T& operator[](size_t pos){assert(pos < size());return _start[pos];}const T& operator[](size_t pos) const{assert(pos < size());return _start[pos];}//扩容 -- 涉及到开新空间 -- 拷贝内容 -- 拷贝的可能是自定义类型void reserve(size_t n){if (n > capacity()){size_t sz = size();T* tmp = new T[n];if (_start != nullptr){//memcpy(tmp, _start, sizeof(T) * sz);for (size_t i = 0; i < sz; ++i){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + sz;_end_of_storage = _start + n;}}//扩容 + 初始化void resize(size_t n, const T& val = T()){//1. n > capacity         -- 扩容 + 初始化if (n > capacity()){reserve(n);}//2. size < n < capacity  -- 初始化if (n > size()){while (_finish < _start + n){*_finish = val;++_finish;         //finish移到新的"end"==>_start + n}}//3. n < size              -- 删除数据else{_finish = _start + n;  //直接更新finish即可}}//增加数据                                        （可修改）//const：匿名对象  隐式转换（临时变量【具有常性】）  左值 + 右值  void push_back(const T& x){/*if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = x;++_finish;*/insert(end(), x);}// pop_backvoid pop_back(){assert(_finish > _start);--_finish;}// insertiterator insert(iterator pos, const T& x){assert(pos >= _start && pos <= _finish);if (_finish == _end_of_storage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2); //扩容后 空间地址更新 pos仍指向原空间pos处//走下面的while时 访问pos --> errorpos = _start + len;                            //为防止pos失效 连带更新pos}// 挪动数据iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = x;++_finish;return pos;}// eraseiterator erase(iterator pos){assert(pos >= _start);assert(pos < _finish);iterator begin = pos + 1;while (begin < _finish){*(begin - 1) = *begin;++begin;}--_finish;if (size() < capacity() / 2){// 缩容 -- 以时间换空间//缩容--空间更新--pos失效--更新pos--只能解决形参作用域内的pos失效//当再次erase--访问pos ：error}return pos; // 删除数据之后 返回pos --> pos指向被删除的值 // 目标值被删除后 数据前移 pos指向空间不变 只不过pos指向的值是 目标值后的值}//frontT& front(){assert(size() > 0);return *_start;}//backT& back(){assert(size() > 0);return *(_finish - 1);}private:iterator _start;iterator _finish;iterator _end_of_storage;};
//二、命名空间内的函数// 增 删 [] size() 迭代器 范围forvoid test_vector1(){vector<int> v;//push_backv.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);// []  size()for (size_t i = 0; i < v.size(); ++i){cout << v[i] << " ";}cout << endl;//正向迭代器vector<int>::iterator it = v.begin();while (it != v.end()){cout << *it << " ";++it;}cout << endl;//反向迭代器vector<int>::riterator rit = v.rbegin();while (rit != v.rend()){cout << *rit << " ";++rit;}cout << endl;//pop_backv.pop_back();v.pop_back();//范围forfor (auto e : v){cout << e << " ";}cout << endl;}// 迭代器失效问题(1) -- insert(野指针问题)void test_vector2(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);for (auto e : v){cout << e << " ";}cout << endl;auto p = find(v.begin(), v.end(), 3);if (p != v.end()){v.insert(p, 30);//在p位置插入数据后不要访问p-->p可能失效：//插入需要扩容 扩容会更新空间地址 pos仍指向源空间的pos处 pos失效//即便改进了insert代码 更新了pos -->解决了insert中while循环内访问pos的问题 //但是形参改变不影响实参  在作用外pos仍失效 //为什么不使用引用？//v.insert(v.begin(), 1); -->//iterator begin()//{//	 return _start;//}//返回临时拷贝--具有常性--与引用可以修改的特性不匹配//那改成：const iterator& pos -->//内部无法对_start修改///** cout << *p << endl;v.insert(p, 40);*/}for (auto e : v){cout << e << " ";}cout << endl;}// erasevoid test_vector3(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);for (auto e : v){cout << e << " ";}cout << endl;auto p = find(v.begin(), v.end(), 3);if (p != v.end()){v.erase(p);}for (auto e : v){cout << e << " ";}cout << endl;v.erase(v.begin());for (auto e : v){cout << e << " ";}cout << endl;}// 迭代器失效问题(2) -- erase 删除所有的偶数 (迭代器位置问题)void test_vector4(){// 正常运行--lucky// 1 2 3 4 5 --> 1 3 5 -- it == end 循环结束vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);// 崩溃// 1 2 3 4 --> 1 4 -- end在4后一个 it在4后两个 it != end 循环无法结束v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);// 结果不对// 1 2 4 3 4 5 -- erase 2 --> 1 4 3 4 5  it再++ 直接跳过4v.push_back(1);v.push_back(2);v.push_back(4);v.push_back(3);v.push_back(4);v.push_back(5);auto it = v.begin();//错误/*while (it != v.end()){if (*it % 2 == 0){v.erase(it);}++it;}*///正确while (it != v.end()){if (*it % 2 == 0){it = v.erase(it); //it不在++ 而是停留在此处}else                  //是奇数才++{++it;}}for (auto e : v){cout << e << " ";}cout << endl;}// 迭代器失效问题(3) -- insert (扩容野指针 + 迭代器位置问题)void test_vector5(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);// 在所有偶数前插入该数2倍的值auto it = v.begin();while (it != v.end()){if (*it % 2 == 0){it = v.insert(it, *it * 2); //1.it重新赋值：插入大概率回扩容 一旦扩容 空间更新 it成为野指针//  insert函数返回新的指向原位置的迭代器 it重新赋值 成功解决问题//2.插入后不再 ++ ：使it停留在此处// 下面两次++是按题意 1 2 3 ——> 1 4 2 3 
// --> it指向4  ++两次指向3(即进行下一次寻找)++it;++it;}else{++it;}}for (auto e : v){cout << e << " ";}cout << endl;}// 迭代器失效问题(4) -- erase (缩容野指针 + 迭代器位置问题)/*待实现*///总结：迭代器失效问题 //1.扩容导致的野指针问题//2.插入或删除导致的迭代器位置错误问题//拷贝构造 void test_vector6(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);// 1 2 3 4 5for (auto e : v){cout << e << " ";}cout << endl;//拷贝构造vector<int> v1(v);v[0] *= 10;        //深拷贝// 10 2 3 4 5for (auto e : v){cout << e << " ";}cout << endl;// 1 2 3 4 5for (auto e : v1){cout << e << " ";}cout << endl;}//迭代器构造void test_vector7(){string s("hello world");vector<int> vs(s.begin(), s.end());for (auto e : vs){cout << e << " ";}cout << endl;vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);vs = v;               // 赋值重载：针对两个已经存在的对象vector<int> copy = v; // 拷贝构造 ==》copy(v); //copy不存在 用一个已有的对象去初始化一个新对象vs[0] *= 10;for (auto e : vs){cout << e << " ";}cout << endl;for (auto e : v){cout << e << " ";}cout << endl;}// 有参构造void test_vector8(){//C++引入了模板 ==》内置类型也可以有构造/*int i = 0;int j = int();int k = int(10);*///正常运行vector<int> v1(10);for (auto e : v1){cout << e << " ";}cout << endl;//正常运行vector<char> v3(10, 'a');for (auto e : v3){cout << e << " ";}cout << endl;// 编译错误：参数匹配//<int> v2(10, 1);//1.vector(size_t n, const T & val = T()) ;            //2.vector(InputIterator first, InputIterator last);//1.int-->u_int int-->T    匹配程度低//2.int-->T     int-->T 【有解引用操作】//修正1.0：vector<int> v2(10u, 1); //第一种匹配程度变高 -- ok//修正2.0：//vector(int n, const T & val = T()) ; for (auto e : v2){cout << e << " ";}cout << endl;}// resizevoid test_vector9(){vector<int> v1;v1.resize(10, 0);for (auto e : v1){cout << e << " ";}cout << endl;vector<int> v2;v2.reserve(10);v2.push_back(1);v2.push_back(2);v2.push_back(3);v2.push_back(4);v2.push_back(5);v2.resize(8, 8);for (auto e : v2){cout << e << " ";}cout << endl;v2.resize(20, 20);for (auto e : v2){cout << e << " ";}cout << endl;v2.resize(3);for (auto e : v2){cout << e << " ";}cout << endl;}//vv的深拷贝天坑void test_vector10(){class Solution{public:vector<vector<int>> generate(int n){vector<vector<int>> Vv;Vv.resize(n);for (size_t i = 0; i < Vv.size(); ++i){Vv[i].resize(i + 1, 0);Vv[i].front() = Vv[i].back() = 1;}for (size_t i = 0; i < Vv.size(); ++i){for (size_t j = 0; j < Vv[i].size(); ++j){if (Vv[i][j] == 0){Vv[i][j] = Vv[i - 1][j] + Vv[i - 1][j - 1];}}}//打印查看for (size_t i = 0; i < Vv.size(); ++i){for (size_t j = 0; j < Vv[i].size(); ++j){cout << Vv[i][j] << " ";}cout << endl;}return Vv;}};vector<vector<int>> ret = Solution().generate(5);}
}

2.5test.cpp

#define _CRT_SECURE_NO_WARNINGS 
#include <iostream>
#include <list>
#include <vector>
#include <algorithm>
#include <array>
#include <time.h>
#include <queue>
using namespace std;#include "list.h"
#include "vector.h"int main()
{apex::test_vector1();return 0;
}

3.反向迭代器的应用

1.使用要求

该容器要能够实现++、–操作，如单向链表或单向map不可使用。

2.迭代器的分类

单向迭代器forward_iterator_tag：支持++：forward_list、unordered_map、unordered_set、
双向迭代器bidirectional_iterator_tag：支持++ --:list 、map、set、
随机迭代器random_access_iterator_tag：支持++ – + -：deque、vector
只读迭代器
只写迭代器