1. priority_queue的模拟实现

1.1 未完全的priority_queue

1.2 迭代器区间构造和无参构造

1.3 仿函数的介绍和使用

1.4 完整priority_queue代码：

1.5 相关笔试选择题

答案：

2. 反向迭代器

2.1 反向迭代器的普通实现

reverse_iterator.h（不对称版）

2.2 反向迭代器的对称实现

reverse_iterator.h

list.h ：

vector.h

3. 迭代器的功能分类

本章完。

1. priority_queue的模拟实现

默认情况下的priority_queue是大堆，我们先不考虑用仿函数去实现兼容大堆小队排列问题，

我们先去实现大堆，先把基本的功能实现好，带着讲解完仿函数后再去进行优化实现。

优先级队列相较于普通的队列，其区别主要是在 push 和 pop 上，

即需要在插入 / 删除数据的同时，增添调整的功能，其也是对适配器的封装，

push 和 pop 需要上调和下调操作，我们不可避免地需要实现上调和下调的算法。

我们这里暂时写死，设计成大堆的 adjust_up 和 adjust_down：

对调整算法不熟悉的可以看这里；

数据结构与算法⑪(第四章_中)堆的分步构建_GR C的博客-CSDN博客

1.1 未完全的priority_queue

入队时将数据插入后，从最后一个元素开始进行上调。

出队时采用堆的删除手法，将根元素（即队头）和最后一个元素进行交换，并调用尾删掉队头。

既然用了头尾交换法，我们就不得不对队列重新调整，所以从根位置进行下调，即可完成出队。

除了插入和删除，其它接口和queue差不多，PriorityQueue.h:

