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

C++ std::vector

news 2025/9/16 9:40:31

std::vector 是 C++ STL 中最常用的序列容器之一，它提供了动态数组的功能，结合了数组的高效访问和链表的动态扩展能力。

1、底层结构与核心原理

1.1 内存布局

  • 连续内存空间：vector 底层是一块连续的动态分配内存，这使得它支持 随机访问（通过下标 [] 或 at() 方法，时间复杂度 O(1)）。

  • 三个核心指针：

    • start：指向内存块的起始位置（第一个元素）。
    • finish：指向最后一个元素的下一个位置。
    • end_of_storage：指向内存块的结束位置。

    三者关系：[start, finish) 是已使用空间，[finish, end_of_storage) 是未使用的预留空间。

1.2 容量（capacity）与大小（size）

  • size：当前存储的元素数量（finish - start）。
  • capacity：总分配的内存可容纳的元素数量（end_of_storage - start）。
  • 当 size == capacity 时，继续插入元素会触发 扩容。

1.3 扩容机制

  • 触发条件：插入元素后 size 超过当前 capacity。
  • 扩容步骤：
    1. 分配一块更大的内存（通常是原容量的 1.5 倍或 2 倍，不同编译器实现不同，如 GCC 是 2 倍，VS 是 1.5 倍）。
    2. 将旧内存中的元素复制/移动到新内存。
    3. 释放旧内存。
    4. 更新 start、finish、end_of_storage 指针。
  • 注意：扩容后，原有的迭代器、指针、引用都会失效（因为指向的旧内存已释放）。

1.4 迭代器类型

  • 随机访问迭代器 (RandomAccessIterator)： 支持所有指针算术运算，如 iter + n, iter - n, iter[n], iter1 < iter2 等。功能最强大的迭代器。

1.5 主要优点

  • 高效的随机访问： 通过 [] 或 .at() 访问任何元素的时间复杂度是 O(1)。
  • 高效的尾部操作： 在尾部进行 push_back 和 pop_back 的平摊时间复杂度是 O(1)。
  • 缓存友好性： 由于内存连续，遍历时具有良好的空间局部性，CPU 缓存命中率高，遍历速度极快。

1.6 主要缺点

  • 低效的中间/头部插入删除： 在 vector 头部或中间插入/删除元素，需要移动后续的所有元素，时间复杂度是 O(n)。
  • 潜在的迭代器失效： 任何可能引起内存重新分配的操作（如 push_back 导致扩容）都会使所有指向该 vector 的迭代器、引用和指针失效。

2、常用操作与示例代码

2.1 包含头文件与创建 vector

#include <iostream>
#include <vector>int main() {// 1. 创建空 vectorstd::vector<int> vec1;// 2. 创建并初始化 (C++11)std::vector<int> vec2 = {1, 2, 3, 4, 5};// 3. 创建包含 n 个相同元素的 vectorstd::vector<int> vec3(5, 100); // {100, 100, 100, 100, 100}// 4. 通过迭代器范围创建int arr[] = {6, 7, 8};std::vector<int> vec4(arr, arr + 3); // {6, 7, 8}// 5. 拷贝构造std::vector<int> vec5(vec2); // vec5 是 vec2 的副本return 0;
}

2.2 添加元素

std::vector<int> vec;// 在尾部添加元素 (最常用！)
vec.push_back(1); // vec: {1}
vec.push_back(2); // vec: {1, 2}
vec.push_back(3); // vec: {1, 2, 3}// C++11: 在尾部就地构造元素，避免拷贝/移动，更高效
vec.emplace_back(4); // vec: {1, 2, 3, 4}// 在指定位置前插入元素 (谨慎使用！成本高)
auto it = vec.begin() + 2; // 指向第3个元素 (3)
vec.insert(it, 999);       // 在 3 之前插入 999 -> {1, 2, 999, 3, 4}// C++11: 在指定位置就地构造元素
vec.emplace(it, 888);      // -> {1, 2, 888, 999, 3, 4}// 插入多个元素或一个区间
vec.insert(vec.end(), 3, 100); // 在末尾插入3个100

2.3 访问元素

