欢迎光临
我们一直在努力

【C++进阶】万字长文手写STL:从Vector到优先队列(Heap)的底层黑科技

前情提要:面试官问你:priority_queue 的底层是队列吗?queue 为什么默认用 deque 而不是 vector?
如果你答不上来,这篇硬核手写STL系列就是为你准备的。本文将从内存模型、常用接口到手写模拟,带你彻底攻克 Vector、List、Queue 以及最复杂的 Priority_queue(堆)。建议收藏,面试前突击必看!会用STL只是基本功,懂底层原理才是高手的入场券。


目录

  • STL 六大组件概览
  • 线性之王:Vector(动态数组)
    • 底层原理与扩容机制
    • 面试重灾区:迭代器失效
    • 硬核实战:手写 MyVector
  • 链表双雄:List(双向链表)
    • 内存结构对比
    • 为什么有了 Vector 还要 List?
    • 核心逻辑:手写 MyList 节点管理
  • 关联容器:Map 与 Unordered_map 的爱恨情仇
    • 红黑树 vs 哈希表
  • 容器适配器:Queue 与 Stack
    • 为什么它们叫“适配器”?
    • 几行代码封装 MyQueue
  • 进阶难点:Priority_queue(优先队列/堆)
    • 堆的物理结构 vs 逻辑结构
    • 核心算法:上滤(AdjustUp)与 下滤(AdjustDown)
    • 手写 MyPriorityQueue(面试高频!)
  • 总结

  • 1. STL 六大组件概览

    在深入代码之前,我们先明确 STL 的核心架构。它不仅仅是容器,而是一个精密的生态系统:

    • 容器 (Containers):存放数据(Vector, List, Map…)
    • 算法 (Algorithms):操作数据(Sort, Find…)
    • 迭代器 (Iterators):连接容器与算法的桥梁(像指针一样的存在)
    • (以及仿函数、适配器、空间配置器)

    今天我们重点攻克容器。


    2. 线性之王:Vector(动态数组)

    2.1 底层原理与扩容机制

    std::vector 本质上是一个连续内存的动态数组。它有三个核心指针:

    • _start:指向数组开头。
    • _finish:指向有效数据的下一个位置。
    • _end_of_storage:指向整个容量的末尾。

    面试必问:Vector 是如何自动扩容的?
    当空间不够(size() == capacity())时,Vector 不会在原数组后面直接拼接(因为后面内存可能被占用了)。它的操作步骤是:

  • 开辟新空间:通常是原容量的 1.5倍 (VS编译器) 或 2倍 (GCC编译器)。
  • 数据拷贝:将旧数据拷贝到新空间。
  • 释放旧空间:删除原来的数组。
  • 更新指针:指向新地址。
  • 代价:扩容是一次高成本操作(深拷贝),所以如果知道数据量,建议提前使用 .reserve(n)。

    2.2 重灾区:迭代器失效

    因为扩容可能导致地址变更,所以扩容后,原来指向旧空间的迭代器全部变成“野指针”,这就叫迭代器失效。

    • 插入失效:insert/push_back 可能触发扩容。
    • 删除失效:erase 会导致被删元素后面的迭代器错位。

    2.3 硬核实战:手写 MyVector

    拒绝纸上谈兵,我们用简化代码模拟一个 Vector 的核心逻辑,也就是手写STL容器,这是最好理解和使用STL的方法。

    #include <bits/stdc++.h>
    using namespace std;
    template<class T>
    class MyVector {
    public:
    typedef T* iterator;//Vector的迭代器本质就是原生指针
    //默认构造函数
    MyVector():_start(nullptr),_finish(nullptr),_end_of_storage(nullptr) {}
    // 析构
    ~MyVector(){
    if (_start){
    delete[] _start;
    _start=_finish=_end_of_storage=nullptr;
    }
    }
    // 核心功能:push_back
    void push_back(const T& x){
    if (_finish ==_end_of_storage) {
    // 需要扩容
    size_t newCapacity=capacity()==0 ? 4 : capacity() * 2;
    reserve(newCapacity);
    }
    *_finish=x;
    _finish++;
    }
    // 核心逻辑:reserve (扩容)
    void reserve(size_t n){
    if (n>capacity()){
    size_t oldSize=size();
    T* tmp=new T[n];//1.开新空间
    if (_start) {
    //2.拷贝数据 (注意:如果是自定义对象,这里不能用memcpy,要用循环赋值进行深拷贝)
    for (size_t i=0;i<oldSize;++i)
    tmp[i]=_start[i];
    delete[] _start;//3.释放旧空间
    }
    //4.更新指针
    _start=tmp;
    _finish=_start+oldSize;
    _end_of_storage=_start+n;
    }
    }
    // 常用接口
    size_t size() const{ return _finish–_start;}
    size_t capacity() const{ return _end_of_storage–_start;}
    T& operator[](size_t pos){
    assert(pos<size());
    return _start[pos];
    }

    // 迭代器接口
    iterator begin() { return _start; }
    iterator end() { return _finish; }

    private:
    T* _start;
    T* _finish;
    T* _end_of_storage;
    };
    int main() {
    MyVector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    cout<<"Size: "<<v.size()<<", Capacity:"<<v.capacity()<<endl;
    for(auto x:v)
    cout<<x<<" ";
    return 0;
    }


    3. 链表双雄:List(双向链表)

    3.1 内存结构对比

    • Vector:空间连续,支持随机访问 O(1),但中间插入删除慢 O(N)。
    • List:空间不连续(一个个节点),不支持随机访问(不能用 []),但任意位置插入删除极快 O(1)。

    3.2 核心逻辑:手写 MyList 节点

    std::list 是一个带头双向循环链表。手写它的关键在于节点的定义。

    // 定义节点结构
    template<class T>
    struct ListNode{
    ListNode<T>* _next;
    ListNode<T>* _prev;
    T _data;
    ListNode(const T& x=T()) : _next(nullptr),_prev(nullptr),_data(x) {}
    };

    // 简易 List 类
    template<class T>
    class MyList {
    typedef ListNode<T> Node;
    public:
    MyList(){
    // 初始化哨兵位头节点
    _head=new Node;
    _head->_next=_head;
    _head->_prev=_head;
    }

    void push_back(const T& x){//添加函数
    // 找尾节点
    Node* tail=_head->_prev;
    Node* new_node=new Node(x);

    // 链接关系:tail–new_node–head
    tail->_next=new_node;
    new_node->_prev=tail;
    new_node->_next=_head;
    _head->_prev=new_node;
    }

    private:
    Node* _head;
    };


    4. 关联容器:Map 与 Unordered_map 的爱恨情仇

    这部分考察的是数据结构的底蕴。

    特性std::map / setstd::unordered_map / set
    底层实现 红黑树 (Red-Black Tree) 哈希表 (Hash Table)
    是否有序 有序 (按 Key 排序) 无序
    查找时间 O(log⁡N)O(\\log N)O(logN) (非常稳定) O(1)O(1)O(1) (最坏情况 O(N)O(N)O(N))
    迭代器 双向迭代器 前向迭代器
    适用场景 需要范围查找、有序输出 单纯的高速查找、去重

    💡 小技巧:
    只要题目没有要求“按顺序输出”,首选 unordered_map,因为它的平均速度比红黑树快得多!


    5. 容器适配器:Queue(队列)

    5.1 原理分析:它不是“容器”?

    在STL中,stack 和 queue 被称为 容器适配器 (Container Adaptors)。
    它们不直接管理内存,而是“寄生”在其他容器(如 deque 或 list)之上,封装出特殊的行为。

    • Queue 特性:FIFO(先进先出)。
    • 默认底层:std::deque(双端队列)。
      • 问:为什么不用 vector?*
      • 答:vector 在头部删除(出队)是 O(N)O(N)O(N) 的,效率太低;而 deque 支持 O(1)O(1)O(1) 的头尾操作。

    5.2 手写 MyQueue

    我们可以利用模板参数,让用户自己选择底层容器(比如用 list 或 deque)。

    #include <bits/stdc++.h>
    //T: 数据类型
    //Container: 底层容器,默认用 deque
    template<class T, class Container=std::deque<T>>
    class MyQueue{
    public:
    //入队:尾插
    void push(const T& x){
    _con.push_back(x);
    }
    //出队:头删
    void pop(){
    if (!empty()) _con.pop_front();
    }
    // 获取队头
    const T& front(){
    return _con.front();
    }
    bool empty(){ return _con.empty(); }
    size_t size(){ return _con.size(); }
    private:
    Container _con; // 直接调用底层容器的接口
    };


    6. 进阶难点:Priority_queue(优先队列)

    这是本文的重头戏! 名字叫“队列”,但它的物理底层其实是 vector,逻辑结构是 堆 (Heap)(说这话看着都挺搞笑的)。

    6.1 堆的原理(二叉树的数组化)

    优先队列保证每次 top() 出来的都是最大值(大顶堆)或最小值(小顶堆)。它使用数组来模拟完全二叉树:

    • 父节点下标:parent = (child – 1) / 2
    • 左孩子下标:left_child = parent * 2 + 1

    6.2 核心算法图解

    想要手写优先队列,必须掌握两个调整算法:

  • push (入堆) -> 向上调整 (AdjustUp)
    • 先把数据插到数组末尾。
    • 和父节点比,如果比父节点大(大顶堆),就交换,继续向上比。
  • pop (出堆) -> 向下调整 (AdjustDown)
    • 千万不能直接删头部! 那样会破坏堆结构。
    • 做法:交换 堆顶 和 数组末尾元素 -> pop_back() 删除末尾 -> 从堆顶开始向下调整。
  • 6.3 手写 MyPriorityQueue (硬核源码)

    #include <bits/stdc++.h>
    using namespace std;
    // 默认大顶堆(大的在上面)
    template<class T, class Container = vector<T>>
    class MyPriorityQueue {
    public:
    // 向上调整(用于插入)
    void AdjustUp(int child) {
    int parent = (child – 1) / 2;
    while (child > 0) {
    // 如果孩子比父亲大,交换
    if (_con[child] > _con[parent]) {
    swap(_con[child], _con[parent]);
    child = parent;
    parent = (child – 1) / 2;
    } else {
    break;
    }
    }
    }

    // 向下调整(用于删除)
    void AdjustDown(int parent) {
    int child = parent * 2 + 1; // 默认找左孩子
    while (child < _con.size()) {
    // 1. 选出左右孩子中较大的那个
    if (child + 1 < _con.size() && _con[child + 1] > _con[child]) {
    ++child; // 右孩子更大,选右孩子
    }

    // 2. 孩子和父亲比较
    if (_con[child] > _con[parent]) {
    swap(_con[child], _con[parent]);
    parent = child;
    child = parent * 2 + 1;
    } else {
    break;
    }
    }
    }

    // 入队
    void push(const T& x) {
    _con.push_back(x);
    AdjustUp(_con.size() – 1);
    }

    // 出队
    void pop() {
    if (empty()) return;
    // 1. 交换首尾
    swap(_con[0], _con[_con.size() – 1]);
    // 2. 删除尾部
    _con.pop_back();
    // 3. 向下调整
    AdjustDown(0);
    }

    const T& top() { return _con[0]; }
    bool empty() { return _con.empty(); }

    private:
    Container _con;
    };

    // 测试代码
    int main() {
    MyPriorityQueue<int> pq;
    pq.push(3);
    pq.push(1);
    pq.push(9);
    pq.push(4);

    while (!pq.empty()) {
    cout << pq.top() << " "; // 输出应为由大到小: 9 4 3 1
    pq.pop();
    }
    return 0;
    }

    💡 进阶思考:
    如何实现小顶堆?
    实际上 STL 使用了 仿函数 (Functor)。你可以增加一个模板参数 class Compare,把代码里的 > 换成 comp(child, parent),以此来控制比较逻辑。


    7. 总结

    容器底层结构迭代器核心考点
    Vector 动态数组 随机访问 扩容机制、深拷贝
    List 双向链表 双向 任意位置插入不失效
    Queue Deque (默认) 无 为什么不用 Vector 做底层?
    Priority_queue Vector + 堆算法 无 TopK 问题、堆排序实现

    手写容器不仅能帮你理解指针和内存管理,更是面试中展现你“技术深度”的杀手锏。建议大家把上面的 MyVector 代码自己敲一遍,尝试添加 insert 和 erase 功能!还有能够手写 Priority_queue 的话说明你数据结构功底扎实。建议大家把本文的代码 Copy 到编译器里跑一遍,甚至尝试去实现 make_heap 的逻辑!

    赞(0)
    未经允许不得转载:171主机测评 » 【C++进阶】万字长文手写STL:从Vector到优先队列(Heap)的底层黑科技
    分享到: 更多 (0)

    评论 抢沙发

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址