#pragma once
#include <iostream>
#include <vector> 
#include <algorithm>
#include <functional> // greater和less的头文件
using namespace std;namespace rtx
{template<class T, class Container = vector<T>>class priority_queue{public:void push(const T& x){_con.push_back(x);adjust_up(_con.size() - 1);}void adjust_up(size_t child){size_t father = (child - 1) / 2;while (child > 0){if (_con[father] < _con[child]){swap(_con[father], _con[child]);child = father;// 交换后向上走father = (child - 1) / 2;}else{break;}}}void pop(){std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}void adjust_down(size_t father){size_t child = father * 2 + 1;// 默认左孩子大while (child < _con.size()){if (child + 1 < _con.size() && _con[child] < _con[child + 1])//先考虑右孩子是否存在{child += 1;}if (_con[child] > _con[father]){swap(_con[child], _con[father]);father = child;child = father * 2 + 1;}else{break;}}}const T& top(){return _con[0];}bool empty()  const{return _con.empty();}size_t size() const{return _con.size();}private:Container _con;};
}

测试一下，Test.c:

#include "PriorityQueue.h"void test_priority_queue()
{rtx::priority_queue<int> pq;pq.push(3);pq.push(1);pq.push(2);pq.push(5);pq.push(0);pq.push(8);pq.push(1);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}cout << endl;
}int main()
{test_priority_queue();return 0;
}

1.2 迭代器区间构造和无参构造

我们前面没写无参构造代码也跑出来了，先写下迭代器区间构造，和以前一样;

但这里不要直接push，push的时间是O（N*logN），建堆的时间是logN：

		template<class InputIterator>priority_queue(InputIterator first, InputIterator last):_con(first,last) // 初始化列表初始化代替下面被注释的{//while (first != last)//{//	_con.push_back(*first);//	++first;//}for (int i = (_con.size() - 1 - 1) / 2;i >= 0;--i){adjust_down(i);}}

这样的话运行代码就发现前面的无参构造报错了：没有默认的构造函数使用。

所以我们还要写上无参构造，但实际里面什么都不用写:

		priority_queue(){}

测试一下，Test.c:

#include "PriorityQueue.h"void test_priority_queue()
{rtx::priority_queue<int> pq;pq.push(3);pq.push(1);pq.push(2);pq.push(5);pq.push(0);pq.push(8);pq.push(1);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}cout << endl;int arr[] = { 0,3,2,1,6,5,4,9,8,7 };rtx::priority_queue<int> heap(arr, arr + sizeof(arr) / sizeof(arr[0]));while (!heap.empty()){cout << heap.top() << " ";heap.pop();}cout << endl;
}int main()
{test_priority_queue();return 0;
}

我们写死的最大问题是 —— 如果想按升序排列，就没办法排了。

我们这里写的用来排降序的大堆，如果想排升序我们需要写小堆，

C++ 在这里有一种叫仿函数的东西，可以控制这些东西，我们下面先来介绍一下仿函数。

1.3 仿函数的介绍和使用

概念：使一个类的使用看上去像一个函数。可以像函数一样使用的对象，称为函数对象。

其实现就是在类中重载 operator()，使得该类具备类似函数的行为，就是一个仿函数类了。

C语言优先级，() 圆括号使用形式为表达式或 "作为函数形参列表的括号"

写一个最简单的仿函数：

#include<iostream>
using namespace std;namespace rtx
{struct less{bool operator()(const int& left, const int& right) const{return left < right;}};
}int main()
{int a = 10, b = 20;rtx::less lessCmp;cout << lessCmp(a, b) << endl;return 0;
}

仿函数（函数对象）—— 对象可以像调用函数一样去使用

我们还可以使其能够支持泛型，我们加一个 template 模板，加一个 greater 仿函数：

#include<iostream>
using namespace std;namespace rtx
{template<class T>struct less{bool operator()(const T& left, const T& right) const{return left < right;}};template<class T>struct greater{bool operator()(const T& left, const T& right) const{return left > right;}};
}int main()
{int a = 10, b = 20;rtx::less<int> lessCmp;cout << lessCmp(a, b) << endl;rtx::greater<int> gtCmp;cout << gtCmp(a, b) << endl;return 0;
}

一个对象能像函数一样用，看上去很神奇，实际上调用的只是我们重载的 operator() 而已。

我们在C阶段不是学过函数指针么，用函数指针不行吗？

函数指针确实可以做到这些功能。但是在这里函数指针跟仿函数比，一点都方便。

在 C++ 里其实是非常不喜欢使用函数指针的，函数的指针在一些地方用起来非常复杂。

所以巨佬才发明了仿函数等，代替函数指针。

1.4 完整priority_queue代码：

我们现在用仿函数去比较那些数据(在模板再加一个参数)，这样就不会写死了。

直接用库的less，PriorityQueue.h:

#pragma once
#include <iostream>
#include <vector> 
#include <algorithm>
#include <functional> // greater和less的头文件
using namespace std;namespace rtx
{// Compare进行比较的仿函数 less->大堆// Compare进行比较的仿函数 greater->小堆template<class T, class Container = vector<T>,class Compare = less<T>>class priority_queue{public:priority_queue(){}template<class InputIterator>priority_queue(InputIterator first, InputIterator last):_con(first,last) // 初始化列表初始化代替下面被注释的{//while (first != last)//{//	_con.push_back(*first);//	++first;//}for (int i = (_con.size() - 1 - 1) / 2;i >= 0;--i){adjust_down(i);}}void push(const T& x){_con.push_back(x);adjust_up(_con.size() - 1);}void adjust_up(size_t child){Compare cmp;size_t father = (child - 1) / 2;while (child > 0){//if (_con[father] < _con[child])if (cmp(_con[father], _con[child]))//仿函数想函数一样使用{swap(_con[father], _con[child]);child = father;// 交换后向上走father = (child - 1) / 2;}else{break;}}}void pop(){std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}void adjust_down(size_t father){Compare cmp;size_t child = father * 2 + 1;// 默认左孩子大while (child < _con.size()){//if (child + 1 < _con.size() && _con[child] < _con[child + 1])if (child + 1 < _con.size() && cmp(_con[child], _con[child + 1]))//先考虑右孩子是否存在{child += 1;}//if (_con[child] > _con[father]) 这里写了大于，所以是不好的(下次一定)if (cmp(_con[father], _con[child])){swap(_con[child], _con[father]);father = child;child = father * 2 + 1;}else{break;}}}const T& top(){return _con[0];}bool empty()  const{return _con.empty();}size_t size() const{return _con.size();}private:Container _con;};
}

测试，直接传greater<int> 建个小堆康康：

#include "PriorityQueue.h"void test_priority_queue()
{rtx::priority_queue<int,vector<int>, greater<int>> pq;pq.push(3);pq.push(1);pq.push(2);pq.push(5);pq.push(0);pq.push(8);pq.push(1);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}cout << endl;int arr[] = { 0,3,2,1,6,5,4,9,8,7 };rtx::priority_queue<int, vector<int>, greater<int>> heap(arr, arr + sizeof(arr) / sizeof(arr[0]));while (!heap.empty()){cout << heap.top() << " ";heap.pop();}cout << endl;
}int main()
{test_priority_queue();return 0;
}

值得一提的是我们这里传的是类型，因为是类模板，

sort里传的是对象（用匿名对象就好），是函数模板：

1.5 相关笔试选择题

1. STL中的priority_queue使用的底层数据结构是什么( )

A.queue

B.heap

C.deque

D.vector

2. 下列代码的运行结果是（）

int main()
{priority_queue<int> a;priority_queue<int, vector<int>, greater<int> > c;priority_queue<string> b;for (int i = 0; i < 5; i++){a.push(i);c.push(i);}while (!a.empty()){cout << a.top() << ' ';a.pop();}cout << endl;while (!c.empty()){cout << c.top() << ' ';c.pop();}cout << endl;b.push("abc");b.push("abcd");b.push("cbd");while (!b.empty()){cout << b.top() << ' ';b.pop();}cout << endl;return 0;
}

A.4 3 2 1 0 0 1 2 3 4 cbd abcd abc

B.0 1 2 3 4 0 1 2 3 4 cbd abcd abc

C.4 3 2 1 0 4 3 2 1 0 abc abcd cbd

D.0 1 2 3 4 4 3 2 1 0 cbd abcd abc

3. 以下说法正确的是( )

A.deque的存储空间为连续空间

B.list迭代器支持随机访问

C.如果需要高效的随机存取，还要大量的首尾的插入删除则建议使用deque

D.vector容量满时，那么插入元素时只需增加当前元素个数的内存即可

4. 仿函数比起一般函数具有很多优点，以下描述错误的是( )

A.在同一时间里，由某个仿函数所代表的单一函数，可能有不同的状态

B.仿函数即使定义相同，也可能有不同的类型

C.仿函数通常比一般函数速度快

D.仿函数使程序代码变简单

5. 假设cont是一个Container 的示例，里面包含数个元素，那么当CONTAINER为：

1.vector 2.list 3.deque 会导致下面的代码片段崩溃的Container 类型是（）

int main()
{Container cont = { 1, 2, 3, 4, 5 };Container::iterator iter, tempIt;for (iter = cont.begin(); iter != cont.end();){tempIt = iter;++iter;cont.erase(tempIt);}
}

A.1, 2

B.2, 3

C.1, 3

D.1, 2, 3

答案：

1. D

分析:优先级队列priority_queue底层采用vector容器作为底层数据结构

2. A

分析:优先级队列默认情况为：大堆，这是解题的关键

priority_queue<int> a; //a是大堆

priority_queue<int, vector<int>, greater<int> > c; //c指定了比较规则，是小堆

priority_queue<string> b; //b是大堆

因此分别建堆的过程是建立a大堆，c小堆，b大堆

所以出队的顺序就按照其优先级大小出队

3. C

A.deque底层总体为不连续空间

B.不支持，因为底层是一个个的不连续节点

C.正确

D.一般会以容量的2倍扩充容量，这是为了减少扩容的次数，减少内存碎片

4. C

A.仿函数是模板函数，可以根据不同的类型代表不同的状态

B.仿函数是模板函数，可以有不同类型

C.仿函数是模板函数，其速度比一般函数要慢,故错误

D.仿函数在一定程度上使代码更通用，本质上简化了代码

5. C

分析：此题主要考察cont.erase(tmpit)删除数据之后，迭代器失效相关问题

本题重点要关注的是底层实现

vector、deque底层都是用了连续空间，所以虽然++iter迭代器了，但是erase(tempit)以后

底层是连续空间，删除会挪动数据，最终导致iter意义变了，已失效了。

而list，不是连续空间，删除以后tempIt虽然失效了，但是不影响iter。

2. 反向迭代器

（此篇文章两万多字，可以在这分两部分看了）

前面讲 list 我们没实现反向迭代器，计划放在这里讲，反向迭代器怎么实现呢，

反向迭代器和正向迭代器加加的方向不一样（唯一区别）。

（即正向迭代器 ++ 是向后走，反向迭代器 ++ 是向前走）

正常思维是把正向迭代器复制粘贴一份，把 ++ 改成 -- 啥的，

前面讲了容器适配器，大佬就实现了一个迭代器适配器：

库里的反向迭代器其实就是对正向迭代器的一种封装 —— 适配器模式（配接器模式）。

用传过来的正向迭代器实现反向迭代器，直接建一个reverse_iterator.h，

2.1 反向迭代器的普通实现

如果知道反向迭代器其实就是对正向迭代器的一种封装，因为以前认为rbegin（）指向的是

最后一个数据，rend（）指向的是第一个数据的前一个（哨兵位头结点）（库里面不是的）

所以现在普通思路实现出来是这样的：（虽然库里面不是的，但也可以实现出来）

reverse_iterator.h（不对称版）

#pragma oncenamespace rtx
{template<class Iterator, class Ref, class Ptr>// 为了适配const迭代器，再加两个参数struct __reverse_iterator  //普通迭代器传的就是 T& 和 T*  const 迭代器传的就是 const T& 和 const T* {Iterator _cur;typedef __reverse_iterator<Iterator, Ref, Ptr> RIterator;__reverse_iterator(Iterator it):_cur(it){}RIterator operator++(){--_cur; // 正向迭代器 ++ 就是反向迭代器 --return *this;}RIterator operator--(){++_cur;return *this;}Ref operator*(){return *_cur;}Ptr operator->(){//return _cur.operator->();//return &(*_cur); // 如果这样写，对称的时候就要改了return &(operator*());}bool operator!=(const RIterator& it){return _cur != it._cur;}};
}

如果你 vector 需要反向迭代器，那就把 vector 的正向迭代器传给 Iterator，

它就可以通过正向迭代器转换出 vector 的反向迭代器。

也就是说，我们实现的反向迭代器并包装的这个类，不是针对某个容器而是针对所有容器的。

任何一个容器只要你实现了正向迭代器，就可以通过其适配出反向迭代器。

先拿list.h 试一下，包一下头文件"reverse_iterator.h"，在以前实现的 list类加上了下面的代码：

		typedef __reverse_iterator<iterator, T&, T*> reverse_iterator; // 传正向迭代器封装出反向迭代器typedef __reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;reverse_iterator rbegin()//按照以前的理解，rbegin指向最后一个数据{//return reverse_iterator(_head->_prev);return reverse_iterator(--end());}reverse_iterator rend()//按照以前的理解，rend指向第一个数据前一个（哨兵位）{//return reverse_iterator(_head);return reverse_iterator(end());}const_reverse_iterator rbegin() const{//return const_reverse_iterator(_head->_prev);return const_reverse_iterator(--end());}const_reverse_iterator rend() const{//return const_reverse_iterator(_head);return const_reverse_iterator(end());}

现在的 list.h 就是这样的：

#pragma once#include<iostream>
#include<assert.h>
#include "reverse_iterator.h"
using namespace std;namespace rtx
{template<class T>struct list_node // 定义结点{T _data;list_node* _prev;list_node* _next;list_node(const T& x = T()):_data(x),_prev(nullptr),_next(nullptr){}};template<class T, class Ref, class Ptr>struct __list_iterator // 定义迭代器{typedef list_node<T> Node;typedef __list_iterator<T, Ref, Ptr> iterator;// 在list类里面：// typedef __list_iterator<T, T&, T*>             iterator;// typedef __list_iterator<T, const T&, const T*> const_iterator;Node* _node;__list_iterator(Node* node):_node(node){}bool operator!=(const iterator& it){return _node != it._node;}//T& operator*()Ref operator*(){return _node->_data;  // 返回结点的数据}//T* operator->()Ptr operator->(){return &(operator*());//即 return &(_node->_data);}iterator& operator++(){_node = _node->_next;return *this; // 返回加加后的值}iterator operator++(int){iterator tmp(*this); // 拷贝构造一个tmp存储原来的值_node = _node->_next;return tmp; // 返回加加前的值}iterator& operator--(){_node = _node->_prev;return *this; // 返回减减后的值}iterator operator--(int){iterator tmp(*this); // 拷贝构造一个tmp存储原来的值_node = _node->prev;return tmp; // 返回减减前的值}};template<class T>class list // 定义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*> reverse_iterator; // 传正向迭代器封装出反向迭代器typedef __reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;const_iterator begin() const{return const_iterator(_head->_next);}const_iterator end() const{return const_iterator(_head);}iterator begin()// begin是实际数据的第一个，_head 是哨兵位头结点{return iterator(_head->_next);}iterator end()// end是实际数据的下一个{return iterator(_head);}reverse_iterator rbegin()//按照以前的理解，rbegin指向最后一个数据{//return reverse_iterator(_head->_prev);return reverse_iterator(--end());}reverse_iterator rend()//按照以前的理解，rend指向第一个数据前一个（哨兵位）{//return reverse_iterator(_head);return reverse_iterator(end());}const_reverse_iterator rbegin() const{//return const_reverse_iterator(_head->_prev);return const_reverse_iterator(--end());}const_reverse_iterator rend() const{//return const_reverse_iterator(_head);return const_reverse_iterator(end());}void empty_init()// 创建并初始化哨兵位头结点（即构造函数）{_head = new Node;_head->_next = _head;_head->_prev = _head;}template <class InputIterator>list(InputIterator first, InputIterator last){empty_init();while (first != last){push_back(*first);++first;}}list(){empty_init();}void swap(list<T>& x)//提一嘴：void swap(list& x)也行（类里面可以省略<T>，类外不行>{std::swap(_head, x._head); // 换哨兵位头结点就行}list(const list<T>& lt)//lt2(lt1){empty_init();list<T> tmp(lt.begin(), lt.end()); // 迭代器区间构造一个(lt1)swap(tmp); // 直接和lt2换哨兵位头结点}list<T>& operator=(list<T> lt)//lt3 = lt1 这里lt1直接深拷贝给lt，lt是局部对象，出来作用域直接调析构{swap(lt);// 把深拷贝出来的lt和lt3交换return *this; // 把lt3返回}~list(){clear();delete _head;_head = nullptr;}void clear(){iterator it = begin();while (it != end()){it = erase(it); // 返回删除位置的下一个结点}}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);}void push_back(const T& x){//Node* tail = _head->_prev;//Node* NewNode = new Node(x);思路图：head        tail  NewNode//tail->_next = NewNode;//NewNode->_prev = tail;//_head->_prev = NewNode;//NewNode->_next = _head;insert(end(), x);}void push_front(const T& x){insert(begin(), x);}iterator erase(iterator pos){assert(pos != end());Node* cur = pos._node; // 删curNode* prev = cur->_prev;prev->_next = cur->_next; // cur前一个指向cur后一个cur->_next->_prev = prev; // cur后一个指回cur前一个delete cur;return iterator(prev->_next); // 返回删除位置下一个}void pop_back(){erase(begin());}void pop_front(){erase(--end());}private:Node* _head; // 哨兵位头结点};
}

测试一下：

#define _CRT_SECURE_NO_WARNINGS 1#include "list.h"namespace rtx
{void Test_reverse_iterator(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);list<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;list<int>::reverse_iterator rit = lt.rbegin();while (rit != lt.rend()){cout << *rit << " ";++rit;}cout << endl;}
}int main()
{rtx::Test_reverse_iterator();return 0;
}

