手把手实现C++STL list容器

我是一只小青蛙888

941人浏览 · 2026-02-03 07:18:38

我是一只小青蛙888 · 2026-02-03 07:18:38 发布

好的，我们来逐步模拟实现一个简化版的 C++ STL list 容器。我们将从最基础的节点结构开始，构建双向链表，然后封装成具备常用接口的容器类。

1. 节点结构 (`ListNode`)

链表的基本单位是节点。每个节点包含：

存储的数据 (data)
指向前一个节点的指针 (prev)
指向后一个节点的指针 (next)

template<typename T>
struct ListNode {
    T data; // 节点存储的数据
    ListNode<T>* prev; // 指向前驱节点的指针
    ListNode<T>* next; // 指向后继节点的指针

    // 构造函数
    ListNode(const T& val = T(), ListNode<T>* p = nullptr, ListNode<T>* n = nullptr)
        : data(val), prev(p), next(n) {}
};

2. 链表基础结构 (`List`)

List 类需要管理链表的头尾，并记录元素个数。为了方便操作（如 begin() 和 end()），通常会使用一个哨兵节点（dummy node）来简化边界条件的处理。这个哨兵节点不存储有效数据，其 next 指向第一个有效节点，prev 指向最后一个有效节点，自身形成一个循环。

template<typename T>
class List {
private:
    ListNode<T>* dummy; // 哨兵节点
    size_t count; // 元素个数

public:
    // 构造函数
    List() : count(0) {
        dummy = new ListNode<T>(); // 创建哨兵节点
        dummy->next = dummy; // 初始化时，自己指向自己
        dummy->prev = dummy;
    }

    // 析构函数 - 释放所有节点
    ~List() {
        clear(); // 清空有效节点
        delete dummy; // 删除哨兵节点
    }

    // 清空链表
    void clear() {
        ListNode<T>* cur = dummy->next;
        while (cur != dummy) { // 遍历到哨兵节点停止
            ListNode<T>* next = cur->next;
            delete cur;
            cur = next;
        }
        dummy->next = dummy; // 重置哨兵节点指向
        dummy->prev = dummy;
        count = 0;
    }

    // ... 其他成员函数将在下面实现
};

3. 迭代器 (`Iterator`)

STL 容器的精髓在于迭代器。我们需要实现一个双向迭代器，支持 ++, --, *, ->, ==, != 等操作。迭代器本质上是对节点指针的封装。

template<typename T>
class List {
    // ... 前面的代码

public:
    // 迭代器类 (嵌套在 List 内部)
    class Iterator {
    private:
        ListNode<T>* ptr; // 指向当前节点的指针

    public:
        Iterator(ListNode<T>* p = nullptr) : ptr(p) {}

        // 解引用操作符 (*)
        T& operator*() const {
            return ptr->data;
        }

        // 成员访问操作符 (->)
        T* operator->() const {
            return &(ptr->data);
        }

        // 前缀 ++
        Iterator& operator++() {
            ptr = ptr->next;
            return *this;
        }

        // 后缀 ++ (需要 int 参数占位)
        Iterator operator++(int) {
            Iterator old = *this;
            ++(*this);
            return old;
        }

        // 前缀 --
        Iterator& operator--() {
            ptr = ptr->prev;
            return *this;
        }

        // 后缀 --
        Iterator operator--(int) {
            Iterator old = *this;
            --(*this);
            return old;
        }

        // 相等比较
        bool operator==(const Iterator& other) const {
            return ptr == other.ptr;
        }

        // 不等比较
        bool operator!=(const Iterator& other) const {
            return ptr != other.ptr;
        }
    };

    // 获取指向第一个元素的迭代器
    Iterator begin() const {
        return Iterator(dummy->next);
    }

    // 获取尾后迭代器 (指向哨兵节点)
    Iterator end() const {
        return Iterator(dummy);
    }

    // ... 其他成员函数
};

4. 核心功能实现

现在利用节点、哨兵和迭代器，实现 list 的核心操作：插入、删除、访问等。

`push_back` (尾部插入)

void push_back(const T& value) {
    ListNode<T>* last = dummy->prev; // 当前最后一个有效节点
    ListNode<T>* newNode = new ListNode<T>(value, last, dummy); // 新节点，prev指最后节点，next指dummy
    last->next = newNode; // 原最后一个节点的next指向新节点
    dummy->prev = newNode; // dummy的prev指向新节点 (新节点成为最后一个)
    ++count;
}

`push_front` (头部插入)

void push_front(const T& value) {
    ListNode<T>* first = dummy->next; // 当前第一个有效节点
    ListNode<T>* newNode = new ListNode<T>(value, dummy, first); // 新节点，prev指dummy，next指第一个节点
    dummy->next = newNode; // dummy的next指向新节点 (新节点成为第一个)
    first->prev = newNode; // 原第一个节点的prev指向新节点
    ++count;
}

`insert` (在迭代器位置前插入)

Iterator insert(Iterator pos, const T& value) {
    ListNode<T>* currNode = pos.ptr; // 当前迭代器指向的节点
    ListNode<T>* prevNode = currNode->prev; // 当前节点的前一个节点

    ListNode<T>* newNode = new ListNode<T>(value, prevNode, currNode);
    prevNode->next = newNode;
    currNode->prev = newNode;

    ++count;
    return Iterator(newNode); // 返回指向新插入元素的迭代器
}

`erase` (删除迭代器指向的元素)

