List的简单模拟实现
这次我们对 List 做一个简单的模拟，主要实现其迭代器和拷贝构造等功能。
1.list 成员变量
list 底层就是带头双向循环链表结构，其成员变量就是结点。所以最开始我们需要构建一个结点结构，并且因为需要对结点反复操作，我们将结点结构类型设置为公有，这里 struct 就十分合适。
在头文件中进行相关设计。
//List.h
#include<iostream>
//声明一个命名空间避免和 std 库中的 list 命名冲突
namespace my_list{
//构造节点
template<class T>
// struct 默认为公有性质
struct list_node{
T _data;
list_node<T>* _next;
list_node<T>* _prev;
//结点的构造，用相应数据初始化结点
lsit_node(const T& x = T())
:_data(x)
,_next(nullptr)
,_prev(nullptr)
{}
};
//list 类
template<class T>
class list{
//便于书写
typedef list_node<T> Node;
//list 成员变量就是结点
private:
Node* _node;
};
}
在用数据构造结点时，我们默认输入的数据是 T()，这表示相应类型的默认数据，如int默认为 0，等。
确定基本结构后，我们再实现一下空链表的构造，以及一个简单的尾插。随后我们就能进行简单的测试了。
//List.h
//list 类
template<class T>
class list{
//便于书写
typedef list_node<T> Node;
public:
//空链表构造
list(){
// new 一个结点
_node = new Node;
//头尾指针指向自己
_node->_next = _node->prev = _node;
}
//构造的链表的第一个结点是作为哨兵位的存在
//尾插
void push_back(cosnt T& x){
//创建新节点
Node* newnode = new Node(x);
//找到当前链表的尾结点
Node* tail = _node->_prev;
//调整指针
newnode->_prev = tail;
tail->_next = newnode;
newnode->_next = _node;
_node->_prev = newnode;
}
//list 成员变量就是结点
private:
Node* _node;
};
————————————————————————————————————————————————————————————————————————————
//test.cpp
namespace my_list{
void test01(){
my_list::list<int> lt1;
lt1.push_back(1);
lt1.push_back(2);
lt1.push_back(3);
lt1.push_back(4);
}
}
int main(){
my_list::test01();
return 0;
}
因为没写迭代器之类的，所以我们通过监视窗口查看。
这里 0 作为哨兵位的数据，_next 指向数据为 1 的结点，_prev 指向数据为 4 的结点。
2.list 迭代器
因为 list 底层是链表结构，基本是结点，所以如果迭代器使用原生指针迭代的话，无法实现结点中的迭代，
所以我们参考了库中 list 迭代器的实现方式——类封装并重载运算符 ++。
//List.h
//用于迭代器的类封装
template<class T>
struct __list_iterator { //加 _ 一般表示不对外暴露
typedef list_node<T> Node;
Node* _node;
//构造迭代器
__list_iterator(Node* node)
:_node(node)
{}
//重载运算符前置 ++
__list_iterator<T>& operator++() {
_node = _node->_next;
//返回修改后的结点
return *this;
}
//解引用
T& operator*() {
return _node->_data;
}
//!=
bool operator!=(const __list_iterator<T>& it)const {
return _node != it._node;
}
};
//list 类
template<class T>
class list {
//便于书写
typedef list_node<T> Node;
public:
//使用类封装的迭代器
typedef __list_iterator<T> iterator;
//获得边界
iterator begin() {
//开始结点是哨兵位的后一结点
return _node->_next;
}
iterator end() {
//尾结点就是哨兵位结点
return _node;
}
......
————————————————————————————————————————————————————————————————————————————————
//test.cpp
void test01() {
my_list01::list<int> lt1;
lt1.push_back(1);
lt1.push_back(2);
lt1.push_back(3);
lt1.push_back(4);
//用迭代器遍历 list lt1
list<int>::iterator it1 = lt1.begin();
while (it1 != lt1.end()) {
cout << *it1 << " ";
++it1;
}
cout << endl;
}
这样我们就能通过迭代器遍历链表 lt1 了。
值得注意的是，在重载运算符 != 时，那两个 const 和 & 使用的意义在于，
1）函数参数列表中的 const 表示传入的参数不可修改；
2）引用 & 表示参数 it 是传入迭代器对象的一个别名，而不是其拷贝，确保了传递的高效性。因 为复制一个指针非常高效，复制整个迭代器结构（即使很小）也比传递引用开销大，这避免了在函数调用时复制整个 __list_iterator 对象；
3）最后一个在函数参数列表之后、函数体之前的 const ，它修饰的是整个成员函数，它确保这个 operator!= 函数在调用时，不会修改调用该函数的迭代器对象本身（即 *this）的任何成员变量。在这个函数内部，this 指针的类型变成了 const __list_iterator<T>*，即 const 修饰的是指针所指向的内容而非这个指针！意味着你不能通过 this 指针修改 this->_node。
除此之外，使用了类封装的迭代器并不需要析构，因为迭代器它指向的结点并不属于迭代器本身，迭代器只是能够访问结点而已。在迭代器离开作用域销毁后，结点属于链表应当仍旧存在。相应地，迭代器的拷贝构造和赋值重载也就不需要写了，就用默认的赋值进行浅拷贝就行。
言至此，我们还没写链表的析构，补充一下，
//list 类中
//析构
~list() {
//从哨兵位的第一个结点开始
Node* cur = _node->_next;
while (cur != _node) {
Node* next = cur->_next;
delete cur;
cur = next;
}
delete cur;
cur = nullptr;
}
实际上，标准库中的 erase 和迭代器可以在这派上用场，我们可以用它再写两个版本的析构，进一步地简化。
//list 类中
//删除 pos 位置的结点
iterator erase(iterator pos) {
//记录 pos 位置的前 中 后 三结点
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
//调整指向
prev->_next = next;
next->_prev = prev;
//释放
delete cur;
cur = nullptr;
//返回 pos 位置的新节点
return iterator(next);
}
//clear —— 只清理内容，不清理空间
void clear() {
iterator it = begin();
while (it != end()) {
it = erase(it);
}
}
内部使用迭代器删除
//~list() {
// iterator it = begin();
// while (it != end()) {
// it = erase(it);
// }
// delete _node;
// _node = nullptr;
//}
//迭代器部分再精简
~list() {
clear();
delete _node;
_node = nullptr;
}
接着，我们再进一步地完善迭代器，加入后置 ++ 、-- 、== 。并且为了便于打印链表类中的各中类型链表，我们写一个针对链表的泛型化打印函数 print()
//迭代器类封装中
//__list_iterator<T>
//后置 ++
__list_iterator<T> operator++(int) {
__list_iterator<T> tmp(*this);
_node = _node->_next;
return tmp;
}
//重载运算符前置 --
__list_iterator<T>& operator++() {
_node = _node->_prev;
//返回修改后的结点
return *this;
}
//后置 --
__list_iterator<T> operator++(int) {
__list_iterator<T> tmp(*this);
_node = _node->_prev;
return tmp;
}
//==
bool operator==(const __list_iterator<T>& it)const {
return _node == it._node;
}
——————————————————————————————————————————————————————————————————————————————————
//test.cpp
//针对链表的泛型化打印
template<class T>
void print(const list<T>& lt) {
//list<T>::iterator it = lt.begin();
//typename list<T>::iterator it = lt.begin();
//更简洁地
auto it = lt.begin();
while (it != lt.end()) {
cout << *it << " ";
++it;
}
cout << endl;
}
有个小细节需要注意的是，前置和后置 ++ 的区别在自定义类型中可有明显体现，后置的一次调用就需要用两次拷贝构造，但前置的没有，因此我们建议常用前置 ++。
运行这个泛型化的打印函数时出现错误，
原因：这里带有模板 T 实例化参数，但还没有实例化，导致编译器不确定这 iterator 是内嵌类型，还是静态成员变量
解决：typename 告知编译器这是类型。
这之后，还是有错误，我们发现调不到我们前面写的普通迭代器，
原因：print 参数列表中的 const 表示这个 list 类调用的是 const 迭代器
解决：删掉 const （能通过，但是达不到目的：指向能够修改，而指向的内容不能修改的 const 迭代器）或者 写一个 const 迭代器（我们最初的目的就是模拟实现 list，所以我们用这种解决方案）。
那么，我们该如何写一个指向能够修改，而指向的内容不能修改的 const 迭代器呢？
iterator 之前加 const？—— 指向不能修改而指向的内容能够修改啦！背道而驰。
因为我们都是使用迭代器中的运算符重载 * 来访问迭代器指向的内容的，所以对它冻🔪。
//普通迭代器类封装中
const T& operator*() {
return _node->_data;
}
这样不就能让迭代器指向的内容不能修改了吗？是的，但是，指向也不能修改了，这个该怎么办？
再搞一个 const 迭代器的封装——能行，但是太麻烦啦。
目前，我们能想到的最好的答案——类模板参数增加
//List.h 中
//增加一个模板参数实现 const 迭代器
template<class T, class Ref>
struct __list_iterator {
typedef list_node<T> Node;
typedef __list_iterator<T, Ref> Multi;
//构造
......
//解引用
Ref operator*() {
return _node->_data;
}
//其他
//后置 --
Multi operator--(int) {
Multi tmp(*this);
_node = _node->_prev;
return tmp;
}
......
};
//list类中
//使用类封装的迭代器
typedef __list_iterator<T, T&> iterator;
typedef __list_iterator<T, const T&> const_iterator;
//获得边界
iterator begin() {
//开始结点是哨兵位的后一结点
return _node->_next;
}
iterator end() {
//尾结点就是哨兵位结点
return _node;
}
const_iterator begin()const {
return _node->_next;
}
const_iterator end()const {
return _node;
}
......
我们增加的类模板参数 Ref 就可在实例化时用 T& 和 const T& 替代，实现两种不同的迭代器。同时注意，迭代器的类封装中要用 Multi 替代 __list_iterator<T>。最后，泛型化的打印函数就能够成功调用 const 迭代器了，
我们在上面考虑的链表类型是十分简单的内置类型 int ，为了加深理解，考虑一个自定义类型——二维坐标类 Pos
//test.cpp
//坐标
struct Pos {
int _row;
int _col;
//构造
Pos(int row = 0, int col = 0)
:_row(row)
, _col(col)
{}
};
void test02() {
my_list01::list<Pos> lt1;
//多参数的隐式类型转换构造 花括号
lt1.push_back({1, 1});
lt1.push_back({2, 2 });
lt1.push_back({3, 3 });
lt1.push_back({4, 4 });
//迭代器遍历
auto it = lt1.begin();
while (it != lt1.end()) {
//Pos 类型的成员访问该用 . 访问
//cout << (*it)._row << ";" << (*it)._col << endl;
cout << it->_row << ";" << it->_col << endl;
++it;
}
}
测试函数 test02() 是通不过的，因为在我们模拟实现的 list 中，迭代器是一个类，并非数据原生指针，所以用 -> 通不过，但是 . 可以通过。众所周知，自定义类型要使用运算符就要调用对应的函数，也就是重载对应的运算符。于是，我们重载这个 -> 。
//List.h
//再搞一个模板参数控制普通对象的指针
template<class T, class Ref, class Ptr>
//迭代器封装
struct __list_iterator {
typedef list_node<T> Node;
typedef __list_iterator<T, Ref, Ptr> Multi;
//重载 ->
Ptr operator->() {
return &_node->_data;
}
......
};
注意到 -> 的重载，它返回的是我们实例化类型 Pos 的指针，并非数据，所以我们要访问 Pos 类的成员变量时应该使用 it->->_row，其实质就是 it.operator->()->_row；但是我们访问时为了代码可读性，就只能用一个 it->_row 或者 it.operator->()->_row表示。
这样，当我们实例化的链表参数是自定义类型时，我们也可以使用 -> 调用它的成员变量。
其他成员函数
1.insert
//List.h 的 list 类中
//pos 位置前插入
iterator insert(iterator pos, const T& val) {
//构造一个新节点
Node* newnode = new Node(val);
//记录 pos 和 其前一个结点
Node* cur = pos._node;
Node* prev = cur->_prev;
//调整指向
newnode->_prev = prev;
prev->_next = newnode;
newnode->_next = cur;
cur->_prev = newnode;
//返回新节点的位置
return iterator(newnode);
//也可以像下面这么写，因为结点的指针能够通过构造函数构造一个 iterator，实质上就是隐式类型转换
//return newnode;
}
有了 insert 我们就可以修改尾插并写其他位置的插入和删除
2.头尾插入删除
//List.h list 类中
void push_back(const T& x) {
insert(end(), x);
}
//头插
void push_front(const T& x) {
insert(begin(), x);
}
//尾删
void pop_back() {
//删除的是哨兵位的前一个结点
erase(--end());
}
//头删
void pop_front() {
erase(begin());
}
——————————————————————————————————————————————————————————————————————————————————
//test.cpp
void test01() {
my_list01::list<int> lt1;
lt1.push_back(1);
lt1.push_back(2);
lt1.push_back(3);
lt1.push_back(4);
print(lt1);
//头插
lt1.push_front(0);
print(lt1);
//尾删
lt1.pop_back();
print(lt1);
//头删
lt1.pop_front();
print(lt1);
}
结果：
3.拷贝构造和多参数构造
我们先写一个链表为空时的初始化函数来优化前面写的构造函数。
//空链表的构造
void empty_init() {
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
}
//空链表构造
list() {
empty_init();
}
不写拷贝而使用默认拷贝构造时，进行的就是浅拷贝，这对迭代器的使用是好的，但是要用拷贝构造复制一个新链表，那这就不行了。
//拷贝构造
list(const list<T>& lt) {
//先搞一个哨兵位
empty_init();
//直接把数据尾插到新链表中去
for (auto& e : lt) {
push_back(e);
}
}
//多参数构造
list(initializer_list<T> il) {
//先搞一个哨兵位
empty_init();
//直接把数据尾插到新链表中去
for (auto& e : il) {
push_back(e);
}
}
//赋值重载 lt1 = lt2
list<T>& operator=(const list<T> lt) {
//避免自己给自己赋值
if (this != <) {
//先清理数据——打扫干净自己的屋子，再请客
clear();
//直接把数据尾插
for (auto& e : lt) {
push_back(e);
}
}
}
//再简化一下
void swap(list<T> lt) {
//交换哨兵位与大小
std::swap(_node, lt._node);
std::swap(_size, lt._size);
}
list<T>& operator=(list<T> lt) {
swap(lt);
return *this;
}
范围 for 中加& 预防 list 对象的类型为较大的对象（string、vector）等时出现不完整的尾插。
这样，我们就完成了 list 的简单模拟。
——————
仅仅是学习记录。