这样实现也行，但是rbegin（）和rend（）就没那么美观，

所以巨佬就设计了下面的艺术行为：（也只是为了对称，没别的）

2.2 反向迭代器的对称实现

前面说到，我们认为应该是这样的：

但是库里面是这样实现的：

rbegin 和 rend 是和 end 和 begin 是相对称的形式设计的，

你的 end 就是我的 rbegin，你的 begin 就是我的 rend。

如果这样实现的话，对rbegin解引用就不对了，

我们先看看库里反向迭代器的解引用：

这样取的就是前一个位置了，rbegin() 位置的前一个位置正是想要取的地方。

来改一下，解引用应该是这样的：

		Ref operator*(){//return *_cur;auto tmp = _cur;--tmp;return *tmp;}

还有那四个接口改成这样：

		reverse_iterator rbegin()// 对称实现{//return reverse_iterator(_head->_prev);//return reverse_iterator(--end());return reverse_iterator(end());}reverse_iterator rend(){//return reverse_iterator(_head);//return reverse_iterator(end());return reverse_iterator(begin());}const_reverse_iterator rbegin() const{//return const_reverse_iterator(_head->_prev);return const_reverse_iterator(end());}const_reverse_iterator rend() const{//return const_reverse_iterator(_head);return const_reverse_iterator(begin());}

reverse_iterator.h

#pragma oncenamespace rtx
{template<class Iterator, class Ref, class Ptr>// 为了适配const迭代器，再加两个参数struct __reverse_iterator  //普通迭代器传的就是 T& 和 T*  const 迭代器传的就是 const T& 和 const T* {Iterator _cur;typedef __reverse_iterator<Iterator, Ref, Ptr> RIterator;__reverse_iterator(Iterator it):_cur(it){}RIterator operator++(){--_cur; // 正向迭代器 ++ 就是反向迭代器 --return *this;}RIterator operator--(){++_cur;return *this;}Ref operator*(){//return *_cur;auto tmp = _cur;--tmp;return *tmp;}Ptr operator->(){//return _cur.operator->();//return &(*_cur); // 如果这样写，对称的时候就要改了return &(operator*());}bool operator!=(const RIterator& it){return _cur != it._cur;}};
}

list.h ：

#pragma once#include<iostream>
#include<assert.h>
#include "reverse_iterator.h"
using namespace std;namespace rtx
{template<class T>struct list_node // 定义结点{T _data;list_node* _prev;list_node* _next;list_node(const T& x = T()):_data(x),_prev(nullptr),_next(nullptr){}};template<class T, class Ref, class Ptr>struct __list_iterator // 定义迭代器{typedef list_node<T> Node;typedef __list_iterator<T, Ref, Ptr> iterator;// 在list类里面：// typedef __list_iterator<T, T&, T*>             iterator;// typedef __list_iterator<T, const T&, const T*> const_iterator;Node* _node;__list_iterator(Node* node):_node(node){}bool operator!=(const iterator& it){return _node != it._node;}//T& operator*()Ref operator*(){return _node->_data;  // 返回结点的数据}//T* operator->()Ptr operator->(){return &(operator*());//即 return &(_node->_data);}iterator& operator++(){_node = _node->_next;return *this; // 返回加加后的值}iterator operator++(int){iterator tmp(*this); // 拷贝构造一个tmp存储原来的值_node = _node->_next;return tmp; // 返回加加前的值}iterator& operator--(){_node = _node->_prev;return *this; // 返回减减后的值}iterator operator--(int){iterator tmp(*this); // 拷贝构造一个tmp存储原来的值_node = _node->prev;return tmp; // 返回减减前的值}};template<class T>class list // 定义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*> reverse_iterator; // 传正向迭代器封装出反向迭代器typedef __reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;const_iterator begin() const{return const_iterator(_head->_next);}const_iterator end() const{return const_iterator(_head);}iterator begin()// begin是实际数据的第一个，_head 是哨兵位头结点{return iterator(_head->_next);}iterator end()// end是实际数据的下一个{return iterator(_head);}//reverse_iterator rbegin()//按照以前的理解，rbegin指向最后一个数据//{//	//return reverse_iterator(_head->_prev);//	return reverse_iterator(--end());//}//reverse_iterator rend()//按照以前的理解，rend指向第一个数据前一个（哨兵位）//{//	//return reverse_iterator(_head);//	return reverse_iterator(end());//}//const_reverse_iterator rbegin() const//{//	//return const_reverse_iterator(_head->_prev);//	return const_reverse_iterator(--end());//}//const_reverse_iterator rend() const//{//	//return const_reverse_iterator(_head);//	return const_reverse_iterator(end());//}reverse_iterator rbegin()// 对称实现{//return reverse_iterator(_head->_prev);//return reverse_iterator(--end());return reverse_iterator(end());}reverse_iterator rend(){//return reverse_iterator(_head);//return reverse_iterator(end());return reverse_iterator(begin());}const_reverse_iterator rbegin() const{//return const_reverse_iterator(_head->_prev);return const_reverse_iterator(end());}const_reverse_iterator rend() const{//return const_reverse_iterator(_head);return const_reverse_iterator(begin());}void empty_init()// 创建并初始化哨兵位头结点（即构造函数）{_head = new Node;_head->_next = _head;_head->_prev = _head;}template <class InputIterator>list(InputIterator first, InputIterator last){empty_init();while (first != last){push_back(*first);++first;}}list(){empty_init();}void swap(list<T>& x)//提一嘴：void swap(list& x)也行（类里面可以省略<T>，类外不行>{std::swap(_head, x._head); // 换哨兵位头结点就行}list(const list<T>& lt)//lt2(lt1){empty_init();list<T> tmp(lt.begin(), lt.end()); // 迭代器区间构造一个(lt1)swap(tmp); // 直接和lt2换哨兵位头结点}list<T>& operator=(list<T> lt)//lt3 = lt1 这里lt1直接深拷贝给lt，lt是局部对象，出来作用域直接调析构{swap(lt);// 把深拷贝出来的lt和lt3交换return *this; // 把lt3返回}~list(){clear();delete _head;_head = nullptr;}void clear(){iterator it = begin();while (it != end()){it = erase(it); // 返回删除位置的下一个结点}}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);}void push_back(const T& x){//Node* tail = _head->_prev;//Node* NewNode = new Node(x);思路图：head        tail  NewNode//tail->_next = NewNode;//NewNode->_prev = tail;//_head->_prev = NewNode;//NewNode->_next = _head;insert(end(), x);}void push_front(const T& x){insert(begin(), x);}iterator erase(iterator pos){assert(pos != end());Node* cur = pos._node; // 删curNode* prev = cur->_prev;prev->_next = cur->_next; // cur前一个指向cur后一个cur->_next->_prev = prev; // cur后一个指回cur前一个delete cur;return iterator(prev->_next); // 返回删除位置下一个}void pop_back(){erase(begin());}void pop_front(){erase(--end());}private:Node* _head; // 哨兵位头结点};
}

Test.cpp：（写到这忽然发现以前的Test.cpp都习惯写成Test.c 了，懂就刑）

#define _CRT_SECURE_NO_WARNINGS 1#include "list.h"namespace rtx
{void Test_reverse_iterator(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);list<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;list<int>::reverse_iterator rit = lt.rbegin();while (rit != lt.rend()){cout << *rit << " ";++rit;}cout << endl;}
}int main()
{rtx::Test_reverse_iterator();return 0;
}

