STL库中list的迭代器实现痛点分析
前文
本篇文章准备换个模式,之前都是先详解模拟实现,但是模拟实现的基本逻辑大多数老铁都是明白的,所以我们这次主要讲解 STL库中list的独特性,也就是模拟实现中的重难点
文末有模拟实现的源码
一,list实现的特殊类
list实现和前面vector,string最大的区别莫过于单独封装了迭代器。
我们通常使用的迭代器分为两种:1. 原生指针作为迭代器。如vector,string。2. 自定义类型对原生指针进行封装,模拟指针的行为。如list。
vector:
list:
在list中,我们对原生指针进行封装,模拟指针的行为,因此我们需要在该类中实现 *(),->,前置++,后置++,前置--,后置--,!=,==等函数重载
这时候可能有的老铁对,迭代器模板中三个模板参数感到惊讶,下面我们就来讲解一下。
二,迭代器模板中的多个模板参数
如图,迭代器模板参数中定义了三个模板参数,这是为什么呢?要注意这里是list中模板 非常非常巧妙的一种用法。
第一个T就不用多说了,和vector中的模板参数意义一样。我们重点说第二和第三个.
2.1 Ref模板参数
Ref模板参数的产生主要是因为 *()操作符重载
在实际的应用中,我们的list可能会被const修饰,导致里面的值只能读取不能修改,而如果用第一个模板参数我们则无法实现 const修饰返回值,因此我们专门写了第二个模板参数Ref来应对这种情况。
如上图所示,右边const修饰的list其中的值无法改变,我们会直接调用const_iterator迭代器进行模板实例化,这样Ref的值就为const T&,至此,我们就借助了第二个模板参数实现了正常迭代器和const修饰的迭代器的区分.
2.2 Ptr模板参数
Ptr模板参数是专门给 ->操作符重载准备的.
没有Ptr的话应该是这样
我们多一个模板参数的原因和Ref的原因一样,都是为了应对list被const修饰无法改变的情况
但是list迭代器中 ->操作符重载有一个 重要的特性。如下所示
图中第313行和314行代码不一样但执行效果却一样,为什么呢?
根据语法,313行想访问_a1,应该这样写it->->_a1,但it->_a1却也可以,为什么呢?
这是因为在这里我们为了 增强可读性,省略了一个->。
三,源码
#pragma once
#include <iostream>
#include <assert.h>
using namespace std;
namespace mjw
{
template<class T>
struct list_node
{
list_node<T>* _prev;
list_node<T>* _next;
T _data;
list_node(const T& val=T())
:_prev(nullptr)
,_next(nullptr)
,_data(val)
{}
};
template<class T,class Ref,class Ptr>
struct _list_iterator
{
typedef list_node<T> node;
typedef _list_iterator<T, Ref,Ptr> iterator;
node* _node;
_list_iterator(node* n)
:_node(n)
{}
//*()重载
Ref operator*()
{
return _node->_data;
}
//->重载
T* operator->()
{
return &_node->_data;
}
//前置++
iterator& operator++()
{
_node = _node->_next;
return *this;
}
//后置++
iterator operator++(int)
{
iterator tmp(*this);
_node = _node->_next;
return tmp;
}
//前置--
iterator& operator--()
{
_node = _node->_prev;
return *this;
}
//后置--
iterator operator--(int)
{
iterator tmp(*this);
_node = _node->_prev;
return tmp;
}
//!=重载
bool operator!=(const iterator ls)
{
return _node != ls._node;
}
//==重载
bool operator==(const iterator ls)
{
return _node == ls._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;
void empty_init()
{
_head = new node;
_head->_next = _head;
_head->_prev = _head;
}
//构造
list()
{
empty_init();
}
//区间构造
//先初始化,然后一个一个尾插
template<class InputIterator>
list(InputIterator first, InputIterator last)
{
empty_init();
while (first != last)
{
push_back(*first);
++first;
}
}
void swap(list<T>& tmp)
{
std::swap(_head, tmp._head);
}
//拷贝构造
list(const list<T>& lt)
{
empty_init();
list<T> tmp(lt.begin(),lt.end());
swap(tmp);
}
//赋值
list<T>& operator=(list<T> lt)
{
swap(lt);
return *this;
}
//析构
~list()
{
delete _head;
_head = _head->_next = _head->_prev = nullptr;
}
//clear
void clear()
{
iterator cur = begin();
while (cur != end())
{
erase(cur++);
}
}
//begin()
iterator begin()
{
return iterator(_head->_next);
}
const_iterator begin() const
{
return const_iterator(_head->_next);
}
//end()
iterator end()
{
return iterator(_head);
}
const_iterator end() const
{
return const_iterator(_head);
}
//尾插
void push_back(const T& val)
{
/*node* newnode = new node(val);
node* next = _head;
node* prev = _head->_prev;
newnode->_next = next;
newnode->_prev = prev;
prev->_next = newnode;
next->_prev = newnode;*/
insert(end(), val);
}
//尾删
void pop_back()
{
erase(--end());
}
//头插
void push_front(const T& val)
{
insert(begin(), val);
}
//头删
void pop_front()
{
erase(begin());
}
void insert(iterator pos, const T& val)
{
node* newnode = new node(val);
node* next = pos._node;
node* prev = next->_prev;
newnode->_next = next;
newnode->_prev = prev;
prev->_next = newnode;
next->_prev = newnode;
}
//为了防止迭代器失效,返回要删除的迭代器的下一个数据
iterator erase(iterator pos)
{
assert(pos._node != _head);
node* prev = pos._node->_prev;
node* next = pos._node->_next;
prev->_next = next;
next->_prev = prev;
delete pos._node;
pos._node = nullptr;
return iterator(next);
}
private:
node* _head;
};
}