在 C++ 的 STL（标准模板库）中，list 是一个十分重要的容器，它就像一个灵活的弹簧，可以在任意位置快速地插入和删除元素。今天，就让我们一起走进 list 的世界，去探索它的奥秘。
list 的节点 —— ListNode
template<class T>
struct ListNode
{
ListNode(const T& val = T())
:_pPre(nullptr),
_pNext(nullptr),
_val(val)
{}
ListNode<T>* _pPre;
ListNode<T>* _pNext;
T _val;
};
list 的基础是节点，就像一串项链上的珠子。代码中的 ListNode 就承载着这样的角色。每个节点都有一个前驱指针 _pPre、一个后继指针 _pNext 和一个存储数据的 _val。它们就像是珠子的连接线，将一个个数据串联起来，构成了 list 的主体。当我们创建一个节点时，它就像一颗独立的珠子，等待被加入到项链中。
list 的 “导览员” —— ListIterator
//List的迭代器类
template<class T, class Ref, class Ptr>
struct ListIterator
{
typedef ListNode<T>* PNode;
typedef ListIterator<T, Ref, Ptr> Self;
//成员函数
ListIterator(PNode pNode = nullptr)
:_pNode(pNode)
{}
ListIterator(const Self& l)//怎么实现拷贝
{
_pNode = l._pNode;
}
T& operator*()
{
return _pNode->_val;
}
//T* operator->()//存疑
//{
// return &_pNode->_val;
//}
Self& operator++()
{
_pNode= _pNode->_pNext;
return *this;
}
Self operator++(int)
{
Self tmp(*this);
_pNode = _pNode->_pNext;
return tmp;
}
Self& operator--()
{
_pNode = _pNode->_pPre;
return *this;
}
Self& operator--(int)
{
Self tmp(*this);
_pNode = _pNode->_pPre;
return tmp;
}
bool operator!=(const Self& l)
{
return _pNode != l._pNode;
}
bool operator==(const Self& l)
{
return _pNode == l._pNode;
}
//成员对象
PNode _pNode;
};
有了节点，我们还需要一个 “导览员” 来带我们游览整个 list，这就是迭代器 ListIterator。它就像是我们手中的一根细棒，可以指向 list 中的任意一个节点，让我们能够方便地访问和操作元素。
构造函数 ：它接受一个节点指针作为参数，默认指向空。这就像我们在开始游览之前，先确定了出发点。
拷贝构造函数 ：当遇到一个已经存在的迭代器时，我们可以通过拷贝它的方式，快速地获得一个指向相同节点的迭代器。这就好比看到朋友手中有一个很好的导览路线，我们直接复制过来一样。
解引用操作符（operator*） ：通过这个操作符，我们可以轻松地获取当前节点所存储的值。这相当于在游览过程中，我们停下脚步，仔细观察手中的珠子。
自增自减操作符（operator++、operator–） ：这两个操作符就像是我们的双脚，可以带着我们在 list 的项链上向前或向后移动，指向下一个或前一个节点。
比较操作符（operator!=、operator==） ：它们可以帮助我们判断两个迭代器是否指向同一个节点。这就好比在不同的游览路线中，我们可以比较是否来到了同一个景点。
list 的核心 —— list 类
现在，我们迎来了主角 —— list 类。它就像是一个精心编织的项链，将众多节点串联起来，并提供了一系列方法让我们能够灵活地操作它。
//list类
template<class T>
class list
{
typedef ListNode<T> Node;
typedef Node* PNode;
public:
typedef ListIterator<T, T&, T*> iterator;
typedef ListIterator<T, const T&, const T&> const_iterator;
public:
///
// List的构造
list()
{
CreateHead();
}
list(int n, const T& value = T())
{
CreateHead();
PNode cur = _pHead;
while (n--)
{
PNode next = new Node(value);
cur->_pNext = next;
next->_pPre = cur;
cur = next;
_size++;
}
cur->_pNext = _pHead;
_pHead->_pPre = cur;
}
template <class Iterator>
list(Iterator first, Iterator last)
{
CreateHead();
PNode cur = _pHead;
while (first != last)
{
PNode next = new Node(*first);
cur->_pNext = next;
next->_pPre = cur;
cur = next;
first++;
_size++;
}
cur->_pNext = _pHead;
_pHead->_pPre = cur;
}
list(const list<T> &l)
{
CreateHead();
for(auto &a:l)
{
push_back(a);
}
}
list<T>& operator=(const list<T> l)
{
CreateHead();
swap(l);
return *this;
}
~list()
{
clear();
delete _pHead;
_pHead = nullptr;
}
///
// List Iterator
iterator begin()
{
return _pHead->_pNext;
}
iterator end()
{
return _pHead;
}
const_iterator begin()const
{
return _pHead->_pNext;
}
const_iterator end()const
{
return _pHead;
}
///
// List Capacity
size_t size()const
{
return _size;
}
bool empty()const
{
return _size == 0;
}
//
// List Access
T& front()
{
return _pHead->_pNext->_val;
}
const T& front()const
{
return _pHead->_pNext->_val;
}
T& back()
{
return _pHead->_pPre->_val;
}
const T& back()const
{
return _pHead->_pPre->_val;
}
// List Modify
void push_back(const T& val)
{
insert(end(), val);
}
void pop_back() {
erase(--end());
}
void push_front(const T& val) {
insert(begin(), val);
}
void pop_front() {
erase(begin());
}
// 在pos位置前插入值为val的节点
iterator insert(iterator pos, const T& val)
{
PNode n = new Node(val);
PNode pre = pos._pNode->_pPre;
pre->_pNext = n;
n->_pPre = pre;
n->_pNext = pos._pNode;
pos._pNode->_pPre = n;
_size++;
return n;
}
// 删除pos位置的节点，返回该节点的下一个位置
iterator erase(iterator pos)
{
PNode pre = pos._pNode->_pPre;
PNode next = pos._pNode->_pNext;
delete pos._pNode;
pre->_pNext = next;
next->_pPre = pre;
_size--;
return next;
}
void clear()
{
PNode cur = _pHead->_pNext;
while (cur != _pHead)
{
PNode next = cur->_pNext;
delete cur;
cur = next;
}
_pHead->_pNext = _pHead;
_pHead->_pPre = _pHead;
_size = 0;
}
void swap(list<T>& l)
{
std::swap(_pHead, l._pHead);
std::swap(_size, l._size);
}
//void print()
//{
// for (auto c : *this)
// {
// cout << c << " ";
// }
// cout << endl;
//}
private:
void CreateHead()
{
_pHead = new Node;
_pHead->_pNext = _pHead;
_pHead->_pPre = _pHead;
_size = 0;
}
PNode _pHead;
size_t _size;
};
};
构造函数
默认构造函数会创建一个头节点 _pHead，它是一个特殊的节点，不存储实际数据，但起到了标记项链开头和结尾的作用。这就像我们在开始制作项链时，先打了个结。
可以指定元素个数和初始值来构造 list。这就像我们已经有了设计图，知道要制作多少颗珠子以及它们的颜色，于是按照这个设计直接把珠子串起来。
还可以从一个范围（通过迭代器指定开始和结束位置）来构造 list。这就像是我们从一个现成的珠子堆中，挑选
出一部分珠子，按照顺序串成项链。
拷贝构造函数能够复制一个已有的 list。这就好比看到了一件精美的项链作品，我们想模仿着制作一个一模一样的。
赋值操作符（operator=） ：它通过 “拷贝 - 交换” 技术，先创建一个临时的 list，再与当前 list 进行交换。这就像我们先按照别人的项链样式做好一个新项链，然后把自己的旧项链换掉。
析构函数 ：在 list 不再被需要时，析构函数会负责清理内存，删除所有节点，并释放头节点。这是在我们结束了项链的使用后，把它拆解，回收材料的过程。
迭代器相关操作
begin() 和 end() 方法分别返回指向 list 第一个节点和头节点（代表结束位置）的迭代器。这就像我们在游览项链时，确定了起点和终点。
const_iterator 版本的 begin() 和 end() 方法可以让我们在不修改 list 的情况下进行遍历，就像是我们戴着白手套，小心翼翼地观察项链上的珠子，而不去改变它们。
容量相关操作
size() 方法能够返回 list 当前的元素个数。这让我们可以清楚地知道项链上有多少颗珠子。
empty() 方法用于判断 list 是否为空，返回一个布尔值。这就像在检查项链是否已经断开，里面是否还有珠子。
元素访问操作
front() 和 back() 方法分别返回 list 第一个和最后一个元素的引用。这相当于我们直接拿起项链的开端或末端的珠子，查看它的模样。
修改操作
push_back() 和 pop_back() 方法用于在 list 的尾部添加或删除元素。这就像我们在项链的末端添加或取下一颗珠子。
push_front() 和 pop_front() 方法则是在 list 的头部进行添加或删除操作。这类似于我们在项链的开头位置进行珠子的增减。
insert() 方法可以在指定位置前插入一个元素。这就好比我们在项链的某个特定位置插入一颗新的珠子，需要调整相邻珠子的连接关系。
erase() 方法用于删除指定位置的元素，并返回下一个元素的位置。这就像我们在项链上取下一颗珠子后，要把剩下的珠子重新连接起来，并且告诉我们接下来的位置在哪里。
clear() 方法会清除 list 中的所有元素，将项链完全拆解，只剩下头节点。这通常在我们想要重新利用这条项链，重新设计样式时使用。
swap() 方法可以快速地交换两个 list 的内容。这就像我们把两条项链的珠子序列互换，但项链本身的结构（如头节点）保持不变。
结尾
通过以上对 list 的各个组成部分以及其成员函数的详细介绍（虽然这里的代码实现可能与 STL 中的 list 有些许不同，只是起到模拟作用），我们对 list 的工作原理和使用方法有了更深入的理解。它就像是我们手中的一条神奇项链，可以根据我们的需求，在任何位置灵活地添加或删除珠子，为我们处理数据提供了极大的便利。希望这次的 list 之旅能够让你对 C++ STL 有更进一步的认识，让我们在编程的世界里继续探索，发现更多宝藏！