STL—— list迭代器封装的底层讲解

前言

list是相较于我们之前学习的vector，string的首个难度大增的容器，究其原因就是我们的list中运用到了较复杂的迭代器封装。（我们之前学习的接口只要一个类就能实现，而实现一个基础的list需要三到四个类）

那嘛什么是迭代器的封装嘞？

• 迭代器封装（Iterator Encapsulation）是指将底层数据遍历的细节隐藏在迭代器对象内部，对外只暴露统一的遍历接口。
• 在 C++ 中，“迭代器封装”并不是标准术语，但通常指的是将迭代器（iterator）包装或隐藏在一个更高级别的接口中，使使用者无需直接操作底层迭代器细节。这种封装的核心目的是简化迭代逻辑、提高安全性或扩展功能。

例如：我们在写一个遍历打印的代码时，虽然它们的底层代码不同，但是在封装后使用时用法几乎相同。这就是迭代器的封装起了作用。

vector<int> v1={1,2,3,4,5};
iterator it=v1.begin();
while(it!=v1.end())
{cont<<*it<<' ';
}
cout<<endl;

list<int> lt={1,2,3,4,5};
iterator it=lt.begin();
while(it!=lt.end())
{cont<<*it<<' ';
}
cout<<endl;

list的底层讲解

list就是所谓的链表，是由一个个结点构成，所以我们就先实现一个结点类（带头双向循环链表）

1.结点

我们的类用到了很多模板，所以定义一律在头文件中定义。
实现前为了和库中的list区分我们得用命名空间封装一下。

template<class T>
struct list_node
{//构造函数//匿名对象构造_datelist_node(const T& x = T()):_data(x), _next(nullptr), _prev(nullptr){}//成原变量设为共有方便其他类访问T _data;list_node<T>* _next = nullptr;list_node<T>* _prev = nullptr;
};

2.迭代器

首先我们要搞明白为什么我们的vector的迭代器就可以用原生指针实现，而list就需要封装呢？

• 那是因为vector是一个顺序表底层是个数组，可以直接用指针进行++，–等操作，而我们的链表底层不是一个连续的空间，指针不能直接++，–。

这时我们就想到去封装一个迭代器类，并且通过运算符重载的方式来实现迭代器的功能。

template<class T>
struct __list_iterator
{typedef list_node<T> Node;//成员变量（因为是封装一个迭代器，要有遍历等作用所以内部成员变量是个指针）Node* _node;//构造函数__list_iterator(Node* node):_node(node){ }	
};

有了成员变量现在开始运算符重载，先讲第一个重点operator*的实现
大家首先第一反应就是这个：

T operator*()
{return _node->_data;
}

2.1operator*的讲解（重点）

这个普通迭代器很简单，那我们的const迭代器就有问题了，如果直接去借鉴vector就有很大的问题：

typedef T* iterator;（vector里的）
typedef const T* const_iterator;（这里的const会使指针指向内容不能改变，而指针仍然可以++，--）

（上面的的const会使指针指向内容不能改变，而指针仍然可以++，--具有迭代器基本功能）
而这样操作我们的list时：

typedef __list_iterator<T> iterator;
typedef const __list_iterator<T> const_iterator;

（这里的__list_iterator<T>本身就是个类，我们在前面加了const后会使__list_iterator<T>类不能修改）不具有迭代器的++，- -等基本功能。
这时候有点同志会想到可以简单粗暴地直接加一个const迭代器的类
这方法简单粗暴，但显然不是最好的方法（多了很多行代码）

template<class T>struct __list_const_iterator{typedef list_node<T> Node;Node* _node;__list_const_iterator(Node* node):_node(node){}const T& operator*(){return _node->_data;}};

最好是利用模拟板参数实例化出一个，const迭代器，就是再加一个模板参数。
将__list_iterator类开头模板修改成这样：
template<class T,class Ref>
此时我们用模板参数实例化普通的operator*和cosnt版本的：

Ref operator*()//这里的Ref可以是T或const T
{return _node->_data;
}

