C++ STL：从零开始模仿实现 list 容器
引言C++ 标准模板库(STL)中的 list 是一个双向链表容器，它提供了高效的插入和删除操作。本文将领导你一步步实现一个简化版的 list 容器，帮助你深入理解其底层原理和设计头脑。
1. 疑难点解析
1.1 迭代器类为什么设置三个模版参数？
为了区分 list 的 const类 和 平凡类 ，我们都知道 const类 的变量是不能修改内部值的，就算用指针也不行。而我们的迭代器也恰好是在模仿指针的举动，所以指针不能修改 const类 变量，我们的迭代器也不行。
为了区分对 const类 的 list（只读） 和 平凡类list（可读可写）的区别，我们需要另一个能做到对容器只读不写的 const类迭代器 ，我们最好的方式便是写两个基本一样的迭代器类（一份供平凡类list调用的平凡迭代器类，一份供const类list调用的const类的迭代器）。
但如许既欠好修改又欠好调试，而在有了模版之后，我们便可以将写两份代码的工作交给编译器去实现（俗称模版实例化，根据传入参数差别，模版可以实例化为多个差别类），所以我们就多加了一个模版参数Ref，根据 list 传入的范例差别，从而区分实例化为 const类 的迭代器照旧 平凡类 ，而又因为我们迭代器可以用 * 和 -> 两种操作符访问，且两操作符的返回值又各差别，所以 迭代器模版 又多加一个 Ptr ，以区分 ->运算符重载函数 对 const类 和 平凡类 的访问。
2. 完备源码
#include<assert.h>
namespace dza {
// 惯例：当成员变量和成员函数全部是公有的时候，一般用struct
// struct 与 class没有区别
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>
//struct list_iterator {
// typedef list_node<T> Node;
// // 定义一个迭代器Self
// typedef list_iterator<T> Self;
// Node* _node;
// list_iterator(Node* node)
// :_node(node)
// {}
// // 解引用的重载
// T& operator*()
// {
// return _node->_data;
// }
// // 公共函数。域内都可以使用
// T* operator->()
// {
// return &_node->_data;
// }
// // 迭代器的实现
// Self& operator++()
// {
// _node = _node->_next;
// return *this;
// }
// Self& operator--()
// {
// _node = _node->_prev;
// return *this;
// }
// Self operator++(int)
// {
// Self tmp(*this);
// _node = _node->_next;
// return tmp;
// }
// Self operator--(int)
// {
// Self tmp(*this);
// _node = _node->_prev;
// return tmp;
// }
// bool operator!=(const Self& s)
// {
// return _node != s._node;
// }
// bool operator==(const Self& s)
// {
// return _node == s._node;
// }
//};
// 模板里面的多参数
template<class T,class Ref,class Ptr>
struct list_iterator {
typedef list_node<T> Node;
// 定义一个迭代器Self
typedef list_iterator<T,Ref,Ptr> Self;
Node* _node;
list_iterator(Node* node)
:_node(node)
{}
// 解引用的重载
Ref operator*()
{
return _node->_data;
}
// 公共函数。域内都可以使用
Ptr operator->()
{
return &_node->_data;
}
// 迭代器的实现
Self& operator++()
{
_node = _node->_next;
return *this;
}
Self& operator--()
{
_node = _node->_prev;
return *this;
}
Self operator++(int)
{
Self tmp(*this);
_node = _node->_next;
return tmp;
}
Self operator--(int)
{
Self tmp(*this);
_node = _node->_prev;
return tmp;
}
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> iterator;
// typedef list_const_iterator<T> iterator;
// 这个类要你自己实现
// or
// list_iterator要有三个模板参数，才能用下面的迭代器，并且const是加在后面的，而不是前面
typedef list_iterator<T, T&, T*> iterator;
typedef list_iterator<T, const T&, const T*> const_iterator;
iterator begin()
{
return iterator(_head->_next);
}
iterator end()
{
return 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;
_size = 0;
}
list()
{
empty_init();
}
// it2(it1) 的模拟实现
list(const list<T>& It)
{
empty_init();
for (auto& e : It)
{
push_back(e);
}
}
// it2 = it3 的模拟实现
list<T>& operator=(list<T> It)
{
swap(It);
return *this;
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
void swap(list<T>& tmp)
{
std::swap(_head, tmp._head);
std::swap(_size, tmp._size);
}
void clear()
{
auto it = begin();
while (it != end())
{
it = erase(it);
// 删除链表中的所有节点
// erase在删除的时候会自动+1
}
}
// it1(3,1)的模拟实现。往list中插入3个1
list(size_t n, const T& val = T())
{
// 清空新链表
empty_init();
// 依次插入
for (size_t i = 0; i < n; i++)
{
push_back(val);
}
}
void push_back(const T& x)
{
Node* new_node = new Node(x);// 指向待插入数据的指针
Node* tail = _head->_prev;// 头结点的上一个节点。也就是链表的最后一个节点
tail->_next = new_node;// 最后一个节点的 next 指向 new_node
new_node->_prev = tail;// new_node 的 prev 指向最后一个节点
new_node->_next = _head;// 由于 new_node 成为最后一个节点。所以更新链表中头结点的下一个指针
_head->_prev = new_node;// 头节点的 prev 指向 new_node
// // 新版本
// insert(end(),x);
}
void push_front(const T& x)
{
insert(begin(), x);
}
void pop_front()
{
erase(begin());
}
void pop_back()
{
erase(--end());
}
iterator insert(iterator pos, const T& val)
{
// cur 需要插入新数据的节点
Node* cur = pos._node;
// newnode 需要插入的新数据
Node* newnode = new Node(val);
// 需要插入新数据节点的上一个节点
Node* prev = cur->_prev;
// list是链表，所以想要头插，就只需要改变上一个节点的next，下一个节点的prev
prev->_next = newnode;// 上一个节点的 next 换成 newnode
newnode->_prev = prev;// 新数据指向上一个节点的指针 prev 指向上一个节点
newnode->_next = cur;// 新数据的下一个节点指向节点的原数据
cur->_prev = newnode;// 原节点的 prev 指向新数据
++_size;// 改变整个链表的长度
// return iterator 通常表示一个函数返回一个 迭代器（iterator） 对象
// 它指向某个容器（如 std::vector、std::list、std::map 等）中的特定元素。
return iterator(newnode);// 返回新数据
}
iterator erase(iterator pos)
{
// 先判断是不是空链表
assert(pos != end());
Node* del = pos._node;// 指向待删除数据的节点的指针
Node* next = del->_next;// 指向待删除数据节点的下一个节点
Node* prev = del->_prev;// 指向待删除数据节点的上一个节点
prev->_next = next;// 上一个节点的 next 指针指向下一个节点
next->_prev = prev;// 下一个节点的 prev 指针指向上一个节点
delete del;// 删除当前的节点
--_size;// 减小整个数组的size
// 返回待删除节点的下一个节点
return iterator(next);
}
private:
Node* _head;
size_t _size;
};
// 通用的 swap 模版。所有的类型都能用
template <class T>
void swap(T& a, T& b)
{
T c(a);
a = b;
b = c;
}
// 特化的 list_swap 版本。仅适用于 list<T>类型 使用
// 特化的模版函数可以提高程序的运行效率
template<class T>
void swap(list<T>& a, list<T>& b)
{
a.swap(b);
}
}
3. 完备测试代码
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
#include<list>
#include<vector>
#include<algorithm>
#include"list.h"
//#include"teacher's list.h"
class Pos
{
public:
int _row;
int _col;
Pos(int row = 0, int col = 0)
:_row(row)
, _col(col)
{
cout << "Pos(int row, int col)" << endl;
}
Pos(const Pos& p)
:_row(p._row)
, _col(p._col)
{
cout << "Pos(const Pos& p)" << endl;
}
};
void test_list01()
{
dza::list<int> lt1;
lt1.push_back(1);
lt1.push_back(2);
lt1.push_back(3);
lt1.push_back(4);
for (auto& e : lt1)
{
cout << e << " ";
}
cout << endl;
auto it1 = lt1.begin();
while (it1 != lt1.end())
{
cout << *it1++ << " ";
}
cout << endl;
}
void test_list02()
{
dza::list<int> lt1;
lt1.push_back(1);
lt1.push_back(1);
lt1.push_back(1);
lt1.push_back(1);
dza::list<int>::iterator it1 = lt1.begin();
while (it1 != lt1.end())
{
*it1 = 2;
cout << *it1 << " ";
++it1;
}
cout << endl;
for (auto e : lt1)
{
cout << e << " ";
}
cout << endl;
}
void test_list03()
{
dza::list<Pos> lt2;
// _row构造次数 == 0，_row构造次数 r1++
// _col构造次数 == 0，_col构造次数 c1++
Pos p1(1, 1);
lt2.push_back(p1);// r1++,c1++
lt2.push_back(Pos(2, 2)); // r1++,c1++
// {}隐式类型转换
lt2.push_back({ 3,3 });// r1++,c1++
// 动用4次_row构造。4次_col构造
dza::list<Pos>::iterator it2 = lt2.begin();
while (it2 != lt2.end())
{
//cout << (*it2)._row << ":" << (*it2)._col << endl;
// 为了可读性，特殊处理，省略了一个->
// 两种读取方式。打印两次
cout << it2->_row << ":" << it2->_col << endl;
cout << it2.operator->()->_row << ":" << it2.operator->()->_col << endl;
++it2;
}
cout << endl;
}
void test_list04()
{
dza::list<int> l1;
l1.push_back(1);
l1.push_back(2);
l1.push_back(3);
l1.push_back(4);
for (auto& e : l1)
{
cout << e << " ";
}
cout << endl;
auto it1 = l1.begin();
int x = 0;
l1.pop_back();
while (it1 != l1.end())
{
cout << *it1++ << " ";
}
cout << endl;
// 头删完成之后需要更新一下it1。否则it1指向原来的位置，为空的迭代器
l1.pop_front();
it1 = l1.begin();
while (it1 != l1.end())
{
cout << *it1++ << " ";
}
cout << endl;
l1.push_front(0);
l1.push_front(1);
for (auto& e : l1)
{
cout << e << " ";
}
cout << endl;
}
void test_list05()
{
dza::list<int> l1;
l1.push_back(1);
l1.push_back(2);
l1.push_back(3);
l1.push_back(4);
dza::list<int> l2(l1);
for (auto& e : l1)
{
cout << e << " ";
}
cout << endl;
for (auto& e : l2)
{
cout << e << " ";
}
cout << endl;
dza::list<int> l3(3,1);
for (auto& e : l3)
{
cout << e << " ";
}
cout << endl;
l3.clear();
for (auto& e : l3)
{
cout << e << " ";
}
cout << endl;
}
void test_list06()
{
dza::list<int> l1;
l1.push_back(1);
l1.push_back(2);
l1.push_back(3);
l1.push_back(4);
for (auto& e : l1)
{
cout << e << " ";
}
cout << endl;
auto it1 = l1.begin();
it1++;
it1++;
l1.insert(it1, 30);
for (auto& e : l1)
{
cout << e << " ";
}
cout << endl;
l1.erase(l1.begin());
for (auto& e : l1)
{
cout << e << " ";
}
cout << endl;
}
int main()
{
test_list06();
return 0;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]