C++ 从入门到精通之四

大纲

• C++ 从入门到精通之一、C++ 从入门到精通之二、C++ 从入门到精通之三
• C++ 从入门到精通之四、C++ 从入门到精通之五、C++ 从入门到精通之六
• C++ 从入门到精通之七、C++ 从入门到精通之八、C++ 从入门到精通之九
• C++ 从入门到精通之十、C++ 从入门到精通之十一、C++ 从入门到精通之十二
• C++ 从入门到精通之十三、C++ 从入门到精通之十四、C++ 从入门到精通之十五
• C++ 从入门到精通之十六、C++ 从入门到精通之十七

C++ 容器

扩展阅读

• C++ STL 容器介绍与使用

容器的分类

C++ STL 容器分为四大类：序列容器、有序关联容器、无序关联容器、容器适配器。

大类	常见容器	底层结构	是否有序	典型查找复杂度
序列容器	array、vector、deque、list、forward_list	数组 / 链表	按位置线性顺序	按位置访问
有序关联容器	set、multiset、map、multimap	红黑树等平衡 BST	按 Key 有序	O(log n)
无序关联容器	unordered_set、unordered_multiset、unordered_map、unordered_multimap	哈希表	不保证顺序	平均 O(1)，最坏 O(n)
容器适配器	stack、queue、priority_queue	基于序列容器封装	取决于底层容器的实现	不直接提供查找功能（迭代器）

其中序列容器（又叫顺序容器）的分类如下图所示：

deque 容器

deque 的概述

deque 一种双向开口的连续线性空间（双端队列容器），底层的数据结构是支持动态开辟内存空间的二维数组。所谓双向开口，意思是可以在头尾两端分别进行元素的插入和移除操作。虽然 vector 也可以在头尾两端进行操作，但是其头部操作的效率非常低，无法被接受。deque 和 vector 的最大差异，一在于 deque 允许于常数项时间内对头端进行元素的插入或移除操作，二在于 deque 没有所谓容量 capacity 的观念，因为它是动态地以分段连续空间组合而成，随时可以增加一段新的空间并链接起来。换句话说，像 vector 那样因旧空间不足而重新配置一块更大的空间，然后拷贝元素，再释放旧空间这样的事情不会发生在 deque 身上，也因此 deque 没有必要提供所谓的空间保留（reserve）功能。虽然 deque 也提供了随机迭代器（Random Access Iterator），但是它的迭代器并不是普通的指针，其复杂度和 vector 不是一个量级，这会影响各个层面的运算效率。因此，除非有必要，应该尽可能的使用 vector，而不是 deque。对 deque 进行的排序操作，为了提高效率，可将 deque 先完整的复制到一个 vector 中，然后对 vector 容器进行排序，再复制回 deque。

deque 的结构

deque 本质上是由一段一段的定量连续空间（分段连续内存空间）构造而成，一旦有必要在 deque 的头端或尾端增加新空间，便会配置一段新的定量连续空间，然后串接在整个 deque 的头端或尾端。deque 最大的工作就是维护这些分段连续的内存空间的整体性的假象，并提供随机存取的接口；这避开了重新配置空间、复制数据、释放空间的轮回，代价就是复杂的迭代器架构。既然 deque 使用的是分段连续内存空间，那么就必须有中央控制器，维持其整体连续的假象，这样也导致了数据结构的设计及迭代器的前进后退操作颇为繁琐，deque 底层实现的代码远比 vector 或 list 都多得多。

deque 内部的中控器维护的是每个缓冲区的地址，而缓冲区则存放着真实的数据，目的是让 deque 使用起来像是一片连续的内存空间。deque 采取一块所谓的 map（注意，不是 STL 的 map 容器）作为主控，这里所谓的 map 是一小块连续的内存空间，其中每一个元素（节点）都是一个指针，指向另一段连续性内存空间，称作缓冲区，缓冲区才是 deque 的存储空间的主体。

deque 的对比

std::vector 与 std::deque 对比，主要区别可以总结为以下五点：

• (1) 头部插入与删除的效率

  • std::deque：对头部元素的插入与删除速度比 std::vector 快。
  • std::vector：对于头部的插入与删除效率极低，且数据量越大，效率越低（因为需要移动所有后续元素）。

