前言：
迭代器
正向迭代器
思路
-
list的关键地方是对迭代器的复写，在复写这一过程，可以不断体会C++语言泛型编程，函数重载的魅力
-
不同于vector，string，其底层类似数组，它们的迭代器是对元素对象的==“通用指针”,通过指针的运算，就可以完成很多操作：++，解引用等，但是因为结点是在堆上是随机存储的，因此链表的迭代器必然要进行改变，同时为了支持算术运算（++，–…）解引用等操作，链表的迭代器必然要封装成一个结构体==。
-
为什么使用结构体？结构体默认成员是public，方便访问成员。
-
同时又因为list是有const之分，因此迭代器分为iterarot和const_iterator,（注意这里的const是指节点中的data不可更改，但是迭代器仍是可以改变的，对比常量指针）**但是这2者的功能非常类似，因此这里就通过类模板的模板参数进行区别。----``泛型编程
**
构造函数
注意拷贝构造函数的形参，是最小权限，可以满足很多情形：匿名对象，类型提升
//迭代器
template <class T, class Ref ,class Ptr>
struct list_iterator
{
typedef list_iterator<T, T&, T*> iterator;
typedef list_iterator<T, const T&, const T*> const_iterator;
typedef list_node<T> Node;
typedef list_iterator<T, Ref, Ptr> Self;
Node* _node;
list_iterator( Node*x)
:_node(x)
{
;
}
list_iterator()
{}
//场景：权限缩小的拷贝，同时因为计算需要，生成临时对象时会调用
//其它的通过默认的拷贝构造和默认赋值运算符即可
list_iterator(const iterator& x) : _node(x._node)
{
}
++，–
typedef list_iterator<T, T&, T*> iterator;
typedef list_iterator<T, const T&, const T*> const_iterator;
typedef list_node<T> Node;
typedef list_iterator<T, Ref, Ptr> Self;
Self& operator++()
{
_node = _node->_next;
return *this;
}
//后置++
Self operator++(int)
{
Self tmp(*this);
_node = _node->_next;
return tmp;
}
Self& operator--()
{
_node = _node->_prev;
return *this;
}
//后置++
Self operator--(int)
{
Self tmp(*this);
_node = _node->_prev;
return tmp;
}
*，->
-
通过返回值的引用，当*时就可以防止const时，进行的写操作
-
对于节点中存放内置类型的数据时，通过*就可以得到数据但是对于自对于类型如果需要访问数据成员时，需要->运算符但是在使用->,为避免出现->->的情况，编译器会进行优化为一个->
如日期类 cout< < it- > year<<“” << it->month<<“”<< it->day<<endl;
本质上要想得到year，需要 (it->) ->year=Date->year,只是编译器优化了一下
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
！=，==
依据不同类型的迭代器，可能会因为生产一个临时的同类型的迭代器如：iterator和const iterator进行比较，会生成一个iterator的临时const_iterator的拷贝
bool operator !=(const Self& it)const
{
return _node != it._node;
}
bool operator ==(const Self& it)const
{
return _node == it._node;
}
反向迭代器
- 反向迭代器是对正向迭代器的复用，同时几乎所有的反向迭代器都是正向迭代器的复用，因此这里利用类模板来构造反向迭代器
- 反向迭代器的rbegin是正向迭代器的end(),rend()是正向迭代器的begin().
- 对于解引用，因为rbegin和rend的特殊性，反向迭代器返回的是迭代器前一个节点的数据
成员
template<class Iterator,class Ref,class Ptr >
class reverse_iterator
{
public:
typedef reverse_iterator<Iterator, Ref, Ptr> self;
private:
Iterator _it;
构造函数
template<class Iterator,class Ref,class Ptr >
class reverse_iterator
{
public:
typedef reverse_iterator<Iterator, Ref, Ptr> self;
//这种形式的形参是最小权限，可以满足任何的拷贝构造
reverse_iterator(const Iterator& it)
:_it(it)
{
;
}
++，–
self& operator++()
{
--_it;
return *this;
}
self operator++(int)
{
self tmp = _it--;
return tmp;
}
self& operator--()
{
++_it;
return *this;
}
self operator--(int)
{
self tmp = _it++;
return tmp;
}
*与->
Ref operator*()
{
Iterator tmp = _it;
return *(--tmp);
}
Ptr operator->()
{
Iterator tmp = _it;
return &(*(--tmp));
}
！=与==
bool operator !=(const self &rit )
{
return _it != rit._it;
}
bool operator ==(const self& rit)
{
return _it == rit._it;
}
private:
Iterator _it;
list
begin()
iterator begin()
{
return iterator (_head->_next);
}
const_iterator begin()const
{
return const_iterator(_head->_next);
}
rbegin()
reverse_iterator rbegin()
{
return reverse_iterator(end());
}
reverse_const_iterator rbegin()const
{
return reverse_iterator(end());
}
end()
iterator end()
{
return iterator(_head);
}
const_iterator end()const
{
return const_iterator(_head);
}
rend()
reverse_iterator rend()
{
return reverse_iterator (begin());
}
reverse_const_iterator rend()const
{
return reverse_iterator(begin());
}
inert()
//pos位置前插入数据
iterator insert(iterator pos, const T& value)
{
assert(pos != end());
Node* prevnode = pos._node->_prev;
Node* newnode = new Node(value);
newnode->_next = pos._node;
newnode->_prev = prevnode;
prevnode->_next = newnode;
pos._node->_prev = newnode;
return iterator(newnode);
}
erase()
//返回删除后下一个节点的迭代器
iterator erase(iterator pos)
{
assert(pos != end());
Node* prevnode = pos._node->_prev;
Node* nextnode = pos._node->_next;
prevnode->_next = nextnode;
nextnode->_prev = prevnode;
delete pos._node;
return iterator(nextnode);
}
全部代码
Reverse_iterator.h
#pragma once
namespace My_Rev_It
{
template<class Iterator,class Ref,class Ptr >
class reverse_iterator
{
public:
typedef reverse_iterator<Iterator, Ref, Ptr> self;
//这种形式的形参是最小权限，可以满足任何的拷贝构造
reverse_iterator(const Iterator& it)
:_it(it)
{
;
}
self& operator++()
{
--_it;
return *this;
}
self operator++(int)
{
self tmp = _it--;
return tmp;
}
self& operator--()
{
++_it;
return *this;
}
self operator--(int)
{
self tmp = _it++;
return tmp;
}
Ref operator*()
{
Iterator tmp = _it;
return *(--tmp);
}
Ptr operator->()
{
Iterator tmp = _it;
return &(*(--tmp));
}
bool operator !=(const self &rit )
{
return _it != rit._it;
}
bool operator ==(const self& rit)
{
return _it == rit._it;
}
private:
Iterator _it;
};
}
List.h
#pragma once
#include<iostream>
#include <stdlib.h>
#include <string>
#include <assert.h>
#include<time.h>
#include<windows.h>
#include<list>
#include"Reverse_iterator.h"
namespace My_List
{
//节点
template<class T>
struct list_node
{
list_node(const T &x=T())
:_next(nullptr),_prev(nullptr),_data(x)
{
;
}
list_node<T>* _next;
list_node<T>* _prev;
T _data;
};
//迭代器
template <class T, class Ref ,class Ptr>
struct list_iterator
{
typedef list_iterator<T, T&, T*> iterator;
typedef list_iterator<T, const T&, const T*> const_iterator;
typedef list_node<T> Node;
typedef list_iterator<T, Ref, Ptr> Self;
Node* _node;
list_iterator( Node*x)
:_node(x)
{
;
}
list_iterator()
{}
//这种形式的形参是最小权限，可以满足
// 权限缩小的拷贝，同时因为计算需要进行提升，生成临时对象时会调用
//其它的通过默认的拷贝构造和默认赋值运算符即可
list_iterator(const iterator& x) : _node(x._node)
{
}
//前置++
Self& operator++()
{
_node = _node->_next;
return *this;
}
//后置++
Self operator++(int)
{
Self tmp(*this);
_node = _node->_next;
return tmp;
}
Self& operator--()
{
_node = _node->_prev;
return *this;
}
//后置++
Self operator--(int)
{
Self tmp(*this);
_node = _node->_prev;
return tmp;
}
//通过返回值的引用，当*时就可以防止const时，进行的写操作
Ref operator*()
{
return _node->_data;
}
/* 对于节点中存放内置类型的数据时，通过*就可以得到数据
但是对于自对于类型如果需要访问数据成员时，需要->运算符
但是在使用->,为避免出现->->的情况，编译器会进行优化为一个->
如日期类
cout<<it->year<<"" <<it->month<<""<<it->day<<endl;
本质上要想得到year，需要 (it->) ->year=Date->year,只是编译器优化了一下*/
Ptr operator->()
{
return &_node->_data;
}
//即使是不同类型的迭代器，这里也会因为生产一个临时的同类型的迭代器
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
{
public:
typedef list_node<T> Node;
typedef list_iterator<T,T&,T*> iterator;
typedef list_iterator<T,const T&,const T*> const_iterator;
typedef My_Rev_It::reverse_iterator<iterator, T&, T*> reverse_iterator;
typedef My_Rev_It::reverse_iterator<const_iterator, const T&, const T*> reverse_const_iterator;
list(const T&value=T())//头节点
{
_head = new Node(value);
_head->_next = _head;
_head->_prev = _head;
}
list(int n, const T& value = T())
{
_head = new Node(value);
_head->_next = _head;
_head->_prev = _head;
for (int i = 0; i < n; ++i)
push_back(value);
}
//:list<Date> lt(5, Date(2022, 1, 2));
//list<int > lt1(5, 1);
//当形参进行对比时，对于Date会准确调用list(size_t n, const T& value = T())
//当为int时，编译器更倾向于list(Inputitator first, Inputitator last)
//因此重载一份list(int n, const T& value = T())即可
list(size_t n, const T& value = T())
{
_head = new Node(value);
_head->_next = _head;
_head->_prev = _head;
for (size_t i = 0; i < n; ++i)
push_back(value);
}
//利用迭代器区别初始化list
template<class Inputitator>
list(Inputitator first, Inputitator last)
{
//构建头节点
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
while (first != last)
{
push_back(*first);
++first;
}
}
//拷贝构造
list(const list<T> <)
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
list<T> tmp(lt.begin(), lt.end());
//注意 _head可能是随机指针或者nullptr
std::swap(_head, tmp._head);
}
//赋值运算符
list<T>& operator=(const list<T> lt)
{
clear();
std::swap(_head, lt._head);
return *this;
}
void clear()
{
iterator it = begin();
while (it != end())
{
erase(it++);
}
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
void push_back(const T &x)
{
insert(end(),x);
/*Node* tail = _head->_prev;
Node* newnode = new Node(x);
tail->_next = newnode;
newnode->_next = _head;
newnode->_prev = tail;
_head->_prev = newnode; */
}
void push_front(const T& x)
{
insert(begin(), x);
}
void pop_back()
{
erase(--end());
}
void pop_front()
{
erase(begin());
}
iterator begin()
{
return iterator (_head->_next);
}
iterator end()
{
return iterator(_head);
}
reverse_iterator rbegin()
{
return reverse_iterator(end());
}
reverse_iterator rend()
{
return reverse_iterator (begin());
}
reverse_const_iterator rbegin()const
{
return reverse_iterator(end());
}
reverse_const_iterator rend()const
{
return reverse_iterator(begin());
}
const_iterator begin()const
{
return const_iterator(_head->_next);
}
const_iterator end()const
{
return const_iterator(_head);
}
//pos位置前插入数据
//不会出现迭代器失效问题，但是需要返回一个插入位置的迭代器
//很显然，constlist是不需要insert的
iterator insert(iterator pos, const T& value)
{
Node* prevnode = pos._node->_prev;
Node* newnode = new Node(value);
newnode->_next = pos._node;
newnode->_prev = prevnode;
prevnode->_next = newnode;
pos._node->_prev = newnode;
return iterator(newnode);
}
//返回删除后下一个节点的迭代器
iterator erase(iterator pos)
{
assert(pos != end());
Node* prevnode = pos._node->_prev;
Node* nextnode = pos._node->_next;
prevnode->_next = nextnode;
nextnode->_prev = prevnode;
delete pos._node;
return iterator(nextnode);
}
private:
Node* _head;
};
}
总结
复写过程经常遇到类型无法转化问题，大概率是因为权限问题或者
转载：https://blog.csdn.net/qq_55439426/article/details/125751148
查看评论