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

STL编程之vector

article 2025/9/13 12:22:16

vector的基础概念：类

#include<iostream>
#include<vector>
using namespace std;int main() {int a[6] = {1,2,4,5,6,7};vector<int> v = { 1,3,6,8 };cout << v.capacity() << endl;v.push_back(8);cout << v.capacity() << endl;cout << "begin: ->" << *v.begin() << endl;cout << "end: ->" << *(v.end()-1) << endl;cout << "front: ->" << v.front() << endl;cout << "back: ->" << v.back() << endl;return 0;
}
[ 10 ]  [ 20 ]  [ 30 ]  [空位置]↑             ↑        ↑
begin()         end()-1  end()

创建对象

#include<iostream>
#include<vector>
using namespace std;void printfVector(vector<int>& v) {for (vector<int>::iterator iter = v.begin(); iter != v.end();iter++	) {cout << *iter << " ";}cout << endl;
}int main() {//1.默认构造函数()不会放入任何数据vector<int> v1;printfVector(v1);//2初始化列表vector<int> v2_1 = { 1,0,5,7 };cout << "v2_1:";printfVector(v2_1);vector<int> v2_2({ 1,4,5,7 });cout << "v2_2:";printfVector(v2_2);// 3.迭代器vector<int> v3(v2_1.begin(), v2_1.end());cout << "v3:";printfVector(v3);//4.全0初始化vector<int> v4(8);cout << "v4:";printfVector(v4);//5.vector<int> 变量名(a, b);申请a个空间的元素,每个元素的值初始化为 bvector<int> v5(8, 6);cout << "v5:";printfVector(v5);//6.拷贝构造函数vector<int> v6(v2_2);cout << "v6:";printfVector(v6);vector<int> v()return 0;
}

vector 赋值操作

#include <iostream>
#include <vector>// 打印vector的函数定义
void printVector(const std::vector<int>& v) {for (int num : v) {std::cout << num << " ";}std::cout << std::endl;
}int main() {std::vector<int> v1 = {1, 2, 3};std::cout << "v1:";printVector(v1);// 1.赋值操作vector<int> v1_1 = v1;printVector(v1_1);// 2. assign(迭代器)std::vector<int> v2;v2.assign(v1.begin(), v1.end());std::cout << "v2:";printVector(v2);// 3. 初始化列表std::vector<int> v3;v3.assign({ 1,2,3,4,5,6 });std::cout << "v3:";printVector(v3);// 4. 初始化 a 个 bstd::vector<int> v4;v4.assign(8, 6);std::cout << "v4:";printVector(v4);return 0;
}

数据插入 数据删除

#include <iostream>
#include <vector>// 打印vector的函数定义
void printVector(const std::vector<int>& v) {for (int num : v) {std::cout << num << " ";}std::cout << std::endl;
}int main() {std::vector<int> v;for (int i = 0; i < 10; ++i) {v.push_back(i);}printVector(v);v.insert(v.begin(), 888);printVector(v);return 0;
}

vector 扩容机制

当向 vector 添加元素（如 push_back、emplace_back、insert 等）导致当前元素数量（size）超过预分配的内存容量（capacity）时，自动扩容会被触发。

2. 扩容的基本步骤

  1. 分配新内存：分配一块更大的连续内存空间（通常是当前容量的倍数）。

  2. 迁移元素：将旧内存中的所有元素拷贝/移动到新内存中。

  3. 释放旧内存：销毁旧内存中的元素并释放内存。

  4. 更新指针：将内部指针指向新内存，更新 size 和 capacity。

3. 扩容的增长因子

std::vector<int> v;
for (int i=0; i<10; i++) {v.push_back(i);std::cout << "Size: " << v.size() << ", Capacity: " << v.capacity() << std::endl;
}

不同编译器的实现策略不同，但核心目标是平衡时间和空间效率：

  • 常见策略：容量按几何级数增长（如 2× 或 1.5×）。

    • GCC (libstdc++)：扩容为当前容量的 2 倍。

    • MSVC (Visual Studio)：扩容为当前容量的 1.5 倍。

    • Clang (libc++)：类似 1.5 倍。

    • 输出

    • Size:1, Capacity:1
Size:2, Capacity:2
Size:3, Capacity:4
Size:4, Capacity:4
Size:5, Capacity:8
...（每次不足时容量翻倍）

      扩容的底层逻辑

    • CONSTEXPR20 size_type _Calculate_growth(const size_type _Newsize) const {const size_type _Oldcapacity = capacity();  // 获取当前容量const auto _Max = max_size();               // 获取容器允许的最大容量// 检查几何增长是否会导致溢出if (_Oldcapacity > _Max - _Oldcapacity / 2) {return _Max; // 若溢出，直接返回最大允许容量}// 计算几何增长后的容量（1.5倍）const size_type _Geometric = _Oldcapacity + _Oldcapacity / 2;// 检查几何增长是否足够容纳新元素if (_Geometric < _Newsize) {return _Newsize; // 若1.5倍仍不足，直接返回所需大小}return _Geometric; // 否则返回1.5倍扩容后的容量
}

       vector 随机访问

    • #include <iostream>