• (2) 中间插入与删除的效率

  • std::deque：对中间元素的插入与删除速度比 std::vector 慢。
  • std::vector：在中间插入或删除元素时，虽然也需要移动元素，但整体效率通常优于 std::deque（因为 std::deque 的内部结构更复杂，移动元素可能涉及跨多个内存块的调整）。

• (3) 元素访问速度

  • std::vector：访问元素的速度比 std::deque 快。这与两者的内部实现有关
    • std::vector 内存完全连续，寻址只需一次指针偏移；
    • 而 std::deque 由多段连续内存空间拼接而成，访问时需要经过中控数组（map）的映射计算。
  • std::deque：虽然也支持随机访问，但随机访问速度略慢于 std::vector。

• (4) 内存布局与扩容机制

  • std::vector：内存空间完全连续，扩容时通常需要重新分配一块更大的连续内存，并迁移所有元素（导致迭代器失效）。
  • std::deque：由多段连续的固定大小内存块拼接而成，通过中控数组（map）管理。扩容时只需新增内存块，不需要搬移已有元素，因此其插入操作导致的迭代器失效情况比 std::vector 更温和（迭代器仅在特定条件下失效）。

• (5) 随机访问的底层复杂度

  • std::vector：支持真正的 O(1) 随机访问，可以直接通过首地址 + 偏移量定位元素。
  • std::deque：虽然也支持 O(1) 随机访问，但内部实现需要先计算元素位于哪个内存块，再计算块内偏移，因此常数系数比 std::vector 大，实际随机访问速度比 std::vector 稍慢。

deque 的使用

常见操作

• 声明

  • deque<int> deq;

• 插入

  • deq.push_back(20)，往尾部插入元素
  • deq.push_front(20)，往头部插入元素
  • deq.insert(iterator, 20)，往迭代器指向的位置插入元素

• 删除

  • deq.pop_back()，往尾部删除元素
  • deq.pop_front()，往头部删除元素
  • deq.erase(it)，删除迭代器指向的元素

• 查询

  • iterator：迭代器遍历

案例代码

#include <deque>
#include <iostream>

using namespace std;

class MyClass {
public:
    MyClass() {
        std::cout << "MyClass()" << std::endl;
    }

    MyClass(const MyClass& obj) {
        std::cout << "MyClass(const MyClass & obj)" << std::endl;
    }

    ~MyClass() {
        std::cout << "~MyClass()" << std::endl;
    }

private:
    int m_i = 0;
};

int main() {
    deque<MyClass> deq;

    for (int i = 0; i < 3; ++i) {
        cout << "---------- begin ----------" << endl;
        deq.push_back(MyClass());
        cout << "---------- end ------------" << endl;
    }

    for (int i = 0; i < deq.size(); ++i) {
        cout << "对象 deq[" << i << "] 的地址：" << &deq[i] << endl;
    }

    return 0;
}

程序运行输出的结果如下：

---------- begin ----------
MyClass()
MyClass(const MyClass & obj)
~MyClass()
---------- end ------------
---------- begin ----------
MyClass()
MyClass(const MyClass & obj)
~MyClass()
---------- end ------------
---------- begin ----------
MyClass()
MyClass(const MyClass & obj)
~MyClass()
---------- end ------------
对象 deq[0] 的地址：0x2bbaf2a16e0
对象 deq[1] 的地址：0x2bbaf2a16e4
对象 deq[2] 的地址：0x2bbaf2a16e8
~MyClass()
~MyClass()
~MyClass()

特别注意

像 std::vector 那样因旧空间不足而重新配置一块更大的空间，然后拷贝元素，再释放旧空间这样的事情不会发生在 std::deque 身上。值得一提的是，虽然上述案例代码输出的对象地址是连续的，但这并不代表 std::deque 分配的内存空间就一定是连续的；因为 std::deque 本质上是由一段一段的定量连续空间（分段连续内存空间）构造而成，一旦有必要在 std::deque 的头端或尾端增加新空间，便会配置一段新的定量连续空间，然后串接在整个 std::deque 的头端或尾端。

案例分析