2.2++，- -，!=，==

这些重载较为简单我们快速带过：

typedef __list_iterator<T, Ref> 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;
}
bool operator!=(const Self& it) const
{return _node != it._node;
}
bool operator==(const Self& it) const
{return _node == it._node;
}

2.3 operstor->（重点）

这个我们也做重点讲解
当我们的list使用一个类实例化时：list<Pos>（以下方的Pos为例）
我们可以通过迭代器的operator*打印：cout << (*it1)._row << ":" << (*it1)._col << endl;
那么operator->该如何实现呢？
我们可以看到Pos类里面有两个成员变量，也就是我们结点的_data中是两个两个一组的数据，那么我们想通过->访问其中一个数据时必须通过指针来完成（指针->_row），由此我们的operator->必须返回一个指针。
现在答案就明了了：

T* operator->()//这里的Ptr是T*和const T*
{return &_node->_data;
}

struct Pos
{int _row;int _col;Pos(int row = 0, int col = 0):_row(row), _col(col){}
};

再结合以下例子深入理解

dhb::list<Pos> lt1;
lt1.push_back({ 1,1 });
lt1.push_back({ 2,2 });
lt1.push_back({ 3,3 });
lt1.push_back({ 4,4 });//list<Pos>::iterator it = lt1.begin();
auto it1 = lt1.begin();//自动匹配类型
while (it1 != lt1.end())
{// 为了可读性，这里语法要求省略一个->cout << it1->_row << ":" << it1->_col << endl;//其实过程是cout << it.operator->()->_row << ":" << it.operator->()->_col << endl;//it.operator->返回的是_data，再通过_data->_row++it1;
}

我们的operator->()也有和operator*()相似的问题，就是const问题，我们这次就和上面一样直接再加一个模板参数使其成为：template<class T, class Ref, class Ptr>

Ptr operator->()//这里的Ptr是T*或const T*
{return &_node->_data;
}

3.链表

• 终于来到了链表本体部分，链表类就是使用结点类的结构并整合迭代器类实现增删查改等功能。
  首先我给大家说明一下，由于结点和迭代器产生了很多复杂类型名，我们在类的开头最好都给他们重命名一下。例如：

typedef list_node<T> Node;
//list最重要的迭代器
//其余类可以定义成内部类也可以外部
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;//也要封装一个反向迭代器的类
typedef Reverse_iterator<T, T&, T*> reverse_iterator;
typedef Reverse_iterator<T, const T&, const T*> const_reverse_iterator;

3.1构造，析构，清除，交换

这些可以说就是list的一个基本框架了
想要写出构造函数我们要先搞明白有多少成员变量：

private:Node* _head;size_t _size = 0;

这个_size是方便导出链表” 大小 “size()的，只要注意在增删查改时加进去就行。

void empty_init()
{_head = new Node;_head->_next = _head;_head->_prev = _head;
}
//构造函数
list()
{empty_init();
}
//拷贝构造
list(const list<T>& lt)
{empty_init();//插入数据for (const auto& e : lt){push_back(e);}
}
list(std::initializer_list<T> lt)  // 需要包含对应头文件，然后再这个命名空间std::使用
{empty_init();for (const auto& e : lt){push_back(e);}
}
void swap(list& li)
{std::swap(_head, li._head);std::swap(_size, li._size);
}
//赋值重载
list<T>& operator=(list<T> li)//list<T>& li  这里我们不传引用li就不会改变
{swap(li);return *this;
}
//析构函数
~list()
{clear();delete _head;_head = nullptr;
}
void clear()//清除列表里的数据
{iterator it = begin();//while (begin != it.end())while(it != end())   // 直接就是end，这里是it呀{it=erase(it);//考虑迭代器失效}
}

3.2迭代器（重点）

• 这里我也顺势给大家补充一下反向迭代器，以我现在的知识最好的解决方案就是再封装一个反向迭代器类，再复用list类中正向迭代器。
  反向迭代器只要注意 头是尾，尾是头，++是- -，- -是++。 其他和正向迭代器大同小异。

