代码仓库：
list模拟实现
list源码
数据结构——双向链表
🍇1. 节点结构体
源码的list是双向带头循环链表，所以我们定义两个节点，一个指向下一个，一个指向前一个
template<class T>
struct list_node
{
list_node<T>* _next; //指向下一个节点
list_node<T>* _prev; //指向前一个
T _val; //数据
list_node(const T& val = T())
:_next(nullptr)
, _prev(nullptr)
, _val(val)
{}
};
🍈2. list成员
list类包含一个_head头节点，然后为了方便查出当前有多少个节点，还能多定义一个_size
template<class T>
class list
{
typedef list_node<T> Node;
public:
// 各类操作方法
//...
private:
Node* _head;
size_t _size;
}
🍉3. 迭代器模板
源码的迭代器设置了三个模板参数：
-
T：表示指向list节点的数据类型 -
Ref：迭代器的引用类型，通常情况为T&，但也可表示const -
Ptr：表示指向节点的指针类型，通常情况下为T*，但也可表示const迭代器，避免代码的冗余
对于string或者是vector的迭代器，对其解引用就可以表示当前的数据；而list是链表，解引用之后表示的一个节点，所以相对会麻烦一点
//Ref T& / const T&
//Ptr T* / const T*
template<class T, class Ref, class Ptr>
struct __list_iterator
{
typedef __list_iterator<T, Ref, Ptr> self;
typedef list_node<T> Node;
Node* _node;
__list_iterator(Node* node)
:_node(node)
{}
Ref operator*()
{
return _node->_val;
}
Ptr operator->()
{
return &_node->_val;
}
//前置++
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& lt)
{
return _node != lt._node;
}
bool operator==(const self& lt)
{
return _node == lt._node;
}
};
Tips:
迭代器并没有写拷贝构造，那么就是默认浅拷贝。这无关影响，因为我们就是希望通过这个迭代器找到这个节点
void test1() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); //浅拷贝 list<int>::iterator it = lt.begin(); while(it!=lt.end()) { cout<< *it << " "; ++it; } cout<<endl; }这里没有奔溃也是因为迭代器没有写析构函数，迭代器只是负责访问，并不负责管理
🍊4. 迭代器
const const_iterator begin() const
{
//单参数构造函数 隐式类型转换
return _head->_next;
}
const const_iterator end() const
{
return _head;
}
iterator begin()
{
//单参数构造函数 隐式类型转换
return _head->_next;
}
iterator end()
{
return _head;
}
🍋5. 插入删除操作
🍌5.1 insert & erase
这里插入删除操作之后，也会存在当前迭代器失效，所以传修改完毕之后的迭代器位置
iterator insert(iterator pos, const T& x)
{
Node* cur = pos._node;
Node* tmp = new Node(x);
Node* prev = cur->_prev;
prev->_next = tmp;
tmp->_next = cur;
cur->_prev = tmp;
tmp->_prev = prev;
++_size;
return tmp;
}
iterator erase(iterator pos)
{
assert(pos != end());
Node* cur = pos._node;
Node* next = cur->_next;
Node* prev = cur->_prev;
prev->_next = next;
next->_prev = prev;
delete cur;
--_size;
return next;
}
🍌5.2 push_back & push_front & pop_back & pop_front
写了指定位置插入删除之后，直接复用即可
void push_back(const T& x)
{
insert(end(), x);
}
void push_front(const T& x)
{
insert(begin(), x);
}
void pop_back()
{
Node* tail = _head->_prev;
erase(tail);
}
void pop_front()
{
erase(begin());
}
🍍6. 构造 & 析构 & 拷贝构造
查看源码发现list的构造和析构都采用了复用
清空链表
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
//_size = 0;
}
复用
void empty_init()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
list()
{
empty_init();
}
list(const list<T>& lt)
{
empty_init();
for (auto& e : lt)
{
push_back(e);
}
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
🥭7. 赋值重载
这里还是采用现代的写法，交换完毕之后，自动调用析构函数
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}
list<T>& operator=(list<T> lt)
{
swap(lt);
return *this;
}
🍓8. 获取元素个数
size_t size()
{
return _size;
}
以上就是list的基本功能实现，实质上就是双向带头循环链表，迭代器这块有点复杂。文章来源：https://www.toymoban.com/news/detail-618438.html
那本期分享就到这里咯，我们下期再见，如果还有下期的话。文章来源地址https://www.toymoban.com/news/detail-618438.html
到了这里，关于C++ ——STL容器【list】模拟实现的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
![[ C++ ] STL---list的模拟实现](https://imgs.yssmx.com/Uploads/2024/04/844850-1.gif)
![C++ [STL之list模拟实现]](https://imgs.yssmx.com/Uploads/2024/02/491169-1.png)