std::vector<int> vec = {10, 20, 30};// 1. 使用下标运算符 [] (最快，但不做边界检查)
std::cout << vec[0] << std::endl; // 输出 10
// vec[5] = 1; // 错误！未定义行为，可能导致程序崩溃// 2. 使用 .at() 成员函数 (做边界检查，更安全)
std::cout << vec.at(1) << std::endl; // 输出 20
// vec.at(5) = 1; // 抛出 std::out_of_range 异常，可以被捕获处理// 3. 访问首尾元素
std::cout << "First: " << vec.front() << std::endl; // 等同于 vec[0]
std::cout << "Last: " << vec.back() << std::endl;   // 等同于 vec[vec.size()-1]// 4. 获取底层数据的原始指针 (用于兼容C API)
int* data_ptr = vec.data();
std::cout << *(data_ptr + 2) << std::endl; // 输出 30

2.4 删除元素

std::vector<int> vec = {1, 2, 3, 4, 5, 6, 7, 8};// 删除尾部元素 (高效！)
vec.pop_back(); // vec: {1,2,3,4,5,6,7}// 删除指定位置的元素 (成本可能高)
auto it = vec.begin() + 3; // 指向第4个元素 (4)
it = vec.erase(it);        // 删除 4，it 现在指向 5 -> {1,2,3,5,6,7}// 删除一个区间 [first, last)
vec.erase(vec.begin() + 1, vec.begin() + 3); // 删除 [2,3) -> {1,5,6,7}// 清空整个 vector
vec.clear(); // size() 变为 0，但 capacity() 通常不变// 删除所有值为 5 的元素 (Erase-remove idiom)
vec = {1, 5, 2, 5, 3};
vec.erase(std::remove(vec.begin(), vec.end(), 5), vec.end()); // -> {1,2,3}

2.5 大小与容量管理

  • size(): 当前拥有的元素数量。
  • capacity(): 当前已分配的内存最多能容纳的元素数量 (size() <= capacity())。
  • reserve(n): 预分配至少能容纳 n 个元素的内存。这是优化性能的关键，可以避免多次不必要的扩容。
  • resize(n): 改变 size() 为 n。如果 n > size()，则添加新元素（默认初始化）；如果 n < size()，则丢弃多余元素。capacity() 可能不变也可能改变。
std::vector<int> vec;std::cout << "Size: " << vec.size() << ", Capacity: " << vec.capacity() << std::endl; // 0, 0vec.push_back(1);
std::cout << "Size: " << vec.size() << ", Capacity: " << vec.capacity() << std::endl; // 1, 1vec.push_back(2); // 需要扩容 -> capacity becomes 2 (假设增长因子为2)
vec.push_back(3); // 需要扩容 -> capacity becomes 4
std::cout << "Size: " << vec.size() << ", Capacity: " << vec.capacity() << std::endl; // 3, 4// 提前预留空间，避免多次扩容
std::vector<int> optimized_vec;
optimized_vec.reserve(1000); // 一次性分配足够空间
for (int i = 0; i < 1000; ++i) {optimized_vec.push_back(i); // 这1000次push_back都不会触发扩容！
}// 调整大小
vec.resize(2);  // vec: {1, 2}, size=2, capacity=4 (未变)
vec.resize(5);  // vec: {1, 2, 0, 0, 0}, size=5, capacity=?
vec.resize(6, 99); // vec: {1, 2, 0, 0, 0, 99}, size=6// 释放未使用的内存 (C++11)，通常用于节省空间
// "shrink_to_fit" 请求将 capacity() 减少至 size()，但实现不一定保证
vec.shrink_to_fit();
std::cout << "Size: " << vec.size() << ", Capacity: " << vec.capacity() << std::endl; // 6, 6 (可能)

2.6 循环

2.6.1 使用范围-based for 循环 (C++11+)
#include <iostream>
#include <vector>int main() {std::vector<int> numbers = {1, 2, 3, 4, 5};// 只读访问for (int num : numbers) {std::cout << num << " ";}// 输出: 1 2 3 4 5// 修改元素for (int& num : numbers) {num *= 2; // 每个元素乘以2}// 再次输出for (int num : numbers) {std::cout << num << " ";}// 输出: 2 4 6 8 10return 0;
}
2.6.2 使用传统 for 循环
#include <iostream>
#include <vector>int main() {std::vector<std::string> fruits = {"Apple", "Banana", "Cherry"};for (size_t i = 0; i < fruits.size(); ++i) {std::cout << i << ": " << fruits[i] << "\n";}// 输出:// 0: Apple// 1: Banana// 2: Cherryreturn 0;
}
2.6.3 使用迭代器