上面这段案例代码使用 deque<MyClass> 创建双端队列，push_back(MyClass()) 每次先创建一个临时的 MyClass 对象，然后将其拷贝到 std::deque 内部，因此会调用一次默认构造函数和一次拷贝构造函数，临时对象随后被销毁；std::deque 不像 std::vector 那样要求所有元素存放在一整块连续内存中，而是采用 “map + 多个固定大小缓冲区（block）“ 的分段连续结构（如下图所示），map 本质上是一个指针数组，每个指针指向一个存放 MyClass 对象的 block，元素在同一个 block 内连续存储，当当前 block 空间不足时再分配新的 block。对于本案例只有 3 个 MyClass 对象，通常会落在同一个 block 中，因此通过 &deq[i] 可以看到三个 MyClass 对象的地址通常是连续递增的；但需要注意，deque 的整体元素内存并不保证连续，只有同一个 block 内的元素连续，不同 block 之间可能相距很远。最后 main() 函数结束时，std::deque 中保存的 3 个 MyClass 对象会依次析构并释放其内部存储空间。上述案例代码的分析图解如下：

案例优化

从上面这段案例代码的运行结果可以发现，将 MyClass 对象放入 std::deque 时，如果使用 deq.push_back(MyClass())，会额外拷贝一份临时对象，大大增加了内存开销。这是因为 deq.push_back(MyClass()) 会先创建一个临时的 MyClass 对象，然后 push_back() 再将这个临时对象拷贝到 std::deque 中。如果 MyClass 提供移动构造函数，可以通过移动构造避免这次拷贝。更推荐直接使用 deq.emplace_back()，它会直接在 std::deque 内部构造对象，避免先创建临时对象再拷贝 / 移动，因此在对象构造成本较高时更加合适。

#include <deque>
#include <iostream>

using namespace std;

class MyClass {
public:
    MyClass() {
        std::cout << "MyClass()" << std::endl;
    }

    MyClass(const MyClass& obj) {
        std::cout << "MyClass(const MyClass & obj)" << std::endl;
    }

    ~MyClass() {
        std::cout << "~MyClass()" << std::endl;
    }

private:
    int m_i = 0;
};

int main() {
    deque<MyClass> deq;

    for (int i = 0; i < 3; ++i) {
        cout << "---------- begin ----------" << endl;
        // 默认会调用 MyClass 的无参构造函数
        deq.emplace_back();
        cout << "---------- end ------------" << endl;
    }

    for (int i = 0; i < deq.size(); ++i) {
        cout << "对象 deq[" << i << "] 的地址：" << &deq[i] << endl;
    }

    return 0;
}

程序运行输出的结果如下：

---------- begin ----------
MyClass()
---------- end ------------
---------- begin ----------
MyClass()
---------- end ------------
---------- begin ----------
MyClass()
---------- end ------------
对象 deq[0] 的地址：0x2658eef16e0
对象 deq[1] 的地址：0x2658eef16e4
对象 deq[2] 的地址：0x2658eef16e8
~MyClass()
~MyClass()
~MyClass()

总结

push_back() 和 emplace_back() 最终都会让对象存放在容器自己的存储空间中，区别在于 push_back() 通常需要先有一个对象（比如临时对象），然后在容器自己的存储空间中，通过拷贝构造或移动构造创建一个新的对象；emplace_back() 则可以直接在容器自己的存储空间中构造对象，从而避免创建不必要的临时对象以及拷贝 / 移动操作。

list 容器

list 的概述

list 是一个双向链表容器，而且通常还是一个双向循环链表，可以高效地进行插入和删除元素。链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。相较于 vector 的连续线性空间，list 就显得负责许多，它的好处是每次插入或者删除一个元素，就是配置或者释放一个元素的空间。因此，list 对于空间的运用有绝对的精准，一点也不浪费。值得一提的是，对于任何位置的元素插入或元素的移除，list 永远是常数时间的耗时（效率较高）；但对于查询操作来说，list 的执行效率较低。

list 的结构

• 从 C++ 标准要求来看：std::list 是双向链表（doubly-linked list），但 C++ 标准并没有要求必须采用 “双向循环链表” 的具体实现。
• 在主流 STL 实现中：通常采用带哨兵节点的双向循环链表。例如 GCC 的 libstdc++、LLVM 的 libc++ 都采用了类似的设计。
• 哨兵节点不存储真正的 MyClass 元素，它主要用于简化 begin()、end()、插入和删除等操作。

