成都教育网站建设公司价格,河北建设工程招标投标协会网站,网站建设 提成,苏州最新新闻事件今天文章目录一、什么是反向迭代器二、STL 源码中反向迭代器的实现三、reverse_iterator 的模拟实现四、vector 和 list 反向迭代器的实现一、什么是反向迭代器
C 中一共有四种迭代器 – iterator、const_iterator、reverse_iterator 以及 const_reverse_iterator#xff0c;其中…
文章目录一、什么是反向迭代器二、STL 源码中反向迭代器的实现三、reverse_iterator 的模拟实现四、vector 和 list 反向迭代器的实现一、什么是反向迭代器
C 中一共有四种迭代器 – iterator、const_iterator、reverse_iterator 以及 const_reverse_iterator其中正向迭代器我们已经很熟悉了其实反向迭代器的使用和正向迭代器几乎一样反向迭代器的特点如下 rbegin() 相当于 end()rend() 相当于 begin()反向迭代器相当于正向迭代器–其他操作比如 * ! - 和正向迭代器相同。 反向迭代器的使用反向迭代器的使用和正向迭代器完全相同
void reverse_iterator_test() {vectorint v;v.push_back(1);v.push_back(5);v.push_back(6);v.push_back(5);v.push_back(9);vectorint::reverse_iterator rit v.rbegin();while (rit ! v.rend()) {(*rit) 1;cout *rit ;rit;}cout endl;
}在以前 string、vector 和 list 中模拟实现中我们只实现了正向迭代器而并没有去实现反向迭代器今天我们就来探究如何实现反向迭代器。 二、STL 源码中反向迭代器的实现
我们可以通过参考 STL 源码中反向迭代器的实现方式来学习如何实现反向迭代器如下
//list.h部分源码 -- SGI版
template class T, class Alloc alloc
class list {
public:typedef __list_iteratorT, T, T* iterator;typedef __list_iteratorT, const T, const T* const_iterator;#ifdef __STL_CLASS_PARTIAL_SPECIALIZATIONtypedef reverse_iteratorconst_iterator const_reverse_iterator;typedef reverse_iteratoriterator reverse_iterator;//vector.h部分源码 -- SGI版
template class T, class Alloc alloc
class vector {
public:typedef T value_type;typedef value_type* iterator;typedef const value_type* const_iterator;#ifdef __STL_CLASS_PARTIAL_SPECIALIZATIONtypedef reverse_iteratorconst_iterator const_reverse_iterator;typedef reverse_iteratoriterator reverse_iterator;可以看到STL 源码中 vector 和 list 的反向迭代器都是 reverse_iterator 类的 typedef而 reverse_iterator 类位于源码中的 stl_iterator.h 中其部分源码如下
//stl_iterator.h -- SGI版
template class Iterator
class reverse_iterator {
protected:Iterator current;public:typedef Iterator iterator_type;typedef reverse_iteratorIterator self;public:reverse_iterator() {}explicit reverse_iterator(iterator_type x) : current(x) {}reverse_iterator(const self x) : current(x.current) {}reference operator*() const {Iterator tmp current;return *--tmp;}
#ifndef __SGI_STL_NO_ARROW_OPERATORpointer operator-() const { return (operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */self operator() {--current;return *this;}self operator--() {current;return *this;}//...
}如上正向迭代器是 reverse_iterator 的模板参数而反向迭代器是 reverse_iterator 的对象所以反向迭代器是一个容器适配器它的适配容器就是对应的正向迭代器这样它就能根据传递过来的正向迭代器的不同实例化出对应的反向迭代器。
也就是说只要实现了 reverse_iterator 类以后不管是 vector、list、map 还是其他的容器只要你将其对应的正向迭代器传递给我我就能适配出对应的反向迭代器做到泛型编程。 三、reverse_iterator 的模拟实现
模拟实现代码iterator.h
#pragma oncenamespace thj {templateclass Iterator, class Ref, class Ptrclass reverse_iterator {typedef reverse_iteratorIterator, Ref, Ptr self;public:reverse_iterator(Iterator it) //构造: _it(it){}self operator() { //--_it;return *this;}self operator(int) { //后置 返回值不加引用因为tmp是局部变量Iterator tmp _it;--_it;return tmp;}self operator--() { //--_it;return *this;}self operator--(int) { //后置-- 返回值不加引用Iterator tmp _it;_it;return tmp;}bool operator!(const self s) const { //不等于return _it ! s._it;}Ref operator*() { //解引用返回的是反向迭代器的前一个位置Iterator tmp _it;return *(--tmp);}Ptr operator-() { //- 返回节点数据的地址return (operator*());}private:Iterator _it; //成员变量是正向迭代器};
}模拟实现细节
1、由于 rbegin() 等价于 end()rend() 等价于 begin()所以 reverse_iterator 等价于 --iteraor–reverse_iterator 等价于 iterator
2、在实现 operator*() 和 operator-() 时我们并不知道 T 的类型 (const 与非 const)所以我们不能确定函数的返回值STL 源码中使用迭代器萃取的方法来解决这个问题如下
//stl_iterator.h部分源码
template class Iterator
class reverse_iterator
{// iterator_traits -- 迭代器萃取typedef typename iterator_traitsIterator::pointertypedef typename iterator_traitsIterator::reference reference;reference operator*() const {Iterator tmp current;return *--tmp;}
#ifndef __SGI_STL_NO_ARROW_OPERATORpointer operator-() const { return (operator*()); }
};但是这种方式十分复杂并且校招的时候并不会考察萃取相关的知识所以这里我们参考 list 正向迭代器 的设计思路 – 增加两个模板参数分别作为 operator*() 和 operator-() 函数的返回值如下
//typedef reverse_iteratorIterator, T, T* reverse_iterator 反向迭代器
//typedef const_reverse_iteratorIterator, const T, const T* const_reverse_iterator const反向迭代器templateclass Iterator, class Ref, class Ptr
class reverse_iterator {typedef reverse_iteratorIterator, Ref, Ptr self;public:Ref operator*() { //解引用特别注意返回的是反向迭代器的前一个位置Iterator tmp _it;return *(--tmp);}Ptr operator-() { //- 返回节点数据的地址return (operator*());}private:Iterator _it; //成员变量是正向迭代器
};3、同时由于 end 是指向最后一个元素的下一个位置而 rbegin 由 end 适配得到所以反向迭代器中 operator*() 不是返回迭代器当前位置的数据而是返回迭代器前一个位置的数据不然会发生越界访问。 四、vector 和 list 反向迭代器的实现
现在我们已经实现了 reverse_iterator 类所以可以直接用 vector 和 list 的正向迭代器作为 reverse_iterator 的适配容器适配出它们的反向迭代器。
vector 反向迭代器
反向迭代器相关代码
#include iterator.h
templateclass Tclass list{//反向迭代器typedef thj::reverse_iteratoriterator, T, T* reverse_iterator;typedef thj::reverse_iteratorconst_iterator, const T, const T* const_reverse_iterator;reverse_iterator rbegin() {return reverse_iterator(end());}reverse_iterator rend() {return reverse_iterator(begin());}const_reverse_iterator rbegin() const {return const_reverse_iterator(end());}const_reverse_iterator rend() const {return const_reverse_iterator(begin());}};
}list.h
#pragma once#include assert.h
#include algorithm
#include iterator.hnamespace thj {templateclass Tstruct list_node{list_nodeT* _next;//不加T也没错但是写上好一些list_nodeT* _prev;T _data;list_node(const T x)//构造:_next(nullptr), _prev(nullptr), _data(x){}};//迭代器最终版//const 迭代器 -- 增加模板参数解决 operator*() 返回值与 operator-() 返回值问题//typedef __list_iteratorT, T, T* iterator;//typedef __list_iteratorT, const T, const T* const_iterator;//STL源码中大佬的写法利用多个模板参数来避免副本造成的代码冗余问题templateclass T, class Ref, class Ptrstruct __list_iterator //迭代器类{typedef list_nodeT node; //重命名list节点typedef __list_iteratorT, Ref, Ptr Self; //这里进行重命名是为了后续再添加模板参数时只用修改这一个地方node* _pnode; //节点指针作为类的唯一成员变量__list_iterator(node* p):_pnode(p){}Ref operator*() //解引用{return _pnode-_data;}Ptr operator-() //-{return _pnode-_data;}Self operator() //前置{_pnode _pnode-_next;return *this;}Self operator(int) //后置{Self it(*this);_pnode _pnode-_next;return it;}Self operator--() //前置--{_pnode _pnode-_prev;return *this;}Self operator--(int) //后置--{Self it(*this);_pnode _pnode-_prev;return it;}bool operator!(const Self it) const //!{return _pnode ! it._pnode;}bool operator(const Self it) const //{return _pnode it._pnode;}};//list 类templateclass Tclass list{typedef list_nodeT node;public:typedef __list_iteratorT, T, T* iterator; //迭代器typedef __list_iteratorT, const T, const T* const_iterator; //const 迭代器//反向迭代器typedef thj::reverse_iteratoriterator, T, T* reverse_iterator;typedef thj::reverse_iteratorconst_iterator, const T, const T* const_reverse_iterator;reverse_iterator rbegin() {return reverse_iterator(end());}reverse_iterator rend() {return reverse_iterator(begin());}const_reverse_iterator rbegin() const {return const_reverse_iterator(end());}const_reverse_iterator rend() const {return const_reverse_iterator(begin());}//迭代器iterator begin() {return iterator(_head-_next);}iterator end() {//iterator it(_head);//return it;//直接利用匿名对象更为便捷return iterator(_head);}const_iterator begin() const {return const_iterator(_head-_next);}const_iterator end() const {return const_iterator(_head);}void empty_initialize() { //初始化 -- 哨兵位头结点_head new node(T());_head-_next _head;_head-_prev _head;_size 0; //空间换时间用于标记节点个数}list() { //构造不是listT的原因构造函数函数名和类名相同而listT是类型empty_initialize();}//迭代器区间构造template class InputIteratorlist(InputIterator first, InputIterator last) {empty_initialize();while (first ! last){push_back(*first);first;//first;}}// 拷贝构造的现代写法//list(const list lt) 官方库是这样写的这是由于在类内类名等价于类型但不建议自己这样写list(const listT lt) {empty_initialize(); //初始化头结点防止交换后tmp野指针不能正常的调用析构listT tmp(lt.begin(), lt.end());swap(tmp);}//赋值重载现代写法//list operator(list lt)listT operator(listT lt) { //不能加引用lt是调用拷贝构造生成的swap(lt);return *this;}~list() { //析构clear();delete _head;_head nullptr;}void swap(listT lt) { //交换两个链表本质上是交换两个链表的头结点std::swap(_head, lt._head);std::swap(_size, lt._size);}size_t size() const { //增加一个计数的成员以空间换时间return _size;}bool empty() { //判空return _size 0;}void clear() {iterator it begin();while (it ! end()) {it erase(it);}_size 0;}void push_back(const T x) {insert(end(), x); //复用}void push_front(const T x) {insert(begin(), x); //复用}void pop_front() {erase(begin());}void pop_back() {erase(--end());}iterator insert(iterator pos, const T x) {node* newnode new node(x);node* cur pos._pnode;node* prev cur-_prev;prev-_next newnode;newnode-_prev prev;cur-_prev newnode;newnode-_next cur;_size;return iterator(pos);}iterator erase(iterator pos) {assert(pos ! end());node* prev pos._pnode-_prev;node* next pos._pnode-_next;prev-_next next;next-_prev prev;delete pos._pnode;--_size;return iterator(next);}private:node* _head;size_t _size;};
}test.cpp
void list_reverse_iterator_test() {thj::listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);thj::listint::reverse_iterator rit lt.rbegin(); //反向迭代器while (rit ! lt.rend()) {(*rit);cout *rit ;rit;}cout endl;const thj::listint clt(lt.begin(), lt.end());thj::listint::const_reverse_iterator crit clt.rbegin(); //const反向迭代器while (crit ! clt.rend()) {//(*crit);cout *crit ;crit;}cout endl;
}vector 反向迭代器
反向迭代器相关代码
namespace thj {templateclass Tclass vector {public://正向迭代器typedef T* iterator;typedef const T* const_iterator;//反向迭代器 -- 容器适配器typedef thj::reverse_iteratoriterator, T, T* reverse_iterator;typedef thj::reverse_iteratorconst_iterator, const T, const T* const_reverse_iterator;reverse_iterator rbegin() {return reverse_iterator(end());}reverse_iterator rend() {return reverse_iterator(begin());}const_reverse_iterator rbegin() const {return const_reverse_iterator(end());}const_reverse_iterator rend() const {return const_reverse_iterator(begin());}};
}vector.h
#pragma once
#include iostream
#include assert.h
#include string.h
#include algorithm
#include iterator.hnamespace thj {templateclass Tclass vector {public://正向迭代器typedef T* iterator;typedef const T* const_iterator;iterator begin() {return _start;}iterator end() {return _finish;}const_iterator begin() const {return _start;}const_iterator end() const {return _finish;}//反向迭代器 -- 容器适配器//反向迭代器 -- 容器适配器typedef thj::reverse_iteratoriterator, T, T* reverse_iterator;typedef thj::reverse_iteratorconst_iterator, const T, const T* const_reverse_iterator;reverse_iterator rbegin() {return reverse_iterator(end());}reverse_iterator rend() {return reverse_iterator(begin());}const_reverse_iterator rbegin() const {return const_reverse_iterator(end());}const_reverse_iterator rend() const {return const_reverse_iterator(begin());}public://---------------------------constructor------------------------------////无参构造vector():_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){}//迭代器区间构造templateclass InputIteratorvector(InputIterator first, InputIterator last):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){while (first ! last){push_back(*first);first;}}//n个val构造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);}//n个val构造 -- 重载vector(int n, const T val T()):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){reserve(n);for (int i 0; i n; i)push_back(val);}//拷贝构造 -- 现代写法vector(const vectorT v):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){vectorT tmp(v.begin(), v.end()); //复用构造函数和swap函数swap(tmp);}//析构函数~vector() {delete[] _start;_start _finish _end_of_storage nullptr;}//赋值重载vectorT operator(vectorT v) //复用拷贝构造存在自我赋值的问题但不影响程序正确性{swap(v);return *this;}//---------------------------------capacity------------------------------------//size_t size() const{return _finish - _start;}size_t capacity() const{return _end_of_storage - _start;}bool empty() const{return _start _finish;}//扩容void reserve(size_t n){if (n capacity()) //reserve 函数不缩容{T* tmp new T[n];//memcpy(tmp, _start, sizeof(T) * size()); //error//memcpy有自定义类型的浅拷贝问题需要对每个元素使用拷贝构造进行深拷贝for (int i 0; i size(); i)tmp[i] _start[i]; //拷贝构造size_t oldSize _finish - _start; //记录原来的size避免扩容不能确定_finishdelete[] _start;_start tmp;_finish _start oldSize;_end_of_storage _start n;}}//扩容并初始化void resize(size_t n, T x T()){if (n capacity()) //resize 不缩容{reserve(n);}if (n size()){while (_finish _start n){*_finish x;_finish;}}if (n size()){_finish _start n;}}//------------------------------element access-------------------//T operator[](size_t pos){assert(pos size()); //检查越界return _start[pos];}const T operator[](size_t pos) const{assert(pos size());return _start[pos];}//----------------------------------modifys-----------------------------------////尾插void push_back(const T n){if (size() capacity()){size_t newCapacity capacity() 0 ? 4 : capacity() * 2;reserve(newCapacity);}*_finish n;_finish;}//尾删void pop_back(){assert(!empty());--_finish;}//任意位置插入iterator insert(iterator pos, const T x){assert(pos _start);assert(pos _finish);//扩容导致 pos 迭代器失效if (size() capacity()){size_t oldPos pos - _start; //记录pos避免扩容后pos变为野指针size_t newCapacity capacity() 0 ? 4 : capacity() * 2;reserve(newCapacity);pos _start oldPos; //扩容之后更新pos}iterator end _finish - 1;while (end pos){*(end 1) *end;--end;}*pos x;_finish;return pos;}//任意位置删除 -- erase 之后也认为 pos 迭代器失效iterator erase(iterator pos){assert(pos _start);assert(pos _finish);iterator begin pos;while (begin _finish - 1){*begin *(begin 1);begin;}--_finish;return pos;}//交换两个对象void swap(vectorT v){std::swap(_start, v._start); //复用算法库的swap函数std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}void clear(){_finish _start;}private:T* _start;T* _finish;T* _end_of_storage;};
}test.cpp
void vector_reverse_iterator_test() {thj::vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);thj::vectorint::reverse_iterator rit v.rbegin();while (rit ! v.rend()) {(*rit);cout *rit ;rit;}cout endl;const thj::vectorint cv(v.begin(), v.end());thj::vectorint::const_reverse_iterator crit cv.rbegin();while (crit ! cv.rend()) {//(*crit);cout *crit ;crit;}cout endl;
}
