【C++篇】深入剖析C++ Vector底层源码及实现机制

Ne0inhk

— 15 min read
【C++篇】深入剖析C++ Vector底层源码及实现机制

文章目录

须知

💬 欢迎讨论：如果你在学习过程中有任何问题或想法，欢迎在评论区留言，我们一起交流学习。你的支持是我继续创作的动力！

👍 点赞、收藏与分享：觉得这篇文章对你有帮助吗？别忘了点赞、收藏并分享给更多的小伙伴哦！你们的支持是我不断进步的动力！
🚀 分享给更多人：如果你觉得这篇文章对你有帮助，欢迎分享给更多对C++感兴趣的朋友，让我们一起进步！

 全面剖析vector底层及实现机制

接上篇：【C++篇】探索STL之美：vector容器讲解_c++vector容器-ZEEKLOG博客

前言

 Vector是C++标准模板库（STL）中提供的一种动态数组容器，能够高效管理元素的存储与操作。它具有自动扩容的特性，即在存储空间不足时会自动分配更大的内存，保证连续存储的同时提高了灵活性。Vector支持随机访问，拥有接近数组的访问速度，同时也提供了丰富的成员函数用于插入、删除、排序等操作，兼顾了灵活性与性能。

总之，Vector是C++开发中最常用的容器之一，因其高效、灵活、易用的特性，在处理动态数据时显得尤为重要。

1. 基本结构与初始化（具有不同种方式）

1.1 基本结构

Vector底层实现类似于动态数组，其内部通过一块连续的内存空间存储元素。主要成员包括：

  • 指针数据（_start, _end, _end_of_storage）：分别指向当前元素的起始地址、末尾地址和存储空间的尾地址，用于跟踪已存储的元素和剩余空间。
  • 动态扩容：当插入新元素超出当前容量时，Vector会申请更大的连续内存空间，并将现有元素复制到新空间中。扩容一般是以一定倍数增长（通常为2倍）。

1.2 带大小和默认值初始化构造函数

  • 初始化一个给定大小的vector，并使用默认值填充。
  • 测试构造后大小、容量是否符合要求。
