各位好友， 本期将开启 List（链表）----->模拟实现 ！
------->List 介绍 ：>
（1）. List 是可以在 任意位置进行 插入 与删除的序列式容器；
（2）. List 底层 ：> 双向带头循环 链表结构， 双向链表 内的每个元素 存储在 互不相同的独立结点中
------->在结点 中通过 指针 指向前一个元素 与后一个元素 ！
（3）. List 与其他序列式容器（array, vector）相比 List 在任意位置进行插入数据， 效率更高 ！
------->另外， 本期最难以理解的点 ：>封装 ----->多模板__迭代器（精华所在）
------->List 底层模拟 ---->代码如下 ：>
------->头文件 “List.h”
//List__底层模拟实现
//部分模拟简单实现
#include <iostream>
using std :: cout;
using std :: endl;
namespace UC
{
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)
{}
};
//封装迭代器
template<class T>
struct _list_iterator
{
typedef list_node<T> Node;
Node* _node;
_list_iterator(Node* node)
:_node(node)
{}
T& operator*()
{
return _node->_val;
}
//前置++
_list_iterator<T>& operator++()
{
_node = _node->_next;
return *this;
}
//后置++
_list_iterator<T> operator++(int)
{
_list_iterator<T> tamp(*this);
_node = _node->_next;
return tamp;
}
//布尔判断
bool operator!=(const _list_iterator<T>& it)
{
return _node != it._node;
}
bool operator==(const _list_iterator<T>& it)
{
return _node == it._node;
}
};
template<class T>
class list
{
typedef list_node<T> Node;
public:
typedef _list_iterator<T> iterator;
iterator begin()
{
return iterator(_head->_next);
}
iterator end()
{
return _head;
}
//创建哨兵位
list()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
}
void push_back(const T& x)
{
Node* tail = _head->_prev;
Node* newNode = new Node(x);
tail->_next = newNode;
newNode->_prev = tail;
newNode->_next = _head;
_head->_prev = newNode;
}
private:
Node* _head;
};
}为了方便好友们， 有更好的观感体验， 现附上 彩色代码图样 ：>
上述 尾插数据环节， 可进一步优化处理 ：>
-------->封装一个 insert（）函数
-------->可在后续环节 ----->实现 头插数据，任意位置 插入数据，做好准备 ！
-------->测试环节 “Test.cpp”
//测试
void test_01()
{
UC :: list<int> It;
It.push_back(21);
It.push_back(22);
It.push_back(23);
It.push_back(32);
It.push_back(37);
UC :: list<T> :: iterator it = It.begin();
while(it != It.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
int main()
{
test_01();
return 0;
}--------->测试环节 ：>
------->const 迭代器（啰嗦写法）
--------->
上述 const_iterator 与 iterator 有着大量重复 ！ --->因此， 多参数模板， 开始展露 铮铮傲骨 ！😊😊
--------->升级版__多参数模板 ----->封装迭代器 （重中之重）
//封装迭代器
//重难点
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)
{}
};
template<class T, class Ref, class Ptr>
struct _list_iterator
{
typedef list_node<T> Node;
typedef _list_iterator<T, T&, T*> iterator;
typedef _list_iterator<T, const T&, const T*> const_iterator;
typedef _list_iterator<T, Ref, Ptr> Self;
Node* _node;
_list_iterator(Node* node)
:_node(node)
{}
_list_iterator() {}
_list_iterator(const iterator& x)
:_node(x._node)
{}
//解引用
Ref operator*()
{
return _node->_val;
}
//解引用：>带有箭头的
Ptr operator->()
{
return &_node->_val;
}
//前置++
Self& operator++()
{
_node = _node->_next;
return *this;
}
//后置++
Self operator++(int)
{
Self tamp(*this);
_node = _node->_next;
return tamp;
}
//前置--
Self& operator--()
{
_node = _node->_prev;
return *this;
}
//后置--
Self operator--(int)
{
Self tamp(*this);
_node = _node->_next;
return tamp;
}
//布尔判断
bool operator!=(const Self& it) const
{
return _node = it._node;
}
bool operator==(const Self& it) const
{
return _node == it._node;
}
};为了方便好友们， 有更好的观感体验， 现附上 彩色代码图样 ：>
------->list_node 结构体
------->_list_iterator 迭代器__封装
--------->测试环节 ：>
------>list 域内 ：>
//list 类 ---->接口实现
template<class T, class Ref, class Ptr>
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 iterator(_head->_next);
}
iterator end()
{
return _head;
}
const_iterator begin() const
{
return iterator(_head->_next);
}
const_iterator end() const
{
return _head;
}
list()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
}
//此处封装的好处，其他接口可以使用
//比如，头删 尾删 任意位置删除数据
~list()
{
empty_list();
delete _head;
_head = nullptr;
}
//尾插数据 ----->第一种
void push_back(const T& x)
{
Node* tail = _head->_prev;
Node* newNode = new Node(x);
tail->_next = newNode;
newNode->_prev = tail;
newNode->_prev = _head;
_head->_next = newNode;
}
//尾插数据 --->第二种
//建议使用第二种， 带有封装性
//可以用在 尾插数据， 任意位置插入数据上
void push_back(const T& x)
{
insert(end(), x);
}
iterator insert(iterator pos, const T& x)
{
Node* cur = pos._node;
Node* Prev = cur->_prev;
Node* newNode = new Node(x);
Prev->_next = newNode;
newNode->_next = cur;
cur->_prev = newNode;
newNode->_prev = Prev;
++_size;
return newNode;
}
iterator earse(iterator pos)
{
Node* cur = pos._node;
Node* next = cur->_next;
Node* Prev = cur->_prev;
Prev->_next = next;
next->_prev = Prev;
delete cur;
--_size;
return next;
}
void empty_list()
{
iterator it = begin();
//此处循环遍历先保存 it 很重要
//设计到一个大的问题， 迭代器失效， 会放在下一期讲解
while(it != end())
{
it = earse(it);
}
_size = 0;
}
size_t size() const
{
return _size;
}
private:
size_t _size;
Node* _head;
};为了方便好友们， 有更好的观感体验， 现附上 彩色代码图样 ：>
各位好友， 本期内容 已完结 ！
下一期 继续推进 ------->List（链表）解析环节 ！ “敬请期待 ！😊😊