当前位置：首页 > news >正文

《C++初阶之STL》【list容器:详解＋实现】

news 2025/8/29 7:43:58

在 STL 的序列式容器家族中，list以其独特的双向链表结构占据重要地位。与vector的连续内存不同，list通过节点间的指针连接实现数据存储，这使得它在任意位置的插入和删除操作中展现出显著优势。本文将从底层原理到实战实现，全面解析 STL list容器的核心机制与 C++ 实现方法。

一、list 容器的核心概念与特性

1. 底层结构：双向链表的魅力

list的底层是双向循环链表结构，每个节点包含三个核心部分：

数据域：存储节点的实际数据
前驱指针：指向当前节点的前一个节点
后继指针：指向当前节点的后一个节点

链表的首尾节点相互连接（尾节点的后继指向头节点，头节点的前驱指向尾节点），形成循环结构，这种设计能简化边界条件的处理（如空链表、首尾操作）。

2. 核心特性

特性	说明
非连续内存	节点在内存中分散存储，通过指针关联，无需连续内存块
双向迭代器	支持++和--操作，可双向遍历，但不支持随机访问（无[]和+n操作）
高效插入删除	任意位置插入 / 删除节点仅需修改指针，时间复杂度 O (1)（已知位置时）
迭代器稳定性	插入操作不会导致迭代器失效；删除操作仅使被删除节点的迭代器失效
内存动态分配	节点随插入动态创建，随删除释放，无需预先分配固定大小内存
缓存不友好	非连续内存导致 CPU 缓存命中率低，遍历效率低于vector

3. 与 vector 的关键对比

操作	list 优势场景	vector 优势场景
插入 / 删除	任意位置频繁操作（尤其是中间位置）	尾部操作（push_back/pop_back）
访问方式	双向顺序遍历	随机访问（[]/at ()）
内存开销	额外存储指针（每个节点 2 个指针）	连续内存，无指针开销，但可能有冗余空间
迭代器有效性	插入不失效，删除仅当前节点失效	插入可能导致全部失效，删除导致后续失效

二、list 容器的迭代器实现

list的迭代器是双向迭代器（Bidirectional Iterator），需支持++、--、*、->等操作。由于链表节点非连续，迭代器无法像vector那样通过指针偏移实现，必须通过节点的前驱 / 后继指针移动。

1. 节点结构定义

首先定义链表节点的结构体，包含数据域和两个指针：