总结

std::list 在语义上是一个双向链表，但 C++ 标准并未规定具体的底层实现；在主流 STL 实现中，通常采用带哨兵节点的双向循环链表结构，每个节点保存元素以及前后节点的指针，哨兵节点用于标识链表边界并简化插入、删除等操作。

list 的对比

std::vector 与 std::list 对比，主要区别可以总结为以下四点：

• (1) 底层数据结构与内存布局

  • std::vector：底层类似于数组，其内存空间是连续的。
  • std::list：底层是双向链表，内存空间并不连续（至少不要求连续）。

• (2) 插入与删除效率

  • std::vector：在头部或者中间插入 / 删除元素的效率比较低（因为需要移动后续元素）。
  • std::list：任意位置插入 / 删除元素的效率非常高（只需改变指针指向）。

• (3) 随机访问能力

  • std::vector：能够高效地支持随机存取（Random Access）。例如访问第 5 个元素，由于内存连续，可以直接通过计算地址瞬间定位元素。
  • std::list：做不到高效的随机存取。例如访问第 5 个元素，必须沿着链表从头开始一直找下去，直到找到第 5 个元素为止。

• (4) 扩容机制（内存管理）

  • std::vector：当内存不够时，会重新分配一块更大的内存，然后在新内存中重新构建对象，最后对原来的旧对象进行析构。
  • std::list：由于是链表结构，通常不涉及整体扩容和数据迁移的问题。

list 的使用

常见操作

• 声明

  • list<int> mylist;

• 插入

  • mylist.push_back(20)，往尾部插入元素
  • mylist.push_front(20)，往头部插入元素
  • mylist.insert(iterator, 20)，往迭代器指向的位置插入元素

• 删除

  • mylist.pop_back()，往尾部删除元素
  • mylist.pop_front()，往头部删除元素
  • mylist.erase(it)，删除迭代器指向的元素

• 查询

  • iterator：迭代器遍历

链表的特性

• 链表采用动态内存分配，不会造成内存浪费和溢出。
• 链表虽然灵活，但是空间和时间的额外耗费较大。
• 链表执行插入和删除操作都十分方便，仅修改指针即可实现，不需要移动大量元素。
• 链表的访问效率比数组要低，适合需要频繁插入、删除元素的场景（读少写多）。
• 链表不可以随机存取元素，所以不支持 at.(pos) 函数与 [] 操作符的使用。

案例代码

#include <iostream>
#include <list>

using namespace std;

class MyClass {
public:
    MyClass() {
        std::cout << "MyClass()" << std::endl;
    }

    MyClass(const MyClass& obj) {
        std::cout << "MyClass(const MyClass & obj)" << std::endl;
    }

    ~MyClass() {
        std::cout << "~MyClass()" << std::endl;
    }

private:
    int m_i = 0;
};

int main() {
    list<MyClass> list;

    for (int i = 0; i < 3; ++i) {
        cout << "---------- begin ----------" << endl;
        list.push_back(MyClass());
        cout << "---------- end ------------" << endl;
    }

    int i = 1;
    for (auto iter = list.begin(); iter != list.end(); ++iter) {
        cout << "第 " << i << " 个对象的地址：" << &(*iter) << endl;
        ++i;
    }

    return 0;
}

程序运行输出的结果如下：

---------- begin ----------
MyClass()
MyClass(const MyClass & obj)
~MyClass()
---------- end ------------
---------- begin ----------
MyClass()
MyClass(const MyClass & obj)
~MyClass()
---------- end ------------
---------- begin ----------
MyClass()
MyClass(const MyClass & obj)
~MyClass()
---------- end ------------
第 1 个对象的地址：0x1c8344d16a0
第 2 个对象的地址：0x1c8344d16c0
第 3 个对象的地址：0x1c8344d16e0
~MyClass()
~MyClass()
~MyClass()

案例分析