常规迭代器

#include <iostream>
#include <vector>
#include <algorithm>int main() {std::vector<int> primes = {2, 3, 5, 7, 11};// 使用迭代器遍历for (auto it = primes.begin(); it != primes.end(); ++it) {std::cout << *it << " ";}// 输出: 2 3 5 7 11// 反向迭代器std::cout << "\nReverse: ";for (auto rit = primes.rbegin(); rit != primes.rend(); ++rit) {std::cout << *rit << " ";}// 输出: 11 7 5 3 2return 0;
}

常量迭代器

#include <iostream>
#include <vector>void printVector(const std::vector<int>& vec) {for (auto it = vec.cbegin(); it != vec.cend(); ++it) {std::cout << *it << " ";}
}int main() {std::vector<int> data = {10, 20, 30, 40};printVector(data);return 0;
}

2.7 使用 STL 算法

2.7.1 std::for_each
#include <iostream>
#include <vector>
#include <algorithm>int main() {std::vector<int> values = {1, 2, 3, 4, 5};// 使用lambda表达式std::for_each(values.begin(), values.end(), [](int n) {std::cout << n * n << " ";});// 输出: 1 4 9 16 25// 带索引的版本 (C++14+)int index = 0;std::for_each(values.begin(), values.end(), [&index](int n) {std::cout << "Value[" << index++ << "] = " << n << "\n";});return 0;
}
2.7.2 std::transform(修改元素)
#include <iostream>
#include <vector>
#include <algorithm>
#include <cctype>int main() {std::vector<std::string> words = {"hello", "world", "c++", "vector"};// 将每个字符串转为大写std::transform(words.begin(), words.end(), words.begin(),[](std::string s) {for (char& c : s) c = std::toupper(c);return s;});// 输出结果for (const auto& word : words) {std::cout << word << " ";}return 0;
}
2.7.3 使用 std::copy_if和 std::for_each
#include <iostream>
#include <vector>
#include <algorithm>int main() {std::vector<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};// 只处理偶数std::for_each(numbers.begin(), numbers.end(), [](int n) {if (n % 2 == 0) {std::cout << n << " is even\n";}});// 收集所有奇数std::vector<int> odds;std::copy_if(numbers.begin(), numbers.end(), std::back_inserter(odds),[](int n) { return n % 2 != 0; });std::cout << "Odd numbers: ";for (int n : odds) {std::cout << n << " ";}// 输出: Odd numbers: 1 3 5 7 9 return 0;
}

3、性能优化技巧

  1. 使用 reserve()： 如果能预知元素的大致数量，务必使用 reserve() 提前分配足够内存，这是提升 vector 性能最有效的手段。
  2. 优先使用 emplace_back()： 对于非平凡类型，emplace_back 直接在校位构造对象，避免了临时对象的创建和拷贝/移动操作，比 push_back 更高效。
  3. 理解迭代器失效规则： 在循环中插入/删除元素时，要特别小心迭代器失效的问题。erase() 会返回下一个有效的迭代器，应利用这一点。

4、常见问题

  1. vector的底层原理是什么？它是如何动态增长的？**
    vector的底层是一个在堆上分配的动态数组。它维护三个核心指针：start、end（指向最后一个元素的下一个位置）和 end_of_storage（指向分配内存的末尾）。当使用push_back或insert等操作导致当前容量(capacity)不足时（即 size() == capacity()），它会执行一次重新分配(Reallocation)：
    1. 分配一块新的、更大的内存块（通常是当前容量的 1.5 或 2 倍，这取决于编译器实现，如GCC常用2倍，VS常用1.5倍）。
    2. 将原有所有元素移动或拷贝到新内存中（C++11后，如果元素类型有移动构造函数，则会使用移动，更高效）。
    3. 释放旧的内存块。
    4. 更新内部的指针指向新内存。
    这个过程性能开销较大，因此如果事先知道元素数量，使用reserve()预分配空间可以避免多次重分配，显著提升性能。

  2. push_back 和 emplace_back 的区别？
    两者都是在尾部添加一个新元素。

  • push_back(const T& value)：接受一个已构造好的对象，将其拷贝（或移动）到容器中。
  • push_back(T&& value)：接受一个右值引用，将其移动到容器中。
  • emplace_back(Args&&... args)：接受一系列构造参数，直接在容器尾部的内存空间中原地构造对象，避免了任何临时对象的创建和拷贝/移动操作。因此，对于非平凡类型（non-trivial types），emplace_back 通常更高效。
    示例：
