C++ STL list全面解析（从入门到模拟实现）

如图所示，双向链表由多个节点组成，每个节点包含数据和两个指针，分别指向前一个节点和后一个节点。这种结构使得在list中插入和删除元素不需要移动其他元素，时间复杂度为O(1)。

二、list的使用

要使用STL容器list，首先需要包含头文件。下面是一些基本操作：

#include #include using namespace std;int main() {    // 创建一个list    list myList;    // 添加元素    myList.push_back(10); // 在末尾添加    myList.push_front(5); // 在开头添加    // 遍历list    for (int num : myList) {        cout << num << " ";    }    cout << endl;    // 插入元素    auto it = myList.begin();    advance(it, 1); // 移动迭代器    myList.insert(it, 7); // 在第二个位置插入7    // 删除元素    myList.pop_front(); // 删除第一个元素    return 0;}

list提供了丰富的成员函数，如size(), empty(), clear(), sort(), merge(), reverse()等。由于list是双向链表，它支持双向迭代器，但不支持随机访问迭代器，因此不能使用下标运算符[]。

在实际编程中，C++ list非常适合需要频繁插入和删除元素的场景，但如果你需要快速访问元素，vector可能更合适。

三、list的模拟实现

为了更好地理解list的工作原理，我们可以尝试模拟实现一个简单的list。这将帮助你深入理解双向链表的数据结构和操作。

首先，我们定义一个节点模板类：

templatestruct ListNode {    T data;    ListNode* prev;    ListNode* next;    ListNode(const T& val = T()) : data(val), prev(nullptr), next(nullptr) {}};

然后，定义list类，包含头尾指针和大小等信息：

templateclass MyList {private:    ListNode* head;    ListNode* tail;    size_t size;public:    MyList() : head(new ListNode()), tail(head), size(0) {        head->next = head;        head->prev = head;    }    ~MyList() {        // 释放所有节点        clear();        delete head;    }    void push_back(const T& val) {        ListNode* newNode = new ListNode(val);        tail->next = newNode;        newNode->prev = tail;        newNode->next = head;        head->prev = newNode;        tail = newNode;        size++;    }    // 其他成员函数如push_front, insert, erase等};

通过模拟实现，你可以更清楚地看到list的内部机制。当然，标准库中的list实现更加复杂和优化，但基本原理相同。

总结：list是C++ STL中一个重要的容器，它基于双向链表实现，提供了高效的插入和删除操作。掌握list的使用和原理，对于编写高效的C++程序至关重要。

希望本教程对你有所帮助！如果你有任何问题，欢迎在评论区留言。