template<class T, class Ref, class Ptr>
struct Reverse_iterator
{typedef list_node<T> Node;typedef Reverse_iterator<T, Ref, Ptr> Self;//成员变量（因为是封装一个迭代器，要有遍历等作用所以内部成员变量是个指针）Node* _node;//构造函数Reverse_iterator(Node* node):_node(node){}Ref operator*()//这里的Ref是T和const T{return _node->_data;}Ptr operator->()//这里的Ptr是T*和const T*{return &_node->_data;}Self& operator++()//前置++{_node = _node->_prev;return *this;}Self& operator++(int)//后置++{Self tmp(*this);_node = _node->_prev;return tmp;}Self& operator--()//前置--{_node = _node->_next;return *this;}Self& operator--(int)//前置--{Self tmp(*this);_node = _node->_next;return tmp;}bool operator!=(const Self& it) const{return _node != it._node;}bool operator==(const Self& it) const{return _node == it._node;}
};

在list类中封装迭代器

iterator begin()
{return iterator(_head->_next);
}
iterator end()
{return iterator(_head);
}//反向迭代器可以复用
reverse_iterator rbegin()
{return reverse_iterator(_head->_prev);
}
reverse_iterator rend()
{return reverse_iterator(_head);
}
const_reverse_iterator rbegin()const
{return const_reverse_iterator(_head->_prev);
}
const_reverse_iterator rend()const
{return const_reverse_iterator(_head);
}
const_iterator begin()const
{return const_iterator(_head->_next);
}
const_iterator end()const
{return const_iterator(_head);
}

3.3增删查改

这和我们以前学习的链表底层结构没多大区别，本期关键就是要介绍C++一大特性：封装。接下来快速带过增删查改代码。

• 接下来其实只要写insert和erase然后其他的头插尾插等就可以复用了
• 两个函数返回的都是迭代器

iterator insert(iterator pos, const T& val)
{Node* cur = pos._node;Node* newnode = new Node(val);//Node* prev = cur->_prve;Node* prev = cur->_prev;//在pos前插入数据prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;_size++;//不要忘记返回值return iterator(newnode);
}
iterator erase(iterator pos)
{Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;_size--;//不要忘记释放空间delete cur;return next;
}
void push_back(const T& val)
{insert(end(), val);//++_size;上面的insert已经完成此操作
}	
void pop_back()
{erase(--end());//这里的参数注意//--_size;
}
void push_front(const T& val)
{insert(begin(), val);
}
void  pop_front()
{erase(begin());
}
size_t size() const
{return _size;
}

完整头文件

最后将完整的头文件给大家：

