C++中的list的学习

1.list的介绍及其使用

1.1list的介绍

list的文档介绍

这张图展示了 C++ 标准库中 list 的底层结构和关键概念，重点体现了 list（双向循环链表）的工作原理。以下是逐部分的详细解析：

1. 核心结构：双向循环链表

list 是基于 环状双向链表（circular doubly-linked list） 实现的，特点：

• 每个节点有 前驱指针（指向前一个节点）和 后继指针（指向后一个节点）。
• 链表首尾相连，形成一个环（end() 不指向 nullptr，而是指向一个 “哨兵节点”）。

2. 关键组件解析

(1) list<int> list；

• 定义了一个存储 int 类型的 list 对象 ilist，底层是双向循环链表。

(2) 哨兵节点（_M_node 所指节点）

• 图中红色方框标记的是 哨兵节点（sentinel node），它是一个 “虚拟节点”，不存储实际数据。
• 作用：统一链表操作（首尾插入 / 删除无需判断边界），让 begin() 和 end() 逻辑更简洁。

(3) 迭代器与范围

• ilist.begin()：返回指向第一个数据节点（蓝色方框，值为 0）的迭代器。
• ilist.end()：返回指向哨兵节点的迭代器（不指向有效数据，标志遍历结束）。
• find(ilist.begin(), ilist.end(), 3)：从第一个数据节点开始遍历，查找值为 3 的节点，返回其迭代器
  ite。

3. 节点与指针关系

每个节点包含：

• 数据域：存储实际值（如 0、2、3、4）。
• 前驱指针：指向前一个节点（图中箭头反向）。
• 后继指针：指向后一个节点（图中箭头正向）。

4. 遍历逻辑

• 正向遍历：从 begin()（值 0）出发，通过 “后继指针” 依次访问 0 → 2 → 3 → 4，直到 end()（哨兵节点）。
• 逆向遍历：从 rbegin()（内部基于 “前驱指针” 实现）出发，可反向访问 4 → 3 → 2 → 0。

总结
这张图清晰展示了 list 的 双向循环链表本质，核心是：

• 用哨兵节点简化边界操作。
• 用双向指针支持高效插入 / 删除。
• 迭代器遍历需从 begin() 到 end()（哨兵节点）终止。

1.2list的使用

list中的接口比较多，只需要掌握如何正确的使用，然后再去深入研究背后的原理，已达到可扩展的能力。以下为list中一些常见的重要接口。

1.2.1 list的构造

1.2.2 list iterator的使用

【注意】

1. begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
2. rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动

1.2.3 list capacity

1.2.4 list element access

1.2.5 list modifiers

1.2.6 list的迭代器失效

此处可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。

void TestListIterator1()
{
	int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
	list<int> l(array, array + sizeof(array) / sizeof(array[0]));
	auto it = l.begin();
	while (it != l.end())
	{
		// erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给
		其赋值
		l.erase(it);
		++it;
	}
}
// 改正
void TestListIterator()
{
	int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
	list<int> l(array, array + sizeof(array) / sizeof(array[0]));
	auto it = l.begin();
	while (it != l.end())
	{
		l.erase(it++); // it = l.erase(it);
	}
}

2.list的模拟实现

2.1list的实现

#include <memory>
#include <iterator>
#include <stdexcept>

template<typename T>
class List {
private:
    // 节点结构
    struct Node {
        T data;
        Node* prev;
        Node* next;
        Node(const T& value = T()) : data(value), prev(nullptr), next(nullptr) {}
    };

    Node* head;  // 头节点（哨兵）
    Node* tail;  // 尾节点（哨兵）
    size_t m_size;

public:
    // 迭代器实现
    class iterator {
    private:
        Node* ptr;
    public:
        iterator(Node* p = nullptr) : ptr(p) {}
        T& operator*() { return ptr->data; }
        iterator& operator++() { ptr = ptr->next; return *this; }
        iterator operator++(int) { iterator tmp = *this; ++(*this); return tmp; }
        iterator& operator--() { ptr = ptr->prev; return *this; }
        iterator operator--(int) { iterator tmp = *this; --(*this); return tmp; }
        bool operator==(const iterator& other) const { return ptr == other.ptr; }
        bool operator!=(const iterator& other) const { return ptr != other.ptr; }
    };

    // 构造函数
    List() : m_size(0) {
        head = new Node();
        tail = new Node();
        head->next = tail;
        tail->prev = head;
    }

    // 析构函数
    ~List() {
        clear();
        delete head;
        delete tail;
    }

    // 容量
    bool empty() const { return m_size == 0; }
    size_t size() const { return m_size; }

    // 迭代器
    iterator begin() { return iterator(head->next); }
    iterator end() { return iterator(tail); }

    // 修改操作
    void push_back(const T& value) {
        insert(end(), value);
    }

    void pop_back() {
        if (!empty()) {
            erase(--end());
        }
    }

    iterator insert(iterator pos, const T& value) {
        Node* p = pos.ptr;
        Node* newNode = new Node(value);

        newNode->prev = p->prev;
        newNode->next = p;
        p->prev->next = newNode;
        p->prev = newNode;

        ++m_size;
        return iterator(newNode);
    }

    iterator erase(iterator pos) {
        if (pos == end()) return pos;

        Node* toDelete = pos.ptr;
        iterator nextNode(toDelete->next);

        toDelete->prev->next = toDelete->next;
        toDelete->next->prev = toDelete->prev;

        delete toDelete;
        --m_size;

        return nextNode;
    }

    void clear() {
        while (!empty()) {
            pop_back();
        }
    }
};

2.2list的反向迭代器

反向迭代器的++就是正向迭代器的–，反向迭代器的–就是正向迭代器的++，
因此反向迭代器的实现可以借助正向迭代器，即：反向迭代器内部可以包含一个正向迭代器，对正向迭代器的接口进行包装即可。

template<class Iterator>
class ReverseListIterator
{
	// 注意：此处typename的作用是明确告诉编译器，Ref是Iterator类中的类型，而不是静态成员变量
	// 否则编译器编译时就不知道Ref是Iterator中的类型还是静态成员变量
	// 因为静态成员变量也是按照 类名::静态成员变量名 的方式访问的
public:
	typedef typename Iterator::Ref Ref;
	typedef typename Iterator::Ptr Ptr;
	typedef ReverseListIterator<Iterator> Self;
public:
	//////////////////////////////////////////////
	// 构造
	ReverseListIterator(Iterator it) : _it(it) {}
	//////////////////////////////////////////////
	// 具有指针类似行为
	Ref operator*() {
		Iterator temp(_it);
		--temp;
		return *temp;
	}
	Ptr operator->() { return &(operator*()); }
	//////////////////////////////////////////////
	// 迭代器支持移动
	Self& operator++() {
		--_it;
		return *this;
	}
	Self operator++(int) {
		Self temp(*this);
		--_it;
		return temp;
	}
	Self& operator--() {
		++_it;
		return *this;
	}
	Self operator--(int)
	{
		Self temp(*this);
		++_it;
		return temp;
	}
	//////////////////////////////////////////////
	// 迭代器支持比较
	bool operator!=(const Self& l)const { return _it != l._it; }
	bool operator==(const Self& l)const { return _it != l._it; }
	Iterator _it;
};

3. list与vector的对比

vector与list都是STL中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及应用场景不同，其主要不同如下：