C++ List容器的底层实现

这里写目录标题

• list 容器节点结构
• list容器迭代器的底层实现
• list容器的底层实现

list 容器节点结构

通过查看 list 容器的源码实现，其对节点的定义如下：

template<typename T,...>
struct __List_node{
   
    //...
    __list_node<T>* prev;
    __list_node<T>* next;
    T myval;
    //...
}

可以看到，list 容器定义的每个节点中，都包含 *prev、*next 和 myval。其中，prev 指针用于指向前一个节点；next 指针用于指向后一个节点；myval 用于存储当前元素的值。

list容器迭代器的底层实现

和 array、vector 这些容器迭代器的实现方式不同，由于 list 容器的元素并不是连续存储的，所以该容器迭代器中，必须包含一个可以指向 list 容器的指针，并且该指针还可以借助重载的 *、++、–、==、!= 等运算符，实现迭代器正确的递增、递减、取值等操作。
因此，list 容器迭代器的实现代码如下：

template<tyepname T,...>
struct __list_iterator{
   
    __list_node<T>* node;
    //...
    //重载 == 运算符
    bool operator==(const __list_iterator& x){
   return node == x.node;}