上面这段案例代码使用 list<MyClass> 创建双向链表，push_back(MyClass()) 每次先创建一个临时的 MyClass 对象，然后将其拷贝到 std::list 内部的链表节点中，因此会调用一次默认构造函数和一次拷贝构造函数，临时对象随后被销毁。std::list 不要求所有元素存放在连续内存中，而是采用链表节点的存储结构，每个节点通常包含一个 MyClass 对象以及指向前后节点的指针，各个节点通过指针连接起来。对于本案例只有 3 个 MyClass 对象，它们分别存放在不同的链表节点中，因此通过 &(*iter) 可以看到三个 MyClass 对象的地址通常是不连续的。也就是说，**list 中的元素本身不是连续存储的，每个元素都位于独立的链表节点中 **。最后 main() 函数结束时，std::list 中保存的 3 个 MyClass 对象会依次析构，同时释放对应的链表节点内存。上述案例代码的分析图解如下：

案例优化

从上面这段案例代码的运行结果可以发现，将 MyClass 对象放入 std::list 时，如果使用 list.push_back(MyClass())，会额外拷贝一份临时对象，大大增加了内存开销。这是因为 list.push_back(MyClass()) 会先创建一个临时的 MyClass 对象，然后 push_back() 再将这个临时对象拷贝到 std::list 的链表节点中。如果 MyClass 提供移动构造函数，可以通过移动构造避免这次拷贝。更推荐直接使用 list.emplace_back()，它会直接在 std::list 的链表节点中构造对象，避免先创建临时对象再拷贝 / 移动，因此在对象构造成本较高时更加合适。

#include <iostream>
#include <list>

using namespace std;

class MyClass {
public:
    MyClass() {
        std::cout << "MyClass()" << std::endl;
    }

    MyClass(const MyClass& obj) {
        std::cout << "MyClass(const MyClass & obj)" << std::endl;
    }

    ~MyClass() {
        std::cout << "~MyClass()" << std::endl;
    }

private:
    int m_i = 0;
};

int main() {
    list<MyClass> list;

    for (int i = 0; i < 3; ++i) {
        cout << "---------- begin ----------" << endl;
        // 默认会调用 MyClass 的无参构造函数
        list.emplace_back();
        cout << "---------- end ------------" << endl;
    }

    int i = 1;
    for (auto iter = list.begin(); iter != list.end(); ++iter) {
        cout << "第 " << i << " 个对象的地址：" << &(*iter) << endl;
        ++i;
    }

    return 0;
}

程序运行输出的结果如下：

---------- begin ----------
MyClass()
---------- end ------------
---------- begin ----------
MyClass()
---------- end ------------
---------- begin ----------
MyClass()
---------- end ------------
第 1 个对象的地址：0x1a308a216a0
第 2 个对象的地址：0x1a308a216c0
第 3 个对象的地址：0x1a308a216e0
~MyClass()
~MyClass()
~MyClass()

容器适配器（Adapter）

stack

stack 的概述

stack 是 C++ STL 提供的一种栈容器适配器（Container Adapter），遵循 “后进先出（LIFO）” 原则，只允许在栈顶进行元素的插入、删除和访问。stack 本身并不负责实际的数据存储，而是基于其他序列容器进行封装，默认底层容器为 deque，也可以使用 vector、list 等满足接口要求的容器。push()、pop()、top() 等操作实际上都是对底层容器对应操作的封装，例如栈顶通常对应底层容器的尾部，因此 stack 可以理解为在底层容器之上限制操作范围，从而实现标准的栈行为。

stack 的使用

#include <iostream>
#include <stack>

int main() {
    // 栈容器（先进后出 - LIFO）
    std::stack<int> st;

    for (int i = 0; i < 5; ++i) {
        // 入栈
        st.push(i);
    }

    while (!st.empty()) {
        // 获取栈顶的元素
        std::cout << st.top() << " ";
        // 出栈
        st.pop();
    }

    return 0;
}

程序运行输出的结果如下：

4 3 2 1 0 

queue

queue 的概述

queue 是 C++ STL 提供的一种队列容器适配器（Container Adapter），遵循 “先进先出（FIFO）” 原则，只允许在队尾插入元素、队头删除和访问元素。queue 本身并不负责实际的数据存储，而是基于其他序列容器进行封装，默认底层容器为 deque，也可以使用 list 等满足要求的容器。push()、pop()、front()、back() 等操作本质上都是对底层容器相应操作的封装，其中队列的队头对应底层容器的 front()，队尾对应 back()，因此 queue 可以理解为在底层容器之上限制可用操作，从而实现标准的先进先出队列行为。