#pragma once
#include <initializer_list>namespace dhb
{//先构建一个带头双向链表//设立为共有template<class T>struct list_node{//构造函数//匿名对象构造_datelist_node(const T& x = T()):_data(x), _next(nullptr), _prev(nullptr){}//成原变量设为共有方便其他类访问T _data;list_node<T>* _next = nullptr;list_node<T>* _prev = nullptr;};//这里迭代器就不能用原生指针实现了//我们自己封装一个迭代器用运算符重载的方式定义功能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){ }//有了成员变量现在开始运算符重载//*//返回的数据如果是const类型就不能改变值，T类型就可以//那我们能不能像顺序表vector一样，用原生指针的方式：//typedef T* iterator;（vector里的）//typedef const T* const_iterator;（这里的const会使指针指向内容不能改变，而指针仍然可以++，--）//这样操作？//显然不行：我们这里的迭代器是服务链表的，链表不能用原生指针实现迭代器//故当我们封装以后如果这样实现的话// typedef const __list_iterator<T> const_iterator;//（这里的__list_iterator<T>本身就是个类，我们在前面加了const后会使__list_iterator<T>类不能修改）//不具有迭代器的++，--功能//这时候有点同志会想到可以简单粗暴地直接加一个const迭代器的类//但是这种方法不是最好的//最好是利用模拟板参数实例化出一个，const迭代器（用Ref）Ref operator*()//这里的Ref是T和const T{return _node->_data;}Ptr operator->()//这里的Ptr是T*和const T*{return &_node->_data;}Self& operator++()//前置++{//_node = _node->next;  _node = _node->_next;// 返回值return *this;}Self& operator++(int)//后置++{Self tmp(*this);//_node = _node->next;  // 名字写错哦_node = _node->_next;// 返回值return tmp;}Self& operator--()//前置--{_node = _node->_prev;// 返回值return *this;}Self& operator--(int)//前置--{Self tmp(*this);_node = _node->_prev;// 返回值return tmp;}bool operator!=(const Self& it) const{return _node != it._node;}bool operator==(const Self& it) const{return _node == it._node;}};template<class T, class Ref, class Ptr>struct Reverse_iterator{typedef list_node<T> Node;typedef Reverse_iterator<T, Ref, Ptr> Self;//成员变量（因为是封装一个迭代器，要有遍历等作用所以内部成员变量是个指针）Node* _node;//构造函数Reverse_iterator(Node* node):_node(node){}Ref operator*()//这里的Ref是T和const T{return _node->_data;}Ptr operator->()//这里的Ptr是T*和const T*{return &_node->_data;}Self& operator++()//前置++{_node = _node->_prev;return *this;}Self& operator++(int)//后置++{Self tmp(*this);_node = _node->_prev;return tmp;}Self& operator--()//前置--{_node = _node->_next;return *this;}Self& operator--(int)//前置--{Self tmp(*this);_node = _node->_next;return tmp;}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;//list最重要的迭代器//其余类可以定义成内部类也可以外部typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;// 反向迭代器适配支持//也要封装一个反向迭代器的类typedef Reverse_iterator<T, T&, T*> reverse_iterator;typedef Reverse_iterator<T, const T&, const T*> const_reverse_iterator;	iterator begin(){return iterator(_head->_next);}iterator end(){return iterator(_head);}//反向迭代器可以复用reverse_iterator rbegin(){return reverse_iterator(_head->_prev);}reverse_iterator rend(){return reverse_iterator(_head);}const_reverse_iterator rbegin()const{return const_reverse_iterator(_head->_prev);}const_reverse_iterator rend()const{return const_reverse_iterator(_head);}const_iterator begin()const{return const_iterator(_head->_next);}const_iterator end()const{return const_iterator(_head);}void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;}//构造函数list(){empty_init();}//拷贝构造list(const list<T>& lt){empty_init();//插入数据for (const auto& e : lt){push_back(e);}}list(std::initializer_list<T> lt)  // 需要包含对应头文件，然后再这个命名空间std::使用{empty_init();for (const auto& e : lt){push_back(e);}}void swap(list& li){std::swap(_head, li._head);std::swap(_size, li._size);}//赋值重载list<T>& operator=(list<T> li)//list<T>& li  这里我们不传引用li就不会改变{swap(li);return *this;}//析构函数~list(){clear();delete _head;_head = nullptr;}void clear()//清除列表里的数据{iterator it = begin();//while (begin != it.end())while(it != end())   // 直接就是end，这里是it呀{it=erase(it);//考虑迭代器失效}}//接下来只要写insert和erase然后其他的头插尾插等就可以复用了//两个函数都是返回迭代器的iterator insert(iterator pos, const T& val){//Node* cur = pos.node;Node* cur = pos._node;Node* newnode = new Node(val);//Node* prev = cur->_prve;Node* prev = cur->_prev;//在pos前插入数据prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;_size++;//不要忘记返回值return iterator(newnode);}iterator erase(iterator pos){Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;_size--;//不要忘记释放空间delete cur;return next;}void push_back(const T& val){insert(end(), val);//++_size;上面的insert已经完成此操作}	void pop_back(){erase(--end());//这里的参数注意//--_size;}void push_front(const T& val){insert(begin(), val);}void  pop_front(){erase(begin());}size_t size() const{/*size_t n = 0;for (auto& e : *this){++n;}return n;*/return _size;}private://Node _head;Node* _head;size_t _size = 0;};
}