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.5 倍或 2 倍，不同编译器实现不同，如 GCC 是 2 倍，VS 是 1.5 倍）。
- 将旧内存中的元素复制/移动到新内存。
- 释放旧内存。
- 更新
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、性能优化技巧
- 使用
reserve()： 如果能预知元素的大致数量，务必使用reserve()提前分配足够内存，这是提升vector性能最有效的手段。 - 优先使用
emplace_back()： 对于非平凡类型，emplace_back直接在校位构造对象，避免了临时对象的创建和拷贝/移动操作，比push_back更高效。 - 理解迭代器失效规则： 在循环中插入/删除元素时，要特别小心迭代器失效的问题。
erase()会返回下一个有效的迭代器，应利用这一点。
4、常见问题
-
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()预分配空间可以避免多次重分配，显著提升性能。 -
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"
-
size()和capacity()的区别？
size()返回当前容器中实际拥有的元素个数。capacity()返回当前容器在不重新分配内存的情况下，最多可以容纳的元素个数。capacity() >= size()恒成立。 -
reserve()和resize()的区别？
这是两个完全不同的操作：
reserve(n)：这是一个容量操作。它请求容器分配至少能容纳n个元素的内存空间。它只影响capacity()，不会改变size()，也不会创建任何元素。主要用于性能优化，避免多次重分配。resize(n)：这是一个大小操作。它改变容器的size()为n。如果n > current_size，则会在尾部创建新的元素（值初始化）；如果n < current_size，则会删除尾部的元素。它可能会导致capacity()的改变（如果需要的话）。
- 什么是迭代器失效？在
vector中哪些操作会导致？
迭代器失效指的是，在进行容器操作之后，之前获取的迭代器所指向的元素可能变得无效（解引用它会导致未定义行为）。
- 会导致所有迭代器失效的操作：任何可能引起内存重新分配的操作，如
push_back/emplace_back(当size==capacity时)、reserve、resize(当需要扩容时)、shrink_to_fit。 - 会导致部分迭代器失效的操作：在中间进行
insert或erase操作。这些操作会使被操作位置之后的所有元素的迭代器、引用和指针都失效，因为后面的元素都需要向前移动。
)
