list的模拟实现
相信大家看完我的这篇有关list使用的博客cpp–list的介绍及使用，一看就会！之后对于list类的基本使用有了一定的了解，如果大家想对于list的底层有所了解，就可以看看我这篇list的模拟实现！
在这之前我建议大家先掌握以下内容
cpp–vector的介绍及其使用，超详细，一看就会！
C++中的string类使用,看我这一篇就够了!
如果已经对上述使用有所了解，可以看看一下的模拟实现，以便对底层有所了解
cpp–vector的模拟实现,注释超详细！
cpp实战项目—string类的模拟实现
list.h
// 防止头文件被重复包含
#pragma once
// 定义命名空间 lis
namespace lis
{
// 定义双向链表节点的结构体模板
template<class T>
struct list_node
{
T _data; // 节点存储的数据
list_node<T>* _next; // 指向下一个节点的指针
list_node<T>* _prev; // 指向前一个节点的指针
// 节点的构造函数，使用默认参数初始化数据，前后指针初始化为空
list_node(const T& x = T())
:_data(x)
, _next(nullptr)
, _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)
{
}
// 前置自增运算符重载，将迭代器指向下一个节点，并返回自身引用
self& operator++()
{
_node = _node->_next;
return *this;
}
// 前置自减运算符重载，将迭代器指向前一个节点，并返回自身引用
self& operator--()
{
_node = _node->_prev;
return *this;
}
// 后置自增运算符重载，先保存当前迭代器状态，再将迭代器指向下一个节点，最后返回保存的状态
self operator++(int)
{
self temp(*this);
_node = _node->_next;
return temp;
}
// 后置自减运算符重载，先保存当前迭代器状态，再将迭代器指向前一个节点，最后返回保存的状态
self operator--(int)
{
self temp(*this);
_node = _node->_prev;
return temp;
}
// 解引用运算符重载，返回当前节点存储的数据的引用
Ref operator*()
{
return _node->_data;
}
// 箭头运算符重载，返回当前节点存储的数据的指针
Ptr operator->()
{
return &_node->_data;
}
// 不等于运算符重载，判断两个迭代器是否指向不同的节点
bool operator!=(const self& s)
{
return _node != s._node;
}
// 等于运算符重载，判断两个迭代器是否指向相同的节点
bool operator==(const self& s)
{
return _node == s._node;
}
};
// 定义双向链表类模板
template<class T>
class list
{
typedef list_node<T> Node; // 重命名节点类型，方便后续使用
public:
typedef __list_iterator<T, T&, T*> iterator; // 定义普通迭代器类型
typedef __list_iterator<T, const T&, const T*> const_iterator; // 定义常量迭代器类型
// 返回指向链表第一个节点的普通迭代器
iterator begin()
{
return _head->_next;
}
// 返回指向链表尾节点（哨兵节点）的普通迭代器
iterator end()
{
return _head;
}
// 返回指向链表第一个节点的常量迭代器
const_iterator begin() const
{
return _head->_next;
}
// 返回指向链表尾节点（哨兵节点）的常量迭代器
const_iterator end() const
{
return _head;
}
// 初始化链表，创建哨兵节点，将其前后指针都指向自身，链表大小初始化为 0
void empty_init()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
// 链表的默认构造函数，调用 empty_init 进行初始化
list()
{
empty_init();
}
// 拷贝构造函数，先初始化链表，再遍历另一个链表，将其元素依次插入到当前链表中
list(const list<T>& lt)
{
empty_init();
for (auto e : lt)
{
push_back(e);
}
}
// 交换两个链表的内容，包括头指针和链表大小
void swap(list<T>& x)
{
std::swap(_head, x._head);
std::swap(_size, x._size);
}
// 赋值运算符重载，通过交换两个链表的内容实现赋值
list<T>& operator=(list<T>& lt)
{
swap(lt);
return *this;
}
// 析构函数，先清空链表，再删除哨兵节点，最后将头指针置为 nullptr
~list()
{
clear();
delete _head;
_head = nullptr;
}
// 清空链表，使用迭代器遍历链表，依次删除每个节点
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}
// 删除指定位置的节点，并返回指向下一个节点的迭代器
iterator erase(iterator pos)
{
Node* cur = pos._node; // 当前要删除的节点
Node* back = cur->_next; // 当前节点的下一个节点
Node* front = cur->_prev; // 当前节点的前一个节点
back->_prev = front; // 调整指针，跳过当前节点
front->_next = back; // 调整指针，跳过当前节点
--_size; // 链表大小减 1
return iterator(back); // 返回指向下一个节点的迭代器
}
// 在指定位置之前插入一个新节点，并返回指向新节点的迭代器
iterator insert(iterator pos, const T& val) // 在 pos 位置之前插入 val
{
Node* cur = pos._node; // 当前位置的节点
Node* newnode = new Node(val); // 创建新节点
Node* front = cur->_prev; // 当前节点的前一个节点
//Node* back = cur->_next;
front->_next = newnode; // 调整指针，将新节点插入到 front 和 cur 之间
newnode->_prev = front; // 调整指针，将新节点插入到 front 和 cur 之间
newnode->_next = cur; // 调整指针，将新节点插入到 front 和 cur 之间
cur->_prev = newnode; // 调整指针，将新节点插入到 front 和 cur 之间
++_size; // 链表大小加 1
return iterator(newnode); // 返回指向新节点的迭代器
}
// 在链表尾部插入一个新元素，调用 insert 函数在尾节点之前插入
void push_back(const T& x)
{
insert(end(), x);
}
// 在链表头部插入一个新元素，调用 insert 函数在头节点之后插入
void push_front(const T& x)
{
insert(begin(), x);
}
// 删除链表头部的元素，调用 erase 函数删除头节点之后的节点
void pop_front()
{
erase(begin());
}
// 删除链表尾部的元素，调用 erase 函数删除尾节点之前的节点
void pop_back()
{
erase(--end());
}
// 返回链表的大小
size_t size()
{
return _size;
}
private:
Node* _head; // 链表的头指针，指向哨兵节点
size_t _size; // 链表的大小
};
// 测试链表的基本功能，插入元素，遍历链表并输出元素
void test_list1()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
// 使用迭代器遍历链表并输出元素
list<int>::iterator it = lt.begin();
while (it != lt.end())
{
std::cout << *it << " ";
++it;
}
std::cout << std::endl;
// 使用范围 for 循环遍历链表并输出元素
for (auto e : lt)
{
std::cout << e << " ";
}
}
// 测试链表的拷贝构造和赋值运算符，创建链表，拷贝链表，赋值链表，分别遍历输出元素
void test_list2()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
list<int> lt1(lt); // 拷贝构造
// 遍历输出原链表的元素
for (auto e : lt)
{
std::cout << e << " ";
}
std::cout << std::endl;
// 遍历输出拷贝链表的元素
for (auto e : lt1)
{
std::cout << e << " ";
}
std::cout << std::endl;
list<int> lt2;
lt2.push_back(10);
lt2.push_back(200);
lt2.push_back(30);
lt2.push_back(40);
lt2.push_back(50);
lt1 = lt2; // 赋值操作
// 遍历输出赋值后链表的元素
for (auto e : lt1)
{
std::cout << e << " ";
}
std::cout << std::endl;
// 遍历输出另一个链表的元素
for (auto e : lt2)
{
std::cout << e << " ";
}
std::cout << std::endl;
}
// 定义一个结构体 AA，包含两个整型成员变量
struct AA
{
AA(int a1 = 0, int a2 = 0)
:_a1(a1)
, _a2(a2)
{
}
int _a1; // 成员变量 a1
int _a2; // 成员变量 a2
};
// 测试链表存储自定义结构体的功能，插入结构体元素，使用迭代器遍历链表并输出结构体成员
void test_list3()
{
list<AA> lt;
lt.push_back(AA(1, 1));
lt.push_back(AA(2, 2));
lt.push_back(AA(3, 3));
list<AA>::iterator it = lt.begin();
while (it != lt.end())
{
// 使用箭头运算符输出结构体成员
std::cout << it->_a1 << " " << it->_a2 << std::endl;
// 显式调用箭头运算符重载函数输出结构体成员
//std::cout << it.operator->()->_a1 << " " << it.operator->()->_a2 << std::endl;
// 编译器会特殊处理，省略一个 -> 以提高可读性
++it;
}
std::cout << std::endl;
}
// 泛型函数，用于打印容器中的元素，使用常量迭代器遍历容器并输出元素
template<typename Container>
void print_container(const Container& con)
{
// 使用 typename 告诉编译器 Container::const_iterator 是一个类型
typename Container::const_iterator it = con.begin();
while (it != con.end())
{
// const 迭代器不能修改元素
//*it = 1;
std::cout << *it << " ";
++it;
}
std::cout << std::endl;
// 使用范围 for 循环遍历容器并输出元素
/*for (auto e : con)
{
std::cout << e << " ";
}
std::cout << std::endl;*/
}
// 测试泛型打印函数，分别使用不同类型的链表和向量容器进行测试
void test_list4()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
// 调用泛型打印函数打印整型链表
print_container(lt);
list<std::string> lt1;
lt1.push_back("11111");
lt1.push_back("11111");
lt1.push_back("11111");
lt1.push_back("11111");
lt1.push_back("11111");
// 调用泛型打印函数打印字符串链表
print_container(lt1);
std::vector<std::string> v;
v.push_back("2222");
v.push_back("2222");
v.push_back("2222");
v.push_back("2222");
// 调用泛型打印函数打印字符串向量
print_container(v);
}
// 测试链表的插入、删除、头插、头删、尾删等操作，并使用泛型打印函数输出结果
void test_list5()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
list<int>::iterator it = lt.begin();
lt.erase(++it); // 删除第二个元素
lt.insert(it, 100); // 在当前位置插入元素 100
print_container(lt); // 打印链表
lt.push_front(-10); // 在链表头部插入元素 -10
print_container(lt); // 打印链表
lt.pop_front(); // 删除链表头部元素
print_container(lt); // 打印链表
lt.pop_back(); // 删除链表尾部元素
print_container(lt); // 打印链表
}
}
test.cpp
#include <iostream>
#include <string>
#include <vector>
#include <list>
using namespace std;
#include "list.h"
int main()
{
lis::test_list4();
return 0;
}