反向迭代器
一.源码及框架分析
SGI-STL30版本源代码，反向迭代器实现的核心源码在stl_iterator.h中，反向迭代器是一个适配器，各个容器中再适配出自己的反向迭代器。下面截出vector和list的的反向迭代器结构框架核心部分截取出来如下：
// stl_list.h
template <class T, class Alloc = alloc>
class list {
public:
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;
#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
typedef reverse_iterator<const_iterator> const_reverse_iterator;
typedef reverse_iterator<iterator> reverse_iterator;
#else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
typedef reverse_bidirectional_iterator<const_iterator, value_type,
const_reference, difference_type> const_reverse_iterator;
typedef reverse_bidirectional_iterator<iterator, value_type, reference,
difference_type> reverse_iterator;
#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
iterator begin() { return (link_type)((*node).next); }
const_iterator begin() const { return (link_type)((*node).next); }
iterator end() { return node; }
const_iterator end() const { return node; }
reverse_iterator rbegin() { return reverse_iterator(end()); }
const_reverse_iterator rbegin() const {
return
const_reverse_iterator(end());
}
reverse_iterator rend() { return reverse_iterator(begin()); }
const_reverse_iterator rend() const {
return
const_reverse_iterator(begin());
}
};
// stl_vector.h
template <class T, class Alloc = alloc>
class vector {
public:
typedef T value_type;
typedef value_type* iterator;
#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
typedef reverse_iterator<const_iterator> const_reverse_iterator;
typedef reverse_iterator<iterator> reverse_iterator;
#else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
typedef reverse_iterator<const_iterator, value_type, const_reference,
difference_type> const_reverse_iterator;
typedef reverse_iterator<iterator, value_type, reference, difference_type>
reverse_iterator;
#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
iterator begin() { return start; }
const_iterator begin() const { return start; }
iterator end() { return finish; }
const_iterator end() const { return finish; }
reverse_iterator rbegin() { return reverse_iterator(end()); }
const_reverse_iterator rbegin() const {
return
const_reverse_iterator(end());
}
reverse_iterator rend() { return reverse_iterator(begin()); }
const_reverse_iterator rend() const {
return
const_reverse_iterator(begin());
}
};
// stl_iterator.h
#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
// This is the new version of reverse_iterator, as defined in the
// draft C++ standard. It relies on the iterator_traits template,
// which in turn relies on partial specialization. The class
// reverse_bidirectional_iterator is no longer part of the draft
// standard, but it is retained for backward compatibility.
template <class Iterator>
class reverse_iterator
{
protected:
Iterator current;
public:
typedef typename iterator_traits<Iterator>::iterator_category
iterator_category;
typedef typename iterator_traits<Iterator>::value_type
value_type;
typedef typename iterator_traits<Iterator>::difference_type
difference_type;
typedef typename iterator_traits<Iterator>::pointer
pointer;
typedef typename iterator_traits<Iterator>::reference
reference;
typedef Iterator iterator_type;
typedef reverse_iterator<Iterator> self;
public:
reverse_iterator() {}
explicit reverse_iterator(iterator_type x) : current(x) {}
reverse_iterator(const self& x) : current(x.current) {}
#ifdef __STL_MEMBER_TEMPLATES
template <class Iter>
reverse_iterator(const reverse_iterator<Iter>& x) : current(x.current) {}
#endif /* __STL_MEMBER_TEMPLATES */
iterator_type base() const { return current; }
reference operator*() const {
Iterator tmp = current;
return *--tmp;
}
#ifndef __SGI_STL_NO_ARROW_OPERATOR
pointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */
self& operator++() {
--current;
return *this;
}
self operator++(int) {
self tmp = *this;
--current;
return tmp;
}
self& operator--() {
++current;
return *this;
}
self operator--(int) {
self tmp = *this;
++current;
return tmp;
}
self operator+(difference_type n) const {
return self(current - n);
}
self& operator+=(difference_type n) {
current -= n;
return *this;
}
self operator-(difference_type n) const {
return self(current + n);
}
self& operator-=(difference_type n) {
current += n;
return *this;
}
reference operator[](difference_type n) const { return *(*this + n); }
};
template <class Iterator>
inline bool operator==(const reverse_iterator<Iterator>& x,
const reverse_iterator<Iterator>& y) {
return x.base() == y.base();
}
template <class Iterator>
inline bool operator<(const reverse_iterator<Iterator>& x,
const reverse_iterator<Iterator>& y) {
return y.base() < x.base();
}
template <class Iterator>
inline typename reverse_iterator<Iterator>::difference_type
operator-(const reverse_iterator<Iterator>& x,
const reverse_iterator<Iterator>& y) {
return y.base() - x.base();
}
template <class Iterator>
inline reverse_iterator<Iterator>
operator+(reverse_iterator<Iterator>::difference_type n,
const reverse_iterator<Iterator>& x) {
return reverse_iterator<Iterator>(x.base() - n);
}
#else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
// This is the old version of reverse_iterator, as found in the original
// HP STL. It does not use partial specialization.
template <class BidirectionalIterator, class T, class Reference = T&,
class Distance = ptrdiff_t>
class reverse_bidirectional_iterator {
typedef reverse_bidirectional_iterator<BidirectionalIterator, T, Reference,
Distance> self;
protected:
BidirectionalIterator current;
public:
typedef bidirectional_iterator_tag iterator_category;
typedef T value_type;
typedef Distance difference_type;
typedef T* pointer;
typedef Reference reference;
reverse_bidirectional_iterator() {}
explicit reverse_bidirectional_iterator(BidirectionalIterator x)
: current(x) {}
BidirectionalIterator base() const { return current; }
Reference operator*() const {
BidirectionalIterator tmp = current;
return *--tmp;
}
#ifndef __SGI_STL_NO_ARROW_OPERATOR
pointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */
self& operator++() {
--current;
return *this;
}
self operator++(int) {
self tmp = *this;
--current;
return tmp;
}
self& operator--() {
++current;
return *this;
}
self operator--(int) {
self tmp = *this;
++current;
return tmp;
}
};
template <class RandomAccessIterator, class T, class Reference = T&,
class Distance = ptrdiff_t>
class reverse_iterator {
typedef reverse_iterator<RandomAccessIterator, T, Reference, Distance>
self;
protected:
RandomAccessIterator current;
public:
typedef random_access_iterator_tag iterator_category;
typedef T value_type;
typedef Distance difference_type;
typedef T* pointer;
typedef Reference reference;
reverse_iterator() {}
explicit reverse_iterator(RandomAccessIterator x) : current(x) {}
RandomAccessIterator base() const { return current; }
Reference operator*() const { return *(current - 1); }
#ifndef __SGI_STL_NO_ARROW_OPERATOR
pointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */
self& operator++() {
--current;
return *this;
}
self operator++(int) {
self tmp = *this;
--current;
return tmp;
}
self& operator--() {
++current;
return *this;
}
self operator--(int) {
self tmp = *this;
++current;
return tmp;
}
self operator+(Distance n) const {
return self(current - n);
}
self& operator+=(Distance n) {
current -= n;
return *this;
}
self operator-(Distance n) const {
return self(current + n);
}
self& operator-=(Distance n) {
current += n;
return *this;
}
Reference operator[](Distance n) const { return *(*this + n); }
};
#endif //__STL_CLASS_PARTIAL_SPECIALIZATION
- 源码中我们可以看到reverse_iterator实现了两个版本，通过 __STL_CLASS_PARTIAL_SPECIALIZATION 条件编译控制使用哪个版本，简单点说就是支持偏特化的迭代器萃取以后，反向迭代器使用的是这个版本，
template < class Iterator > class reverse_iterator;之前使用的是
template <class BidirectionalIterator, class T, class Reference, class Distance> class reverse_bidirectional_iterator;
template <class RandomAccessIterator, class T, class Reference ,class Distance> class reverse_iterator; - 可以看到它们的差别主要是在模板参数是否传递迭代器指向的数据类型，支持偏特化的迭代器萃取以后就不需要给了，因为 reverse_iterator 内部可以通过迭代器萃取获取数据类型。迭代器萃取的本质是一个特化，这个还有有些小复杂就不讲解了。这个我们主要使用模版参数传递数据类型的方式实现。
- 反向迭代器本质是一个适配器，使用模版实现，传递哪个容器的迭代器就可以封装适配出对应的反向迭代器。因为反向迭代器的功能跟正向的迭代器功能高度相似，只是遍历的方向相反，类似operator++ 底层调用迭代器的 operator-- 等，所以封装一下就可以实现。
- 比较奇怪的是operator*的实现，内部访问的是迭代器当前位置的前一个位置。这个要结合容器中rbegin和rend实现才能看懂，rbegin返回的是封装end位置的反向迭代器，rend返回的是封装begin位置迭代器的反向迭代器，这里是为了实现出一个对称，所以解引用访问的是当前位置的前一个位置。
二.反向迭代器实现代码
1.ReverseIterator.h
#pragma once
//反向迭代器为适配器，适配于所有容器
//其中：Iterator：正向迭代器; Ref：数据类型的引用; Ptr：数据类型的指针
template<class Iterator, class Ref, class Ptr>
class ReverseIterator
{
typedef ReverseIterator<Iterator, Ref, Ptr> Self;
public:
ReverseIterator(Iterator it)
:_it(it)
{}
//迭代器不负责释放资源，没有析构函数
Ref operator*()
{
//return *_it;
Iterator tmp = _it;
--tmp;
return *tmp;
}
Ptr operator->()
{
return &(operator*());
}
Self& operator++()
{
--_it;
return *this;
}
Self operator++(int)
{
Self tmp(*this);
--_it;
return tmp;
}
Self& operator--()
{
++_it;
return *this;
}
Self operator--(int)
{
Self tmp(*this);
--_it;
return tmp;
}
bool operator!=(const Self& s)
{
return _it != s._it;
}
bool operator==(const Self& s)
{
return _it == s._it;
}
private:
Iterator _it; //利用正向迭代器封装方向迭代器
};
2.Vector.h
#pragma once
#include<assert.h>
#include"ReverseIterator.h"
namespace xzy
{
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
typedef ReverseIterator<iterator, T&, T*> reverse_iterator;
typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator;
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}
/*reverse_iterator rbegin()
{
return reverse_iterator(--end());
}
reverse_iterator rend()
{
return reverse_iterator(end());
}
const_reverse_iterator rbegin() const
{
return const_reverse_iterator(--end());
}
const_reverse_iterator rend() const
{
return const_reverse_iterator(end());
}*/
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()
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{}
vector(initializer_list<T> il)
{
reserve(il.size());
for (auto& e : il)
{
push_back(e);
}
}
vector(const vector<T>& v)
{
reserve(v.size());
for (auto& e : v)
{
push_back(e);
}
}
//类模版的成员函数可以是函数模版
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{
while (first != last)
{
push_back(*first);
++first;
}
}
vector(size_t n, const T& val = T())
{
reserve(n);
for (size_t i = 0; i < n; i++)
{
push_back(val);
}
}
void clear()
{
_finish = _start;
}
void swap(vector<int>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_storage, v._end_of_storage);
}
//类内可以用类名替代类型：vector& operator=(vector tmp)
vector<T>& operator=(vector<T> tmp)
{
swap(tmp);
return *this;
}
~vector()
{
if (_start != nullptr)
{
delete[] _start;
}
_start = _finish = _end_of_storage;
}
void reserve(size_t n)
{
if (n > capacity())
{
//先保存有效数据个数
size_t old_size = size();
//开空间
T* tmp = new T[n];
//拷贝数据
for (size_t i = 0; i < old_size; i++)
{
tmp[i] = _start[i];
}
//释放旧空间
delete[] _start;
//更新数据
_start = tmp;
_finish = _start + old_size;
_end_of_storage = _start + n;
}
}
void resize(size_t n, const T& val = T())
{
if (n < size())
{
_finish = _start + n;
}
else
{
reserve(n);
while (_finish < _start + n)
{
*_finish = val;
++_finish;
}
}
}
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 : 2 * capacity());
}
//尾插
*_finish = x;
++_finish;
}
bool empty()
{
return _start == _finish;
}
void pop_back()
{
assert(!empty());
--_finish;
}
iterator insert(iterator pos, const T& x)
{
//容量满了——>扩容
if (_finish == _end_of_storage)
{
//记录pos的相对位置防止迭代器失效
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : 2 * capacity());
pos = _start + len;
}
//整体后移一位
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
--end;
}
//插入数据
*pos = x;
++_finish;
return pos;
}
iterator erase(iterator pos)
{
iterator it = pos + 1;
while (it != end())
{
*(it - 1) = *it;
++it;
}
--_finish;
return pos;
}
T& operator[](size_t i)
{
assert(i >= 0 && i < size());
return _start[i];
}
const T& operator[](size_t i) const
{
assert(i >= 0 && i < size());
return _start[i];
}
private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _end_of_storage = nullptr;
};
}
3.List.h
#pragma once
#include<assert.h>
#include"ReverseIterator.h"
namespace xzy
{
template<class T>
struct list_node
{
typedef list_node<T> Node;
list_node(const T& data = T())
:_data(data)
, _next(nullptr)
, _prev(nullptr)
{}
T _data;
Node* _next;
Node* _prev;
};
template<class T, class Ref, class Ptr>
struct list_iterator
{
typedef list_node<T> Node;
typedef list_iterator<T, Ref, Ptr> Self;
Node* _node;
list_iterator(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;
}
bool operator==(const Self& s) const
{
return _node == s._node;
}
bool operator!=(const Self& s) const
{
return _node != s._node;
}
};
template<class T>
class list
{
public:
typedef list_node<T> Node;
typedef list_iterator<T, T&, T*> iterator;
typedef list_iterator<T, const T&, const T*> const_iterator;
typedef ReverseIterator<iterator, T&, T*> reverse_iterator;
typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator;
iterator begin()
{
return _head->_next;
}
iterator end()
{
return _head;
}
const_iterator begin() const
{
return _head->_next;
}
const_iterator end() const
{
return _head;
}
/*reverse_iterator rbegin()
{
return reverse_iterator(--end());
}
reverse_iterator rend()
{
return reverse_iterator(end());
}
const_reverse_iterator rbegin() const
{
return const_reverse_iterator(--end());
}
const_reverse_iterator rend() const
{
return const_reverse_iterator(end());
}*/
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());
}
void empty_init()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
list()
{
empty_init();
}
list(initializer_list<T> il)
{
empty_init();
for (auto& e : il)
{
push_back(e);
}
}
list(const list<T>& lt)
{
empty_init();
for (auto e : lt)
{
push_back(e);
}
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}
list<T>& operator=(list<T> tmp)
{
swap(tmp);
return *this;
}
void clear()
{
auto it = begin();
while (it != end())
{
it = erase(it);
}
_size = 0;
}
void push_back(const T& x)
{
//1.创建要插入的节点
Node* newnode = new Node(x);
//2.寻找尾节点
Node* tail = _head->_prev;
//3.尾插新节点
tail->_next = newnode;
newnode->_prev = tail;
newnode->_next = _head;
_head->_prev = newnode;
//4.节点数自增一个
++_size;
//insert(end(), x);
}
void push_front(const T& x)
{
//1.创建要插入的节点
Node* newnode = new Node(x);
//2.定位头节点的下一个节点
Node* next = _head->_next;
//3.头插新节点
_head->_next = newnode;
newnode->_prev = _head;
newnode->_next = next;
next->_prev = newnode;
//4.节点数自增一个
++_size;
//insert(begin(), x);
}
iterator insert(iterator pos, const T& x)
{
//1.保存结构体pos的指针和pos的前一个节点的指针
Node* cur = pos._node;
Node* prev = cur->_prev;
//2.创建要插入的节点
Node* newnode = new Node(x);
//3.插入新节点
newnode->_next = cur;
cur->_prev = newnode;
newnode->_prev = prev;
prev->_next = newnode;
//4.节点数自增一个
++_size;
return newnode;
}
void pop_back()
{
//1.保存要删除的节点的指针和前一个节点的指针
Node* del = _head->_prev;
Node* prev = del->_prev;
//2.修改指针的指向+删除节点
prev->_next = _head;
_head->_prev = prev;
delete del;
//3.节点数自减一个
--_size;
//erase(--end());
}
void pop_front()
{
//1.保存要删除的节点的指针和后一个节点的指针
Node* del = _head->_next;
Node* next = del->_next;
//2.修改指针的指向+删除节点
_head->_next = next;
next->_prev = _head;
delete del;
//3.节点数自减一个
--_size;
//erase(begin());
}
iterator erase(iterator pos)
{
//注意：不能删除哨兵位的头节点
assert(pos != end());
//1.保存pos节点的前后节点的指针
Node* prev = pos._node->_prev;
Node* next = pos._node->_next;
//2.修改指针的指向+删除节点
prev->_next = next;
next->_prev = prev;
delete pos._node;
//3.节点数自减一个
--_size;
return next;
}
private:
list_node<T>* _head;
size_t _size;
};
}
4.Test.cpp
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
#include"List.h"
#include"Vector.h"
int TestListReverseIterator()
{
xzy::list<int> lt1 = { 1,2,3,4 };
xzy::list<int>::reverse_iterator rit = lt1.rbegin();
while (rit != lt1.rend())
{
//*rit = 1; 可以修改
cout << *rit << " ";
++rit;
}
cout << endl;
const xzy::list<int> lt2 = { 1,2,3,4 };
xzy::list<int>::const_reverse_iterator crit = lt2.rbegin();
while (crit != lt2.rend())
{
//*crit = 1; 不能修改
cout << *crit << " ";
++crit;
}
cout << endl;
return 0;
}
int TestVectorReverseIterator()
{
xzy::vector<int> lt1 = { 1,2,3,4 };
xzy::vector<int>::reverse_iterator rit = lt1.rbegin();
while (rit != lt1.rend())
{
//*rit = 1; 可以修改
cout << *rit << " ";
++rit;
}
cout << endl;
const xzy::vector<int> lt2 = { 1,2,3,4 };
xzy::vector<int>::const_reverse_iterator crit = lt2.rbegin();
while (crit != lt2.rend())
{
//*crit = 1; 不能修改
cout << *crit << " ";
++crit;
}
cout << endl;
return 0;
}
int main()
{
TestVectorReverseIterator();
TestListReverseIterator();
return 0;
}