C++（list的简单实现，着重点是迭代器）
本文适合能自主实现双向链表增删的有功底的人，如果不会的话可以看我以前使用c实现的双向链表。
C++中list是双向链表，forword_list才是单链表
目录
1.节点（list_node）
2.链表的成员函数的实现
3.iterator迭代器
4.const_iterator 迭代器
5.合并iterator和const_iterator
1.节点（list_node）
template<class T>
struct list_node
{
list_node(const T& val = T())
:_val(val)//这里是初始化
{
_next = _prev = this;//使指针指向自己
//_val = val;//为什么不在写？因为这里赋值，因为模板参数可能是T = const int等，const不支持修改
}
list_node<T>* _next;
list_node<T>* _prev;
T _val;
};初始化列表是初始化，而代码块中的代码是赋值。const类型的数据一旦初始化后，就不能在修改其值。
2.链表的成员函数的实现
这里就是链表的增删问题了这里就不讲了，直接给代码。
template<class T>
class list
{
typedef list_node<T>* PNode;
typedef list_node<T> Node;
public:
//构造
list()
{
_phead = new Node(-1);
}
//拷贝构造
list(const list<T>& l)
{
PNode pcur = l._phead->_next;
while (pcur != l._phead)
{
push_back(pcur->_val);
}
}
//深拷贝实现的复制
list<T>& operator=(const list<T>& l)
{
PNode pcur = l._phead->_next;
while (pcur != l._phead)
{
push_back(pcur->_val);
}
return *this;
}
//现代写法
list<T>& operator=(list<T> l)
{
std::swap(_phead,l._phead);
return *this;
}
//析构
~list()
{
delete(_phead);
}
iterator begin()
{
return _phead->_next;
}
iterator end()
{
return _phead;
}
size_t size()
{
PNode pcur = _phead->_next;
int cout = 0;
while (pcur != _phead)
{
count++;
pcur = pcur->_next;
}
return count;
}
bool empty()
{
return _phead->_next == _phead;
}
T& front()
{
return _phead->_next->_val;
}
T& back()
{
PNode pcur = _phead->_next;
while (pcur->_next != _phead)
{
pcur = pcur->_next;
}
return pcur->_val;
}
//push,pop可以复用insert和erase
void push_back(const T& val) { insert(end(), val); }
void pop_back() { erase(--end()); }
void push_front(const T& val) { insert(begin(), val); }
void pop_front() { erase(begin()); }
// 在pos位置前插入值为val的节点
iterator insert(iterator pos, const T& val)
{
PNode newnode = new Node(val);
newnode->_prev = pos.operator->()->_prev;
pos.operator->()->_prev->_next = newnode;
newnode->_next = pos.operator->();
pos.operator->()->_prev = newnode;
return newnode;
}
// 删除pos位置的节点，返回该节点的下一个位置
iterator erase(iterator pos)
{
PNode del = pos.operator->();
PNode ret = del->_next;
del->_prev->_next = del->_next;
del->_next -> _prev = del->_prev;
delete del;
return ret;
}
void clear()
{
PNode* pcur = _phead;
PNode* next;
while (pcur != _phead)
{
next = pcur->_next;
delete pcur;
pcur = next;
}
}
//交换的是资源
void swap(list<T>& l)
{
std::swap(_phead, l._phead);
}
private :
PNode _phead;//指向哨兵位
};3.iterator迭代器
iterator迭代器的本质就是控制指向节点的指针的向前和向后移动。
template<class T>
class Iterator
{
typedef list_node<T>* PNode;
typedef list_node<T> Node;
typedef Iterator<T> Self;
public:
//构造
Iterator(PNode ptr = nullptr)
{
_pnode = ptr;
}
//没有析构函数，让编译器自动生成就可以了，因为没有资源需要释放
//返回当前iterator指向的节点的_val值
T& operator*()
{
return _pnode->_val;
}
//如果_val的类型是一个结构体的话可以使用这个，这个的意思就是访问_val的成员
T* operator->()
{
return &(_pnode->_val);
}
//前置++
Self& operator++()
{
_pnode = _pnode->_next;
return *this;
}
//后置++
Self operator++(int)
{
PNode tmp = _pnode;
_pnode = _pnode->_next;
return tmp;
}
Self& operator--()
{
_pnode = _pnode->_prev;
return* this;
}
Self operator--(int)
{
PNode* tmp = _pnode;
_pnode = _pnode->_prev;
return tmp;
}
bool operator!=(const Self& l)
{
return _pnode != l._pnode;
}
bool operator==(const Self& l)
{
return _pnode == l._pnode;
}
private:
PNode _pnode;
};这里将operator-> 的一些注意事项：
理解一下operator->()的本质，就是返回_val的首元素地址。
//假如T的类型是class A
class A
{
public:
int a;
int b;
}
//
list<A> ls = {{1,2}，{2,3}，{2,4}}}；
list<A>::iterator it = ls.begin();
it->a; //这句代码的实现就是 it.operator->()->a; 也就是先调用operator->()，再用其返回值加上下标引用操作符访问a，可以理解为operator->()返回的是结构体或类的等可以通过下标访问操作符访问其成员的指针
注意前置++，和后置++的区别
首先，前置++，是先++后使用，返回的是该iterator的引用。
后置++，是先使用后++，所以返回的是++之前的值，所以返回值，就是++前的iterator（不是引用）。
前置--，和后置--也是类似的道理。
4.const_iterator 迭代器
注意const_iterator与iterator的区别，不是再iterator前加一个const，注意cosnt和iterator之间有一个下划线连接；而两者的真正区别就是const_iterator不允许对iterator指向的节点的元素的值进行修改。
template<class T>
class Iterator
{
typedef list_node<T>* PNode;
typedef list_node<T> Node;
typedef Iterator<T> Self;
public:
//构造
Iterator(PNode ptr = nullptr)
{
_pnode = ptr;
}
//没有析构函数，让编译器自动生成就可以了，因为没有资源需要释放
//返回当前iterator指向的节点的_val值
const T& operator*()
{
return _pnode->_val;
}
//如果_val的类型是一个结构体的话可以使用这个，这个的意思就是访问_val的成员
const T* operator->()
{
return &(_pnode->_val);
}
//前置++
const Self& operator++()
{
_pnode = _pnode->_next;
return *this;
}
//后置++
const Self operator++(int)
{
PNode tmp = _pnode;
_pnode = _pnode->_next;
return tmp;
}
const Self& operator--()
{
_pnode = _pnode->_prev;
return* this;
}
const Self operator--(int)
{
PNode* tmp = _pnode;
_pnode = _pnode->_prev;
return tmp;
}
bool operator!=(const Self& l)
{
return _pnode != l._pnode;
}
bool operator==(const Self& l)
{
return _pnode == l._pnode;
}
private:
PNode _pnode;
};跟上面的iterator的实现差不多就是返回值需要用const修饰，毕竟不允许修改值嘛。
5.合并iterator和const_iterator
上面的两个迭代器的实现非常类似，所以能否通过一个模板来实现呢？
注意上面两个代码的异同
iterator const_iterator
T const T
T* const T*
T& const T&
//下面两个可以根据传入的T还是const T来相应的生成。
iterator<T> const_iterator<const T>
iterator<T>& const_iterator<const T>&
所以只需要根据前三个参数，模板就可以知道生成iterator的模板还是const_iterator的模板。
template<class T,class Ref,class Ptr>
class Iterator
{
typedef list_node<T>* PNode;
typedef list_node<T> Node;
typedef Iterator<T, Ref, Ptr> Self;
public:
Iterator(PNode ptr = nullptr)
{
_pnode = ptr;
}
T& operator*()
{
return _pnode->_val;
}
PNode operator->()
{
return _pnode;
}
Self& operator++()
{
_pnode = _pnode->_next;
return *this;
}
Self operator++(int)
{
PNode tmp = _pnode;
_pnode = _pnode->_next;
return tmp;
}
Self& operator--()
{
_pnode = _pnode->_prev;
return* this;
}
Self operator--(int)
{
PNode* tmp = _pnode;
_pnode = _pnode->_prev;
return tmp;
}
bool operator!=(const Self& l)
{
return _pnode != l._pnode;
}
bool operator==(const Self& l)
{
return _pnode == l._pnode;
}
private:
list_node<T>* _pnode;
};实例化时：
template<class T>
class list
{
public:
typedef Iterator<T,T&,T*> iterator;//iteraotr迭代器
typedef Iterator<const T, const T&, const T*> const_iterator;//const_iterator迭代器
}完整代码。
刷题记录: 用来调试刷题是写的代码 (gitee.com)