queue 的使用

#include <iostream>
#include <queue>

int main() {
    // 队列容器（先进先出 - FIFO）
    std::queue<int> que;

    for (int i = 0; i < 5; ++i) {
        // 入队
        que.push(i);
    }

    while (!que.empty()) {
        // 获取队头的元素
        std::cout << que.front() << " ";
        // 出队
        que.pop();
    }

    return 0;
}

程序运行输出的结果如下：

0 1 2 3 4 

分配器（Allocator ）

分配器的概述

C++ STL 中的分配器（Allocator）主要负责为容器提供内存的分配与释放机制，将 “内存管理” 和 “容器的数据结构、元素管理” 进行分离。STL 容器通常通过分配器申请存储元素所需的原始内存，再在这块内存上构造和销毁对象，从而避免容器直接依赖具体的内存分配方式。C++ 标准库提供了默认的 std::allocator，同时也允许开发者根据实际需求实现自定义分配器，例如用于内存池、对象池或特殊内存管理场景。因此，分配器可以理解为 STL 容器底层的内存管理抽象层，主要解决 “从哪里获取内存、如何释放内存” 等问题，而对象的构造、销毁以及容器自身的数据结构则由容器负责实现。值得一提的是，在现代 C++ 标准库实现中，std::allocator 通常主要负责通过底层动态内存分配机制获取和释放内存，并不要求必须实现专门的内存池；具体是否存在缓存、批量分配、线程缓存等优化，属于 C++ 标准库内部实现细节，不同编译器和 C++ 标准库版本的实现可能存在差异。

C++ 内存池的介绍与实现

• C++ 内存池的简单实现
• Nginx 内存池源码剖析
• SGI STL 内存池源码剖析

分配器的使用

案例代码一

#include <iostream>
#include <list>

int main() {
    std::list<int> myList1;

    // 指定分配器，等效于上面的写法，因为 std::allocator 是默认分配器
    std::list<int, std::allocator<int>> myList2;

    for (int i = 0; i < 5; ++i) {
        myList2.push_back(i);
    }

    for (int& iter : myList2) {
        std::cout << &iter << std::endl;
    }

    return 0;
}

案例代码二

#include <iostream>
#include <list>

int main() {
    // 定义一个 allocator 对象，为 int 类型对象分配内存
    std::allocator<int> alloc;

    // 通过 allocate() 分配一段原始的未构造的内存，这段内存能够保存 3 个类型为 int 的对象（12 个字节）
    int* p = alloc.allocate(3);

    // 在这块内存中使用 3 个 int 对象
    int* q = p;
    *q = 1;
    q++;
    *q = 2;
    q++;
    *q = 3;

    // 通过 deallocate() 释放内存，第二个参数必须与 allocate() 的数量对应，记住分配了几个对象的内存，就要正确释放几个对象的内存
    alloc.deallocate(p, 3);

    return 0;
}

其他的分配器

在下图中，展示的是 SGI STL（候捷老师在《STL 源码剖析》中深入剖析的版本）中经典的二级空间配置器（allocator）的内部结构，具体来说是其自由链表（free-list）与内存池（memory pool）的协同工作机制，底层的源码剖析可以参考 SGI STL 内存池源码剖析。

顶部从 #0 到 #15 的 16 个槽位代表自由链表数组，分别负责管理大小为 8、16、24 …… 直至 128 字节的内存块，即以 8 个字节为步长进行对齐。图中各个槽位下方悬挂的方块就是对应大小的空闲内存块，它们通过指针串联成单向链表。当应用程序申请不超过 128 字节的内存时，配置器会将申请大小向上调整为 8 的倍数，然后从对应的自由链表中直接摘取第一个可用内存块；如果对应的自由链表为空，则会触发 refill 操作，从内存池中申请一大块连续内存，并将其切割成多个固定大小的小块，其中一块返回给调用者，其余小块挂入对应的自由链表中。当内存池中的空间也不足时，配置器才会进一步通过 malloc() 向系统堆申请内存。这种设计通过减少频繁调用系统内存分配接口的次数，降低小块内存分配的开销，并在一定程度上减少外部内存碎片，从而提高小对象内存分配的效率。