namespace W { template<class T> class vector { public: typedef T* iterator; vector(size_t n, const T& value = T()) { _start = new T[n]; _finish = _start + n; _endOfStorage = _finish; for (size_t i = 0; i < n; ++i) { _start[i] = value; // 填充默认值 } } size_t size() const { return _finish - _start; } size_t capacity() const { return _endOfStorage - _start; } bool empty() const { return _start == _finish; } T& operator[](size_t pos) { return _start[pos]; } ~vector() { if (_start) { delete[] _start; _start = _finish = _endOfStorage = nullptr; } } private: iterator _start; iterator _finish; iterator _endOfStorage; }; }

测试用例：

void TestInitVector() { W::vector<int> v(5, 10); assert(v.size() == 5); // 验证大小 assert(v.capacity() == 5); // 验证容量 assert(!v.empty()); // 验证非空 for (size_t i = 0; i < 5; ++i) { assert(v[i] == 10); // 验证默认值 } std::cout << "TestInitVector passed" << std::endl; }

1.3 拷贝构造函数

  • 实现vector的拷贝构造函数。
  • 测试拷贝后的vector是否完全复制原来的内容和容量。

实现代码：

namespace W { template<class T> class vector { public: typedef T* iterator; vector(const vector<T>& v) { size_t n = v.size(); _start = new T[n]; _finish = _start + n; _endOfStorage = _finish; for (size_t i = 0; i < n; ++i) { _start[i] = v._start[i]; // 复制数据 } } size_t size() const { return _finish - _start; } size_t capacity() const { return _endOfStorage - _start; } bool empty() const { return _start == _finish; } T& operator[](size_t pos) { return _start[pos]; } ~vector() { if (_start) { delete[] _start; _start = _finish = _endOfStorage = nullptr; } } private: iterator _start; iterator _finish; iterator _endOfStorage; }; }

测试用例：

void TestCopyVector() { W::vector<int> v1(10, 20); W::vector<int> v2(v1); assert(v2.size() == 10); // 验证大小 assert(v2.capacity() == 10); // 验证容量 for (size_t i = 0; i < 10; ++i) { assert(v2[i] == 20); // 验证数据拷贝 } std::cout << "TestCopyVector passed" << std::endl; }

1.4 赋值操作符重载

  • 实现赋值操作符重载。
  • 测试两个vector赋值后，是否正确拷贝了内容和容量。
namespace W { template<class T> class vector { public: typedef T* iterator; vector<T>& operator=(const vector<T>& v) { if (this != &v) { delete[] _start; // 释放旧的空间 size_t n = v.size(); _start = new T[n]; _finish = _start + n; _endOfStorage = _finish; for (size_t i = 0; i < n; ++i) { _start[i] = v._start[i]; // 复制数据 } } return *this; } size_t size() const { return _finish - _start; } size_t capacity() const { return _endOfStorage - _start; } bool empty() const { return _start == _finish; } T& operator[](size_t pos) { return _start[pos]; } ~vector() { if (_start) { delete[] _start; _start = _finish = _endOfStorage = nullptr; } } private: iterator _start; iterator _finish; iterator _endOfStorage; }; }

测试用例：

void TestAssignVector() { W::vector<int> v1(15, 30); W::vector<int> v2 = v1; // 赋值操作 assert(v2.size() == 15); // 验证大小 assert(v2.capacity() == 15); // 验证容量 for (size_t i = 0; i < 15; ++i) { assert(v2[i] == 30); // 验证数据拷贝 } std::cout << "TestAssignVector passed" << std::endl; }

2. 容器管理内存的实现与测试

2.1 reserve函数：动态扩容

实现代码：

namespace W { template<class T> class vector { public: void reserve(size_t n) { if (n > capacity()) { size_t oldSize = size(); T* tmp = new T[n]; for (size_t i = 0; i < oldSize; ++i) { tmp[i] = _start[i]; } delete[] _start; _start = tmp; _finish = _start + oldSize; _endOfStorage = _start + n; } } }; }

测试用例：

void TestReserveVector() { W::vector<int> v(5, 10); v.reserve(10); // 预留容量 assert(v.capacity() == 10); // 验证容量扩展 for (size_t i = 0; i < 5; ++i) { assert(v[i] == 10); // 验证数据保持不变 } std::cout << "TestReserveVector passed" << std::endl; }

输出

TestReserveVector passed

 2.2 resize函数：改变大小

用途

1. 增加容器大小

当新的大小大于当前大小时，resize会在容器末尾添加新元素，新添加的元素会被默认值初始化（对于内置类型，默认值通常为0或空值）。

std::vector<int> vec = {1, 2, 3};
vec.resize(5); // vec变为 {1, 2, 3, 0, 0}

2. 减少容器大小
当新的大小小于当前大小时，resize会移除多余的元素，只保留从起始位置算起的新大小的元素。

std::vector<int> vec = {1, 2, 3, 4, 5};
vec.resize(3); // vec变为 {1, 2, 3} 

 3.指定新元素的初始值
在扩容时，可以通过第二个参数指定新添加元素的初始值，而不是使用默认值。

std::vector<int> vec = {1, 2, 3};
vec.resize(5, 10); // vec变为 {1, 2, 3, 10, 10}

特点

  • 不会影响容量（capacity）：resize只调整size（实际元素数量），不会改变容器的容量（底层分配的内存大小）。扩容时容量可能会增长，但缩小时容量不会减少。
  • 元素保留特性：缩小时多余的元素会被移除，但未移除的元素保持不变；扩容时已存在的元素同样不受影响。
  • 性能：resize可能引起新元素的构造或旧元素的析构，因此需要注意其性能开销。
namespace W { template<class T> class vector { public: void resize(size_t n, const T& value = T()) { if (n < size()) { _finish = _start + n; // 缩小大小 } else { reserve(n); for (iterator it = _finish; it != _start + n; ++it) { *it = value; // 填充新值 } _finish = _start + n; } } }; }

测试用例：

void TestResizeVector() { W::vector<int> v(5, 10); v.resize(8, 20); // 扩展大小并填充新值 assert(v.size() == 8); // 验证扩展后大小 for (size_t i = 0; i < 5; ++i) { assert(v[i] == 10); // 验证原值不变 } for (size_t i = 5; i < 8; ++i) { assert(v[i] == 20); // 验证新值 } std::cout << "TestResizeVector passed" << std::endl; }

3. 增加与删除元素

3.1 push_back函数：向vector末尾插入元素

3.1.1 实现思路

  1. 检查容量是否足够，若不足则扩容（通常容量加倍）。
  2. 将新元素插入到当前末尾。
  3. 更新_finish指针，指向新的末尾。

示例代码：

namespace W { template<class T> class vector { public: void push_back(const T& x) { // 如果空间不足，扩展容量为当前容量的两倍 if (_finish == _endOfStorage) { size_t newCapacity = capacity() == 0 ? 1 : capacity() * 2; reserve(newCapacity); } // 在末尾插入新元素 *_finish = x; ++_finish; } private: T* _start; T* _finish; T* _endOfStorage; }; }

 测试用例：

void TestPushBackVector() { W::vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); assert(v.size() == 3); // 验证插入后的大小 assert(v.capacity() >= 3); // 验证容量是否自动扩容 assert(v[0] == 1 && v[1] == 2 && v[2] == 3); // 验证插入的元素是否正确 std::cout << "TestPushBackVector passed" << std::endl; }

输出：

TestPushBackVector passed

 3.2 pop_back函数：删除末尾元素

 将_finish指针向后移动移动一位，即该指针指向的就是最后一个元素

示例代码：

namespace W { template<class T> class vector { public: void pop_back() { assert(_finish != _start); // 确保vector非空 --_finish; // 逻辑删除最后一个元素 } private: T* _start; T* _finish; T* _endOfStorage; }; }

3.3 insert：在指定位置插入数据

实现思路

1 检查容量，不足扩容

2 将指定的数据从后往前挪动，空出该位置

3 将该位置插入指定数据

4 更新finish指针

实现代码：

namespace W { template<class T> class vector { public: T* insert(T* pos, const T& value) { assert(pos >= _start && pos <= _finish); // 确保pos是有效指针 // 检查空间是否足够 if (_finish == _endOfStorage) { size_t newCapacity = capacity() == 0 ? 1 : capacity() * 2; size_t offset = pos - _start; // 记录插入位置 reserve(newCapacity); // 扩容 pos = _start + offset; // 更新插入位置 } // 将插入位置之后的元素整体向后移动 for (T* it = _finish; it > pos; --it) { *it = *(it - 1); } // 插入新元素 *pos = value; ++_finish; return pos; } private: T* _start; T* _finish; T* _endOfStorage; }; }

4 erase函数：删除指定位置的元素

实现思路

1 循环将指定位置数据的后面每一位向前挪动

2 更新finish指针

实现代码：

namespace W { template<class T> class vector { public: T* erase(T* pos) { assert(pos >= _start && pos < _finish); // 确保pos是有效指针 // 将pos之后的元素向前移动 for (T* it = pos; it < _finish - 1; ++it) { *it = *(it + 1); } --_finish; // 更新_finish指针 return pos; } private: T* _start; T* _finish; T* _endOfStorage; }; }

4. 查找元素

4.1 front函数：返回vector的第一个元素

实现代码：

namespace W { template<class T> class vector { public: T& front() { assert(!empty()); // 确保vector非空 return *_start; // 返回第一个元素 } private: T* _start; T* _finish; T* _endOfStorage; }; }

测试用例：

void TestFrontVector() { W::vector<int> v; v.push_back(10); assert(v.front() == 10); // 验证front v.push_back(20); assert(v.front() == 10); // 验证front不变 std::cout << "TestFrontVector passed" << std::endl; }

输出：

TestFrontVector passed

4.2 back函数：获取最后一个元素

实现代码：

namespace W {
    template<class T>
    class vector {
    public:
        T& back() {
            assert(!empty());  // 确保vector非空
            return *(_finish - 1);  // 返回最后一个元素
        }

    private:
        T* _start;
        T* _finish;
        T* _endOfStorage;
    };
}

测试用例：

void TestBackVector() { W::vector<int> v; v.push_back(10); assert(v.back() == 10); // 验证back v.push_back(20); assert(v.back() == 20); // 验证back变化 std::cout << "TestBackVector passed" << std::endl; }

 5. 迭代器的实现

  • begin 函数返回指向 vector 起始位置的迭代器（即指向第一个元素）。
  • end 函数返回指向 vector 末尾的迭代器（即指向最后一个元素的下一个位置）。
  • 两者结合可以用于遍历 vector 中的元素。

实现代码：
 

namespace W { template<class T> class vector { public: typedef T* iterator; iterator begin() { return _start; } iterator end() { return _finish; } private: T* _start; T* _finish; T* _endOfStorage; }; }

测试用例：

void TestIteratorVector() { W::vector<int> v; v.push_back(10); v.push_back(20); v.push_back(30); // 使用迭代器遍历 vector for (W::vector<int>::iterator it = v.begin(); it != v.end(); ++it) { std::cout << *it << " "; } std::cout << std::endl; }

输出：

10   20   30

 6. swap函数：交换两个vector

用途：

  • swap 函数用于交换两个 vector 的内容，包括它们的起始指针、结束指针和容量指针。
  • swap 函数是常用的优化操作，特别是在实现移动语义时能大大提高效率。

实现代码：

namespace W { template<class T> class vector { public: void swap(vector<T>& v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_endOfStorage, v._endOfStorage); } private: T* _start; T* _finish; T* _endOfStorage; }; }

 测试用例：

void TestSwapVector() { W::vector<int> v1; W::vector<int> v2; v1.push_back(1); v1.push_back(2); v2.push_back(3); v2.push_back(4); v1.swap(v2); // 验证 v1 和 v2 交换后内容是否正确 for (auto e : v1) { std::cout << e << " "; } std::cout << std::endl; for (auto e : v2) { std::cout << e << " "; } std::cout << std::endl; }

输出：

3 4 
1 2 

 7. 赋值运算符重载：深拷贝vector

 现代技术：拷贝并交换（Copy and Swap） 技术，这种技术可以减少重复代码并提高异常安全性。

实现代码：

namespace W { template<class T> class vector { public: //这里可以服用reserve和push_back函数了 vector(const vector<T>& v) : _start(nullptr), _finish(nullptr), _endOfStorage(nullptr) { reserve(v.size()); // 分配所需空间 for (const T& elem : v) { push_back(elem); // 拷贝每个元素 } } // 赋值操作符，使用拷贝并交换技术 vector<T>& operator=(vector<T> v) { swap(v); // 调用 swap 函数交换内容 return *this; } // swap 函数 void swap(vector<T>& v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_endOfStorage, v._endOfStorage); } // 其他成员函数同之前实现... private: T* _start; T* _finish; T* _endOfStorage; }; }

测试用例：

void TestCopyAndAssignVector() { // 测试拷贝构造函数 W::vector<int> v1; v1.push_back(1); v1.push_back(2); v1.push_back(3); W::vector<int> v2(v1); // 使用拷贝构造函数 for (size_t i = 0; i < v2.size(); ++i) { assert(v2[i] == v1[i]); // 验证每个元素是否相同 } // 测试赋值操作符 W::vector<int> v3; v3 = v1; // 使用赋值操作符 for (size_t i = 0; i < v3.size(); ++i) { assert(v3[i] == v1[i]); // 验证每个元素是否相同 } std::cout << "TestCopyAndAssignVector passed" << std::endl; }
现代写法解释 ：

传值参数：通过传递 vector<T> 的值作为参数，创建一个临时对象 v。调用拷贝构造函数时自动执行拷贝，然后在赋值操作中与现有对象交换内容。传值是安全的，避免了手动内存管理问题。
swap：通过交换数据成员 _start、_finish 和 _endOfStorage，避免手动内存释放，简化代码逻辑。交换后的临时对象 v 离开作用域时自动销毁，保证资源释放。


 8. vector容器特性总结

1. 动态大小

  • 可以根据需要动态调整大小，而无需预定义固定容量，避免内存浪费。
  • 自动处理底层内存分配和扩展。

2. 随机访问性能优秀

  • 支持常数时间的随机访问，类似于数组，便于快速读取和修改元素。

3. 便捷的插入和删除操作

  • 支持尾部插入/删除操作，时间复杂度为O(1)。
  • 通过erase和insert等方法，支持中间位置的元素操作，虽然复杂度为O(n)，但提供了便利。

4. 内存管理

  • 自动管理底层内存，不需要开发者手动分配或释放内存，减少内存泄漏的风险。

5. 支持迭代器

  • 提供灵活的迭代器支持，可以轻松遍历、修改元素，并与其他STL算法结合使用。

6. 多功能性

  • 可以存储不同类型的对象，包括用户定义类型。
  • 提供了丰富的操作函数，例如排序、搜索等。

7. 与C++标准库兼容性高

  • 与标准库中的其他容器（如map、set）和算法无缝集成，形成强大的工具组合。

8. 性能优化

  • 在扩容时，底层内存分配采用指数增长策略（通常为两倍），减少了频繁的重新分配操作

这些特点使vector在需要灵活、动态数组的场景中非常实用，例如处理未知大小的输入数据或需要高效随机访问的场景。

 

相信通过这篇文章你对C++STL->vector的使用高级部分的有了初步的了解。如果此篇文章对你学习C++有帮助，期待你的三连，你的支持就是我创作的动力！！！

下一篇文章再会.

Read more

鸿蒙金融理财全栈项目——合规审计、风险控制、产品创新优化

鸿蒙金融理财全栈项目——合规审计、风险控制、产品创新优化

《鸿蒙APP开发从入门到精通》第21篇：鸿蒙金融理财全栈项目——合规审计、风险控制、产品创新优化 📊🛡️🚀 内容承接与核心价值 这是《鸿蒙APP开发从入门到精通》的第21篇——合规审计、风险控制、产品创新优化篇，100%承接第20篇的运维监控、性能优化、安全加固架构，并基于金融场景的合规审计、风险控制、产品创新要求，设计并实现鸿蒙金融理财全栈项目的合规审计、风险控制、产品创新优化功能。 学习目标： * 掌握鸿蒙金融理财项目的合规审计优化设计与实现； * 实现合规审计自动化、合规审计报告优化、合规审计风险预警； * 理解风险控制优化在金融场景的核心设计与实现； * 实现风险评估自动化、风险监控实时化、风险预警智能化； * 掌握产品创新优化在金融场景的设计与实现； * 实现产品创新敏捷化、产品创新数据化、产品创新生态化； * 优化金融理财项目的用户体验（合规审计、风险控制、产品创新优化）。 学习重点： * 鸿蒙金融理财项目的合规审计优化设计原则； * 风险控制优化在金融场景的应用； * 产品创新优化在金融场景的设计要点。 一、 合规审计优化基础

By Ne0inhk
盘点十大国产 AI 大模型工具推荐：Deepseek、豆包、Kimi、秘塔AI、文心一言、智谱轻言、通义千问、元宝、360 纳米搜索、天工 AI

盘点十大国产 AI 大模型工具推荐：Deepseek、豆包、Kimi、秘塔AI、文心一言、智谱轻言、通义千问、元宝、360 纳米搜索、天工 AI

工欲善其事，必先利其器。我们要用好人工智能，首先对一些主流通用的 AI 工具有一个较为全面的了解，才能够将它用到匹配场景，产生预期的效益。 以下是我结合自己日常用且感觉好用的AI 工具，梳理下来刚好十个。方便大家自行阅读快速了解。拿走不谢！  ps：这篇是小白入门贴，高手可略过哈~ 工具一：Deepseek 官网： https://www.deepseek.com 🌟 功能亮点： * 深度思考强：出身于金融公司，数学好、逻辑推理强，因而适合复杂逻辑对话； ⚠️同时也要留意幻觉现象，对生成结果要做人工审核。 * 中文语境强：在中文精准理解和表达方面优秀，能很好地理解懂中国文化和中国国情，包括一些人情世故和职场黑话。 免费或性价比高：对普通用户免费可用，支持文件上传解析；对企业性价比高，调用API也很便宜。 工具二：豆包 官网：https://www.doubao.com 🌟 功能亮点： • 语音交互天花板：内置&

By Ne0inhk
Flutter 组件 serverpod_swagger 的鸿蒙化适配实战 - 自动化生成后端映射、Swagger UI 桥接与 API 交互效率提升方案

Flutter 组件 serverpod_swagger 的鸿蒙化适配实战 - 自动化生成后端映射、Swagger UI 桥接与 API 交互效率提升方案

欢迎加入开源鸿蒙跨平台社区：https://openharmonycrossplatform.ZEEKLOG.net Flutter 组件 serverpod_swagger 的鸿蒙化适配实战 - 自动化生成后端映射、Swagger UI 桥接与 API 交互效率提升方案 前言 在现代的全栈 Flutter 开发架构中，Serverpod 以其“代码即协议”的理念，打破了前后端通信的繁冗壁垒。然而，当后端模型不断膨胀，如何让前端（尤其是正在飞速扩张的鸿蒙端）开发者能够直观地查看、调试并自动生成对应的 API 调用代码？ serverpod_swagger 应运而生。它是 Serverpod 生态中负责生成符合 OpenAPI 标准（Swagger）协议的核心模块，能够将复杂的后端 Model 和 Endpoint 瞬间转化为标准的 Swagger

By Ne0inhk
拖延症福音：AI论文软件 千笔ai写作 VS 灵感ai

拖延症福音：AI论文软件 千笔ai写作 VS 灵感ai

随着人工智能技术的迅猛迭代与普及，AI辅助写作工具已逐步渗透到高校学术写作场景中，成为本科生、研究生完成毕业论文不可或缺的辅助手段。越来越多面临毕业论文压力的学生，开始依赖各类AI工具简化写作流程、提升创作效率。但与此同时，市场上涌现的AI写作工具良莠不齐、功能各异，许多学生在海量选择中陷入“选择困难”与深层困惑——既担心工具专业性不足、无法适配学术写作规范，又顾虑工具效率低下、难以真正解决论文写作中的核心难题，在反复筛选、尝试中浪费大量宝贵时间，愈发陷入毕业论文的焦虑困境。在此背景下，千笔AI凭借其在学术写作场景中突出的高效性与严谨的专业性，在众多同类工具中脱颖而出，成为备受正在为毕业论文苦恼的学生关注的优选辅助工具。 一、强烈推荐：千笔AI —— 一站式学术支持“专家”，降低AI的性价比之选（推荐指数：★★★★★） 千笔AI针对学生论文写作的痛点，精心打造了八大核心功能，让论文写作变得前所未有的高效和规范。 1. 免费AI辅助选题：精准定位，快速确定研究方向 千笔AI的免费AI辅助选题功能，基于深度学习算法分析近5年顶刊论文和会议文献，构建学科知识图谱，帮助你快速确定一个既有

By Ne0inhk