以后为了和库里面的类似，所以还是艺术地实现对称的反向迭代器好。

写到这可能还不知道我们实现的反向迭代器有多强（只要提供一个正向迭代器就行）

我们试试把 vector 的弄出来，在vector.h里 #include "reverse_iterator.h"

和上面一样只需在vector类里面加上下面的代码：

一模一样，你甚至可以一步复制粘贴，位置也不改了：

		typedef __reverse_iterator<iterator, T&, T*> reverse_iterator; // 传正向迭代器封装出反向迭代器typedef __reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;reverse_iterator rbegin()// 对称实现{//return reverse_iterator(_head->_prev);//return reverse_iterator(--end());return reverse_iterator(end());}reverse_iterator rend(){//return reverse_iterator(_head);//return reverse_iterator(end());return reverse_iterator(begin());}const_reverse_iterator rbegin() const{//return const_reverse_iterator(_head->_prev);return const_reverse_iterator(end());}const_reverse_iterator rend() const{//return const_reverse_iterator(_head);return const_reverse_iterator(begin());}

所以vector.h就是这样的：

vector.h

#pragma once#include<iostream>
#include<assert.h>
#include<string>
#include "reverse_iterator.h"
using namespace std;namespace rtx
{template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;typedef __reverse_iterator<iterator, T&, T*> reverse_iterator; // 传正向迭代器封装出反向迭代器typedef __reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;reverse_iterator rbegin()// 对称实现{//return reverse_iterator(_head->_prev);//return reverse_iterator(--end());return reverse_iterator(end());}reverse_iterator rend(){//return reverse_iterator(_head);//return reverse_iterator(end());return reverse_iterator(begin());}const_reverse_iterator rbegin() const{//return const_reverse_iterator(_head->_prev);return const_reverse_iterator(end());}const_reverse_iterator rend() const{//return const_reverse_iterator(_head);return const_reverse_iterator(begin());}vector():_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){}~vector(){delete[] _start;_start = _finish = _end_of_storage = nullptr;}size_t size() const{return _finish - _start;}size_t capacity() const{return _end_of_storage - _start;}void push_back(const T& x){//if (_finish == _end_of_storage)//{//	reserve(capacity() == 0 ? 4 : capacity() * 2);//}//*_finish = x;//++_finish;insert(end(), x);}void reserve(size_t n){if (n > capacity()){size_t sz = size();T* tmp = new T[n];if (_start){//memcpy(tmp, _start, sizeof(T) * sz); //浅拷贝，不行for (size_t i = 0; i < sz; i++)// 如果T是int，一个一个拷贝没问题{tmp[i] = _start[i];// 如果T是string等自定义问题，一个一个拷贝调用的是T的深拷贝，也不会出问题。}delete[] _start;}_start = tmp;_finish = tmp + sz;_end_of_storage = tmp + n;}}T& operator[](size_t pos){assert(pos < size());return *(_start + pos);}const T& operator[](size_t pos) const{assert(pos < size());return *(_start + pos);}iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}template<class InputInterator>vector(InputInterator first, InputInterator last):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){while (first != last){push_back(*first);++first;}}void resize(size_t n, const T& val = T()){if (n > capacity()){reserve(n);}if (n > size()){while (_finish != _start + n){*_finish = val;++_finish;}}else{_finish = _start + n;}}void pop_back(){assert(_finish > _start);--_finish;}iterator insert(iterator pos, const T& val){assert(pos >= _start);// ①检查pos是否越界assert(pos <= _finish);if (_finish == _end_of_storage)// ②检查是否需要扩容{size_t len = pos - _start;// 记录一下pos到_start的距离reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;// 迭代器失效问题，扩容后pos还是指向原来的空间，更新一下pos，//而且形参不会影响实参，传引用的话begin等就传不了，所以用返回解决}iterator right = _finish - 1;// ③移动数据while (right >= pos){*(right + 1) = *right;--right;}*pos = val;// ④插入数据++_finish;return pos;}iterator erase(iterator pos){assert(pos >= _start);assert(pos < _finish);// 不能<= 因为_finish指向的是最后一个数据的下一个iterator left = pos + 1;while (left < _finish){*(left - 1) = *left;++left;}--_finish;return pos;//此时pos就是删除位置下一个位置迭代器}//vector(const vector<T>& v)// 传统写法//{//	reserve(v.capacity());//	// memcpy(_start, v._start, v.size() * sizeof(T));  // 会翻车//	for (const auto& e : 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());swap(tmp);}vector<T>& operator=(vector<T> v)// 现代写法{swap(v);return *this;}private:iterator _start;iterator _finish;iterator _end_of_storage;};
}

Test.cpp

#define _CRT_SECURE_NO_WARNINGS 1#include "list.h"
#include "vector.h"namespace rtx
{void Test_reverse_iterator(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);list<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;list<int>::reverse_iterator rit = lt.rbegin();while (rit != lt.rend()){cout << *rit << " ";++rit;}cout << endl;}void Test_reverse_iterator2(){vector<int> lt;//为了方便lt的名字都不改成常用的v了lt.push_back(10);lt.push_back(20);lt.push_back(30);lt.push_back(40);lt.push_back(50);vector<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;vector<int>::reverse_iterator rit = lt.rbegin();while (rit != lt.rend()){cout << *rit << " ";++rit;}cout << endl;}
}int main()
{//rtx::Test_reverse_iterator();rtx::Test_reverse_iterator2();return 0;
}