Iterator erase(Iterator pos) {
    if (pos == end()) { // 不能删除尾后迭代器
        return end();
    }
    ListNode<T>* currNode = pos.ptr;
    ListNode<T>* prevNode = currNode->prev;
    ListNode<T>* nextNode = currNode->next;

    prevNode->next = nextNode;
    nextNode->prev = prevNode;

    Iterator nextIter(nextNode); // 记录下一个元素的迭代器
    delete currNode;
    --count;
    return nextIter; // 返回被删除元素的下一个元素的迭代器
}

`size` 和 `empty`

size_t size() const {
    return count;
}

bool empty() const {
    return count == 0;
}

`front` 和 `back` (访问首尾元素)

T& front() {
    return dummy->next->data; // 第一个有效节点的数据
}

const T& front() const {
    return dummy->next->data;
}

T& back() {
    return dummy->prev->data; // 最后一个有效节点的数据
}

const T& back() const {
    return dummy->prev->data;
}

5. 完整示例代码 (简化版)

将以上部分组合起来：

template<typename T>
class List {
private:
    struct ListNode {
        T data;
        ListNode* prev;
        ListNode* next;
        ListNode(const T& val = T(), ListNode* p = nullptr, ListNode* n = nullptr)
            : data(val), prev(p), next(n) {}
    };

    ListNode* dummy;
    size_t count;

public:
    class Iterator {
    private:
        ListNode* ptr;
    public:
        Iterator(ListNode* p = nullptr) : ptr(p) {}
        T& operator*() const { return ptr->data; }
        T* operator->() const { return &(ptr->data); }
        Iterator& operator++() { ptr = ptr->next; return *this; }
        Iterator operator++(int) { Iterator old = *this; ++(*this); return old; }
        Iterator& operator--() { ptr = ptr->prev; return *this; }
        Iterator operator--(int) { Iterator old = *this; --(*this); return old; }
        bool operator==(const Iterator& other) const { return ptr == other.ptr; }
        bool operator!=(const Iterator& other) const { return ptr != other.ptr; }
    };

    List() : count(0) {
        dummy = new ListNode();
        dummy->next = dummy;
        dummy->prev = dummy;
    }

    ~List() {
        clear();
        delete dummy;
    }

    void clear() {
        ListNode* cur = dummy->next;
        while (cur != dummy) {
            ListNode* next = cur->next;
            delete cur;
            cur = next;
        }
        dummy->next = dummy;
        dummy->prev = dummy;
        count = 0;
    }

    Iterator begin() const { return Iterator(dummy->next); }
    Iterator end() const { return Iterator(dummy); }

    void push_back(const T& value) {
        ListNode* last = dummy->prev;
        ListNode* newNode = new ListNode(value, last, dummy);
        last->next = newNode;
        dummy->prev = newNode;
        ++count;
    }

    void push_front(const T& value) {
        ListNode* first = dummy->next;
        ListNode* newNode = new ListNode(value, dummy, first);
        dummy->next = newNode;
        first->prev = newNode;
        ++count;
    }

    Iterator insert(Iterator pos, const T& value) {
        ListNode* currNode = pos.ptr;
        ListNode* prevNode = currNode->prev;
        ListNode* newNode = new ListNode(value, prevNode, currNode);
        prevNode->next = newNode;
        currNode->prev = newNode;
        ++count;
        return Iterator(newNode);
    }

    Iterator erase(Iterator pos) {
        if (pos == end()) return end();
        ListNode* currNode = pos.ptr;
        ListNode* prevNode = currNode->prev;
        ListNode* nextNode = currNode->next;
        prevNode->next = nextNode;
        nextNode->prev = prevNode;
        Iterator nextIter(nextNode);
        delete currNode;
        --count;
        return nextIter;
    }

    size_t size() const { return count; }
    bool empty() const { return count == 0; }

    T& front() { return dummy->next->data; }
    const T& front() const { return dummy->next->data; }
    T& back() { return dummy->prev->data; }
    const T& back() const { return dummy->prev->data; }
};

总结

这个简化版的 List 实现了 STL list 的核心功能：

底层结构：基于带有哨兵节点的双向循环链表。
节点管理：ListNode 封装数据和指针。
迭代器：Iterator 类封装节点指针，提供类似指针的操作接口，使算法能透明地操作容器元素。
容器接口：提供了 begin(), end(), push_back, push_front, insert, erase, size, empty, front, back 等常用接口。

实际 STL 的实现更为复杂，涉及内存分配器 (allocator)、更完善的异常安全保证、类型萃取 (type traits)、const 迭代器、反向迭代器 (reverse_iterator) 等。但这个简化版清晰地展示了 list 从底层链表到容器封装的关键设计思想和实现路径。

亚马逊云科技技术品牌专区

更多推荐

基于大数据+Hadoop+深度学习的淘宝用户购物可视化与行为预测系统设计与开发

亚马逊云科技技术品牌专区

基于大数据爬虫+Hadoop+深度学习的旅游推荐系统设计与开发

亚马逊云科技技术品牌专区

学Linux选学校：一线城市还是老家？

而二线城市很多机构的老师，自己都没进过大厂，技术停留在五年前的水平，甚至对着PPT照本宣科。而二线机构缺乏企业合作资源，项目案例永远是“搭建博客系统”“配置个LAMP环境”——这些在现在的云计算岗位面试中，连初筛都过不了。在一线城市学习，你接触的同学、老师、企业内推资源，都是二线城市没法比的。而老家机构的学员，最好的结果也就是去本地小公司做网管，月薪五六千，天花板肉眼可见。在IT培训这行干了快十年