文章目录
前言
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
{
//构造函数
//匿名对象构造_date
list_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
{
//构造函数
//匿名对象构造_date
list_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;
};
}