#include <vector>
#include <stdexcept> // 用于捕获 out_of_range 异常using namespace std;// 打印 vector 内容的函数
void printVector(const vector<int>& vec) {cout << "Vector elements: ";for (auto iter = vec.begin(); iter != vec.end(); ++iter) {cout << *iter << " ";}cout << endl;
}int main() {vector<int> v = {9, 8, 7, 6, 5};// 打印初始 vectorprintVector(v);  // 输出: Vector elements: 9 8 7 6 5// 使用下标访问cout << "v[2]: " << v[2] << endl;      // 输出: 7// 使用 at() 访问cout << "v.at(2): " << v.at(2) << endl; // 输出: 7// 越界访问示例（注释掉的危险操作）// cout << v[12] << endl;     // 未定义行为（可能崩溃或输出垃圾值）try {// cout << v.at(12) << endl; // 会抛出 out_of_range 异常} catch (const out_of_range& e) {cerr << "异常捕获: " << e.what() << endl; // 输出: vector::_M_range_check: __n (which is 12) >= this->size() (which is 5)}// 访问首尾元素cout << "front: " << v.front() << endl; // 输出: 9cout << "back: " << v.back() << endl;   // 输出: 5return 0;
}

      vector 内存置换

    • 内存的缩容 删除 其实都是使用swap()函数实现的
    • #include <iostream>
#include <vector>
#include <stdexcept>using namespace std;// 打印vector元素的工具函数
void printVector(const vector<int>& vec) {cout << "[";for (auto iter = vec.begin(); iter != vec.end(); ++iter) {cout << *iter;if (iter != vec.end() - 1) cout << ", ";}cout << "]" << endl;
}int main() {// 1. 内存交换演示cout << "\n===== 内存交换 =====" << endl;vector<int> v1 = {1,2,3,4,5};vector<int> v2 = {9,8,7,6,5};cout << "交换前:" << endl;cout << "v1: "; printVector(v1);  // [1,2,3,4,5]cout << "v2: "; printVector(v2);  // [9,8,7,6,5]v1.swap(v2);cout << "\n交换后:" << endl;cout << "v1: "; printVector(v1);  // [9,8,7,6,5]cout << "v2: "; printVector(v2);  // [1,2,3,4,5]// 2. 缩容演示cout << "\n===== 缩容操作 =====" << endl;v1.resize(1000000);         // 扩容到100万元素v1.resize(5);               // 缩小到5元素cout << "直接resize后的容量: " << v1.capacity() << endl;  // 输出约1000000// 使用swap技巧缩容vector<int>(v1).swap(v1);   // 关键缩容操作cout << "swap缩容后的容量: " << v1.capacity() << endl;    // 输出5vector<int> x(v1);          // 拷贝构造cout << "拷贝构造的容量: " << x.capacity() << endl;       // 输出5// 3. 内存清理演示cout << "\n===== 内存清理 =====" << endl;v2.resize(1000000);         // 扩容到100万元素v2.clear();                 // 清空元素cout << "clear后的容量: " << v2.capacity() << endl;       // 输出约1000000vector<int>({}).swap(v2);   // 强制释放内存cout << "强制清理后的容量: " << v2.capacity() << endl;    // 输出0return 0;
}

       vector 空间预留

    • #include <iostream>
#include <vector>
using namespace std;int main() {vector<int> v;v.reserve(100);          // 预分配容量为100for (int i = 0; i < 100; ++i) {// 输出当前的 size 和 capacity（添加元素前）cout << "size = " << v.size() << ", " << "capacity = " << v.capacity() << endl;v.push_back(i);      // 添加元素，size 增加1}return 0;
}

      高速删除(在不关心元素的顺序情况下)

    • #include <iostream>
#include <vector>
using namespace std;void rpmove1(vector<int>& v, int index) {v.erase(v.begin() + index);
}void rpmove2(vector<int>& v, int index) {swap(v[index], v.back());v.pop_back();
}void printVector(const vector<int>& v) {for (int i = 0; i < v.size(); ++i) {cout << v[i] << " ";}cout << endl;
}int main() {vector<int> v;// 测试 rpmove1 的性能cout << "remove1 : ";for (int i = 0; i < 150006; ++i) {v.push_back(i);}for (int i = 0; i < 150000; ++i) {rpmove1(v, 4);  // 持续删除索引4位置的元素}cout << "结束" << endl;v.clear();  // 清空vector// 测试 rpmove2 的性能cout << "remove2 : ";for (int i = 0; i < 150006; ++i) {v.push_back(i);}for (int i = 0; i < 150000; ++i) {rpmove2(v, 4);  // 持续删除索引4位置的元素}cout << "结束" << endl;return 0;
}

      vector 数据排序(sort函数的底层逻辑)

    • #include <iostream>