template <typename T>struct ListNode {    T data;               // 数据域    ListNode<T>* prev;    // 前驱指针    ListNode<T>* next;    // 后继指针    // 构造函数    ListNode(const T& val)         : data(val), prev(nullptr), next(nullptr) {}};

2. 迭代器类实现

迭代器需要封装节点指针，并重载必要的运算符以支持遍历：

template <typename T>struct ListIterator {    using Node = ListNode<T>;    using Self = ListIterator<T>;    Node* node;  // 指向当前节点的指针    // 构造函数    ListIterator(Node* n) : node(n) {}    // 解引用：获取节点数据    T& operator*() const { return node->data; }    // 箭头运算符：访问数据成员    T* operator->() const { return &(node->data); }    // 前置++：移动到下一个节点    Self& operator++() {        node = node->next;        return *this;    }    // 后置++    Self operator++(int) {        Self temp = *this;        node = node->next;        return temp;    }    // 前置--：移动到前一个节点    Self& operator--() {        node = node->prev;        return *this;    }    // 后置--    Self operator--(int) {        Self temp = *this;        node = node->prev;        return temp;    }    // 相等比较    bool operator==(const Self& other) const {        return node == other.node;    }    // 不等比较    bool operator!=(const Self& other) const {        return node != other.node;    }};

3. const 迭代器

为支持const对象的遍历，需定义const版本的迭代器（数据只读）：

template <typename T>struct ListConstIterator {    using Node = ListNode<T>;    using Self = ListConstIterator<T>;    Node* node;    ListConstIterator(Node* n) : node(n) {}    // 解引用返回const引用    const T& operator*() const { return node->data; }    // 箭头运算符返回const指针    const T* operator->() const { return &(node->data); }    // 迭代器移动操作（与非const版本相同）    Self& operator++() { node = node->next; return *this; }    Self operator++(int) { Self temp = *this; node = node->next; return temp; }    Self& operator--() { node = node->prev; return *this; }    Self operator--(int) { Self temp = *this; node = node->prev; return temp; }    bool operator==(const Self& other) const { return node == other.node; }    bool operator!=(const Self& other) const { return node != other.node; }};

三、list 容器的核心实现

1. 容器类框架

list容器需维护链表的头节点（哨兵节点，简化操作）、大小等信息，并提供核心操作接口：

template <typename T>class List {public:    // 类型别名定义    using Node = ListNode<T>;    using Iterator = ListIterator<T>;    using ConstIterator = ListConstIterator<T>;    using ValueType = T;    using Reference = T&;    using ConstReference = const T&;    using SizeType = size_t;private:    Node* head;  // 头节点（哨兵节点，不存储实际数据）    SizeType size_;  // 元素个数    // 创建哨兵节点（前驱和后继都指向自身）    Node* createHead() {        Node* node = new Node(ValueType());        node->prev = node;        node->next = node;        return node;    }public:    // 构造函数    List() : head(createHead()), size_(0) {}    // 析构函数    ~List() {        clear();  // 释放所有元素节点        delete head;  // 释放哨兵节点        head = nullptr;    }    // 迭代器接口    Iterator begin() { return Iterator(head->next); }    Iterator end() { return Iterator(head); }    ConstIterator begin() const { return ConstIterator(head->next); }    ConstIterator end() const { return ConstIterator(head); }    ConstIterator cbegin() const { return ConstIterator(head->next); }    ConstIterator cend() const { return ConstIterator(head); }    // 容量操作    SizeType size() const { return size_; }    bool empty() const { return size_ == 0; }    // 元素访问    Reference front() { return *begin(); }    ConstReference front() const { return *cbegin(); }    Reference back() { return *(--end()); }    ConstReference back() const { return *(--cend()); }    // 核心操作：插入、删除、清空等（下文详细实现）    void push_back(const T& val);    void push_front(const T& val);    void pop_back();    void pop_front();    Iterator insert(Iterator pos, const T& val);    Iterator erase(Iterator pos);    void clear();    void swap(List& other);};

2. 插入操作实现

（1）尾部插入（push_back）

在链表尾部（哨兵节点前）插入新节点：

template <typename T>void List<T>::push_back(const T& val) {    Node* newNode = new Node(val);    Node* last = head->prev;  // 最后一个元素节点    // 调整指针关系    newNode->next = head;     // 新节点后继指向哨兵    newNode->prev = last;     // 新节点前驱指向原最后节点    last->next = newNode;     // 原最后节点后继指向新节点    head->prev = newNode;     // 哨兵前驱指向新节点    size_++;  // 大小递增}

（2）头部插入（push_front）

在链表头部（哨兵节点后）插入新节点：

template <typename T>void List<T>::push_front(const T& val) {    Node* newNode = new Node(val);    Node* first = head->next;  // 第一个元素节点    // 调整指针关系    newNode->prev = head;      // 新节点前驱指向哨兵    newNode->next = first;     // 新节点后继指向原第一个节点    first->prev = newNode;     // 原第一个节点前驱指向新节点    head->next = newNode;      // 哨兵后继指向新节点    size_++;  // 大小递增}

（3）任意位置插入（insert）

在指定迭代器位置前插入新节点：

template <typename T>typename List<T>::Iterator List<T>::insert(Iterator pos, const T& val) {    Node* newNode = new Node(val);    Node* cur = pos.node;  // 当前位置节点    Node* prevNode = cur->prev;  // 当前位置的前一个节点    // 调整指针关系    newNode->prev = prevNode;    newNode->next = cur;    prevNode->next = newNode;    cur->prev = newNode;    size_++;    return Iterator(newNode);  // 返回指向新节点的迭代器}

3. 删除操作实现

（1）尾部删除（pop_back）

删除链表最后一个元素节点：

template <typename T>void List<T>::pop_back() {    if (empty()) return;  // 空链表直接返回    Node* last = head->prev;  // 最后一个元素节点    Node* prevLast = last->prev;  // 倒数第二个元素节点    // 调整指针关系    prevLast->next = head;    head->prev = prevLast;    delete last;  // 释放节点内存    size_--;      // 大小递减}

（2）头部删除（pop_front）

删除链表第一个元素节点：

template <typename T>void List<T>::pop_front() {    if (empty()) return;    Node* first = head->next;  // 第一个元素节点    Node* nextFirst = first->next;  // 第二个元素节点    // 调整指针关系    head->next = nextFirst;    nextFirst->prev = head;    delete first;  // 释放节点内存    size_--;       // 大小递减}

（3）任意位置删除（erase）

删除指定迭代器位置的节点：

template <typename T>typename List<T>::Iterator List<T>::erase(Iterator pos) {    if (pos == end()) return end();  // 不能删除哨兵节点    Node* cur = pos.node;    Node* prevNode = cur->prev;    Node* nextNode = cur->next;    // 调整指针关系    prevNode->next = nextNode;    nextNode->prev = prevNode;    delete cur;  // 释放节点内存    size_--;    return Iterator(nextNode);  // 返回下一个节点的迭代器}

4. 清空操作（clear）

释放所有元素节点，保留哨兵节点：

template <typename T>void List<T>::clear() {    Node* cur = head->next;    while (cur != head) {  // 遍历到哨兵节点停止        Node* next = cur->next;        delete cur;        cur = next;    }    // 重置哨兵节点指针（指向自身）    head->prev = head;    head->next = head;    size_ = 0;}

5. 交换操作（swap）

交换两个链表的内容（仅交换头指针和大小，O (1) 复杂度）：

template <typename T>void List<T>::swap(List& other) {    std::swap(head, other.head);    std::swap(size_, other.size_);}

四、完整使用示例

#include <iostream>#include <algorithm>  // 用于for_eachusing namespace std;// 此处插入ListNode、ListIterator、ListConstIterator和List的完整定义int main() {    // 1. 创建list并插入元素    List<int> lst;    lst.push_back(10);    lst.push_back(20);    lst.push_front(5);    lst.insert(lst.begin()++, 7);  // 在5之后插入7    // 2. 遍历输出（预期：5 7 10 20）    cout << "list元素：";    for (auto it = lst.begin(); it != lst.end(); ++it) {        cout << *it << " ";    }    cout << endl;    // 3. 元素访问    cout << "首元素：" << lst.front() << endl;  // 5    cout << "尾元素：" << lst.back() << endl;    // 20    cout << "元素个数：" << lst.size() << endl;  // 4    // 4. 删除操作    lst.pop_front();  // 删除5    lst.erase(--lst.end());  // 删除20    cout << "删除后元素：";    for (int val : lst) {  // 范围for循环        cout << val << " ";  // 7 10    }    cout << endl;    // 5. 清空链表    lst.clear();    cout << "清空后是否为空：" << (lst.empty() ? "是" : "否") << endl;  // 是    return 0;}

五、list 容器的时间复杂度与适用场景

1. 时间复杂度分析

操作	时间复杂度	说明
push_back	O(1)	尾部插入，直接调整指针
push_front	O(1)	头部插入，直接调整指针
pop_back	O(1)	尾部删除，直接调整指针
pop_front	O(1)	头部删除，直接调整指针
insert(pos, val)	O(1)	已知位置插入，仅调整指针
erase(pos)	O(1)	已知位置删除，仅调整指针
begin()/end()	O(1)	直接返回迭代器
front()/back()	O(1)	直接访问首尾节点
size()	O(1)	直接返回存储的大小
clear()	O(n)	需要遍历释放所有节点
遍历	O(n)	需访问每个节点

2. 适用场景

list适合以下场景：

频繁在任意位置插入 / 删除元素：如实现链表式队列、栈、双向队列等数据结构
元素数量不确定且动态变化大：无需预先分配内存，避免vector的扩容开销
需要迭代器稳定性：插入操作后原有迭代器仍有效，仅删除的节点迭代器失效
数据元素较大：插入删除时无需移动大量元素（vector需复制移动数据）

不适合的场景：

需要随机访问元素：list不支持[]或at()，访问第 n 个元素需 O (n) 时间
遍历效率要求高：非连续内存导致缓存命中率低，遍历速度慢于vector

六、STL list 的扩展特性

实际 STL 中的list还提供更多实用功能：

排序：sort()成员函数（链表排序，时间复杂度 O (n log n)）
合并：merge()合并两个有序链表
反转：reverse()反转链表（仅调整指针，O (n)）
去重：unique()移除连续重复元素
拼接：splice()将另一个链表的元素转移到当前链表（O (1)）

示例：使用 STL list 的排序和去重功能

#include <list>#include <iostream>using namespace std;int main() {    list<int> stl_lst = {3, 1, 4, 1, 5, 9, 2, 6};        stl_lst.sort();  // 排序：1 1 2 3 4 5 6 9    stl_lst.unique();  // 去重：1 2 3 4 5 6 9        for (int val : stl_lst) {        cout << val << " ";    }    return 0;}

查看全文

http://www.ijyty.com/news/1036.html