std::vector<std::pair<int, std::string>> v;
v.push_back({1, "one"}); // 需要先构造一个临时pair，然后移动（或拷贝）到vector中
v.emplace_back(2, "two"); // 直接在vector的内存中调用pair<int, string>的构造函数，参数是2和"two"

  1. size() 和 capacity() 的区别？
    size() 返回当前容器中实际拥有的元素个数。capacity() 返回当前容器在不重新分配内存的情况下，最多可以容纳的元素个数。capacity() >= size() 恒成立。

  2. reserve() 和 resize() 的区别？
    这是两个完全不同的操作：

  • reserve(n)：这是一个容量操作。它请求容器分配至少能容纳 n 个元素的内存空间。它只影响capacity()，不会改变size()，也不会创建任何元素。主要用于性能优化，避免多次重分配。
  • resize(n)：这是一个大小操作。它改变容器的size()为 n。如果 n > current_size，则会在尾部创建新的元素（值初始化）；如果 n < current_size，则会删除尾部的元素。它可能会导致capacity()的改变（如果需要的话）。
  1. 什么是迭代器失效？在 vector 中哪些操作会导致？
    迭代器失效指的是，在进行容器操作之后，之前获取的迭代器所指向的元素可能变得无效（解引用它会导致未定义行为）。
  • 会导致所有迭代器失效的操作：任何可能引起内存重新分配的操作，如 push_back/emplace_back (当 size==capacity时)、reserve、resize (当需要扩容时)、shrink_to_fit。
  • 会导致部分迭代器失效的操作：在中间进行insert或erase操作。这些操作会使被操作位置之后的所有元素的迭代器、引用和指针都失效，因为后面的元素都需要向前移动。
http://www.wxhsa.cn/company.asp?id=5364

相关文章：

  • RC-Explainer | Reinforced Causal Explainer for Graph Neural Networks
  • 批量遍历文件夹内得文件生成md5值
  • 使用源码启动 seata tc server
  • OpenLDAP 常见命令行命令及解析
  • 自动化http请求脚本
  • 绕过亚马逊儿童版家长控制的技术漏洞分析
  • P2564 [SCOI2009] 生日礼物
  • 【C++】类与对象（下） - 详解
  • 今日计划-2025年9月16日
  • C#/.NET/.NET Core技术前沿周刊 | 第 54 期（2025年9.8-9.14）
  • C# Avalonia 13- MoreDrawing - GenerateBitmap
  • Flutter个性化主题系统：Material Design 3的深度定制
  • Typescript中闭包的原理
  • IvorySQL 4.6：DocumentDB+FerretDB 实现 MongoDB 兼容部署指南
  • 在Xilinx Vitis中创建并使用静态库
  • Go使用cyclicbarrier示例
  • 做题记录2
  • 剑指offer-30、连续⼦数组的最⼤和
  • ITK-SNAP 安装
  • Morpheus 审计报告分享3：StETH 的精度丢失转账机制
  • 小区物业的智慧：轻松图解JVM垃圾回收的奥秘
  • SPI 总线概述及嵌入式 Linux 从属 SPI 设备驱动程序开发（第二部分，实践） - 教程
  • 详细介绍：idea2025创建第一个项目
  • CUDA多版本安装切换（转链接自用）
  • 社交交友源码：功能剖析、盈利探索与绿色运营策略
  • 权变与权力异化，是斗争的根源，超越自我，良性循环
  • 元推理AGI，是人类文明的结晶，超越爱因斯坦相对论，是文明进步的必然
  • PLC结构化文本设计模式——原型模式（Prototype Pattern）
  • 【一步步开发AI运动APP】十二、自定义扩展新运动项目1
  • 【Linux】人事档案——用户及组管理 - 详解