#include <vector>
#include <algorithm>  // 需要包含algorithm头文件用于sort函数
using namespace std;// 打印vector内容的函数
void printVector(const vector<int>& v) {for (int i = 0; i < v.size(); ++i) {cout << v[i] << " ";}cout << endl;
}// 修正后的比较函数（降序排序）
bool cmp(int a, int b) {return a > b;  // 原代码的"< >"是错误写法，改为">"实现降序排列
}int main() {vector<int> v = { 9,8,7,1,2,3,4 };sort(v.begin(), v.end(), cmp);printVector(v);  // 输出：9 8 7 4 3 2 1return 0;  // return语句应该位于main函数内部
}

      快速排序 

    • 快速排序核心思想

      快速排序通过 分治法 将数组拆分为更小的子数组，逐步排序。核心步骤是选择一个 基准值（pivot），将数组分为两部分：

    • 左半部分：所有元素 ≤ 基准值。

    • 右半部分：所有元素 > 基准值。

    • 递归地对左右部分排序，最终合并为有序数组。

    • #include <iostream>
using namespace std;// 分区函数：返回基准值的最终位置
int partition(int arr[], int low, int high) {int pivot = arr[high];   // 选择最后一个元素为基准（实际应优化）int i = low - 1;         // i 是“小元素区”的右边界for (int j = low; j < high; j++) {if (arr[j] <= pivot) {  // 如果当前元素比基准小i++;                // 扩大“小元素区”swap(arr[i], arr[j]); // 把这个小元素扔到“小元素区”}}swap(arr[i + 1], arr[high]);  // 把基准放到正确位置return i + 1;                 // 返回基准的位置
}void quickSort(int arr[], int low, int high) {if (low < high) {int pi = partition(arr, low, high); // pi是基准的位置quickSort(arr, low, pi - 1);       // 排序左半部分quickSort(arr, pi + 1, high);      // 排序右半部分}
}int main() {int arr[] = {5, 3, 8, 4, 2};int n = sizeof(arr) / sizeof(arr[0]);quickSort(arr, 0, n - 1);// 输出结果：2 3 4 5 8for (int i = 0; i < n; i++) {cout << arr[i] << " ";}return 0;
}

      插入排序 (Insertion Sort)

    • 1. 实现原理

      插入排序的核心思想是将数组分为 已排序 和 未排序 两部分，每次从未排序部分取出第一个元素，将其插入到已排序部分的正确位置。
      具体步骤：

    • 初始时，已排序部分仅包含第一个元素。

    • 遍历未排序部分的每个元素，将其与已排序部分的元素从后往前逐个比较。

    • 若当前元素小于已排序元素，则将该元素后移一位，直到找到合适的位置插入。

    • void insertionSort(int arr[], int n) {for (int i = 1; i < n; ++i) {int key = arr[i];int j = i - 1;// 将 key 插入到已排序部分的正确位置while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j--;}arr[j + 1] = key;}
}

      课后习题

#include <vector>
using namespace std;class Solution {
public:vector<int> getConcatenation(vector<int>& nums) {int n = nums.size();vector<int> ans(nums);  // 初始化ans为nums的副本（前n个元素已正确）ans.resize(2 * n);      // 调整大小为2n，后n个元素初始化为0for (int i = 0; i < n; ++i) {ans[i + n] = nums[i]; // 覆盖后n个元素为nums的值}return ans;}
};

 

http://www.lryc.cn/news/2380519.html

相关文章：

  • BI是什么意思？一文讲清BI的概念与应用！
  • [ 计算机网络 ] 深入理解TCP/IP协议
  • 微软开放代理网络愿景
  • UDP三种通信方式
  • 4-5月份，思科，华为，微软，个别考试战报分享
  • 计算机网络-HTTP与HTTPS
  • 信号波形发生器电路Multisim仿真
  • 深入解析Java微服务架构：Spring Boot与Spring Cloud的整合实践
  • 医学影像辅助诊断系统开发教程-基于tensorflow实现
  • 前端单点登录
  • Spring AI 介绍
  • onlyoffice 源码 调试说明 -ARM和x86双模式安装支持
  • EXCEL在一列数据前统一添加负号
  • 从零开始打造个人主页：HTML/CSS/JS实战教程
  • UEFI Spec 学习笔记---33 - Human Interface Infrastructure Overview---33.2.6 Strings
  • 高等数学基础(牛顿/莱布尼茨公式)
  • Node.js路径处理指南：如何安全获取当前脚本目录路径
  • RK3588 ArmNN CPU/GPU ResNet50 FP32/FP16/INT8 推理测试
  • 2025年渗透测试面试题总结-华顺信安[实习]安全服务工程师（题目+回答）
  • 按键精灵ios/安卓辅助工具高级函数OcrEx文字识别（增强版）脚本开发介绍
  • Unity3D HUD UI性能优化方案
  • 掌握Git：版本控制与高效协作指南
  • VsCode和AI的前端使用体验：分别使用了Copilot、通义灵码、iflyCode和Trae
  • 交叉熵损失函数，KL散度， Focal loss
  • php、laravel框架下如何将一个png图片转化为jpg格式
  • 足式机器人经典控制常用的ROS库介绍
  • 在tp6模版中加减法
  • 【Part 3 Unity VR眼镜端播放器开发与优化】第一节｜基于Unity的360°全景视频播放实现方案
  • Python打卡DAY30
  • IDEA连接github（上传项目）