一、vector 为什么需要 capacity？#

首先明确一个事实：C++ 标准规定，vector 中的元素必须连续存储。
也就是说：

1
vector<int> a = {10, 20, 30, 40};

可以理解成是这样子的：

假设第一个元素的地址是 0x1000，那么：

这就是连续内存。
因此，我们可以通过：

1
a[i]

非常高效地访问任意位置的元素。

二、那么 capacity 是怎么来的？#

假设我们创建：

1
vector<int> a;

一开始：

1
size = 0
2
capacity = 0

现在：

1
a.push_back(10);

vector 需要申请一块能够存储元素的连续内存。
为了避免每添加一个元素就重新申请内存，STL 通常会采用一种策略：一次申请比当前实际需求更多的空间。
例如，假设某个实现采用如下扩容策略（仅作演示）：

你应该已经发现规律了：

• size 表示实际元素数量。
• capacity 表示当前分配的存储空间可以容纳多少元素。
• 当 size 超过 capacity，就需要扩容。

三、扩容时究竟发生了什么？#

这是最有意思的地方。假设原来：

1
capacity = 4
2
size = 4

现在执行：

1
a.push_back(50);

原来的空间已经满了。
由于 vector 要求连续内存，它不能简单地在原内存后面随便找个地方放第五个元素。
因此，典型的扩容过程是：

1. 申请新的连续内存
   假设新空间可以容纳 8 个元素。
2. 迁移原来的元素
   把原来的 4 个元素复制或移动到新空间。
3. 释放旧空间
   原来的内存不再使用，释放给内存分配器。
4. 添加新元素
   将 50 放入新空间

这也解释了一个非常重要的现象：
vector 扩容时，原来元素的内存地址可能全部发生变化。因此，扩容之后，之前保存的指针、引用和迭代器可能失效。
例如：

1
vector<int> a = {1, 2, 3};
2

3
int* p = &a[0];
4

5
a.push_back(4);  // 如果发生扩容
6

7
// 此时 p 可能已经失效

不要再使用这个失效的指针。

四.为什么每次不扩容一个空间？#

1. 策略 A：每次只增加一个元素的空间，可能需要进行大量内存重新分配和元素迁移。
2. 策略 B：按一定比例增长：
   例如每次将容量扩大到原来的两倍。
   迁移次数就会大幅减少。
   这使得 push_back() 的时间复杂度具有一个很重要的性质：
   均摊 O(1)，意思是：

   虽然某一次 push_back() 可能因为扩容而需要 (O(n)) 的时间，但大量连续添加元素时，平均每次添加的时间复杂度是 (O(1))。

是不是很抽象呢？不严谨来说就是每次搬迁都会预留一下内存空间，导致下次不一定搬迁，平均下来就是O(N)
我们来不严谨的举一个例子：假设我们采用“两倍扩容”的策略，假设我们采用“两倍扩容”的策略，初始容量是 1：

注意：不是每次添加元素都扩容。 扩容之后会空出不少位置，可以连续添加好几个元素。

迭代器失效#

之前我们提过，

vector 扩容时，原来元素的内存地址可能全部发生变化。因此，扩容之后，之前保存的指针、引用和迭代器可能失效

需要注意以下操作可能会导致迭代器失效：

1
for (auto it = a.begin(); it != a.end(); it++) {
2
    if (*it % 2 == 0) {
3
        a.erase(it);
4
    }
5
}

想一想，这个代码有问题吗？看起来没问题，对吧？但实际上，这段代码有一个严重的问题。
关键在这里：

1
a.erase(it);

我们之前学过，erase() 会让被删除位置及其后面的迭代器失效。
假设当前：

1
a = {1, 2, 3, 4, 5}
2
       ↑
3
       it

执行：

1
a.erase(it);

删除 2 后：

1
a = {1, 3, 4, 5}

原来的 it 已经失效了！
但是 for 循环结束这一轮后，还会执行：

1
it++;

这相当于对一个已经失效的迭代器进行操作，属于未定义行为。
那我们怎么办呢？
还记得吗？erase() 会返回一个新的有效迭代器。
所以应该这样写：

1
for (auto it = a.begin(); it != a.end();) {
2
    if (*it % 2 == 0) {
3
        it = a.erase(it);
4
    } else {
5
        it++;
6
    }
7
}

end() 迭代器的行为#

初始化时 it = dlist.end()，但是end() 指向的是最后一个元素的“下一个位置”，它里面没有有效数据！ 如果我们在循环体里面解引用它，程序会直接崩溃（段错误）。
所以说关于上面的a.back();其实等效于*(--a.end())，而不是end()

it != dlist.begin() 的问题#

这里来举个例子，你就发现其实这里还是有毒点的。
假设我们的容器里面有 3 个元素：[10, 20, 30]。
在内存里，它们的排列是这样的：

1
数据：  [ 10 ]      [ 20 ]      [ 30 ]      无意义内存
2
位置：  begin()                 中间          end()

当 it 退到 20 时，判断 it != begin() 成立，打印 20，然后 —it。
此时 it 指向了第一个元素 10。 再次判断 it != begin()。因为此时 it 已经等于 begin() 了，条件为假，循环直接结束了！ 所以，第一个元素 10 永远没有被打印出来。
所以说我们的第一个元素好像被很悲哀的吃掉了（
那么逆序输出要怎么办才好呢，请看下一节：

逆序输出的最终解#

1
for(auto it = dlist.rbegin(); it != dlist.rend(); ++it) {
2
    cout << *it << endl;
3
}

1
if (!dlist.empty()) {
2
    // 从最后一个元素的前一个位置开始（也就是最后一个有效元素）
3
    auto it = dlist.end();
4
    do {
5
        --it; // 先往前退一步
6
        cout << *it << " ";
7
    } while (it != dlist.begin()); // 退到开头就停止
8
}

1. 不加 &：for (auto x : a)#

• 这里的 x 是容器里元素的拷贝。
• 每次循环，系统会把 a 里面的元素复制一份，放进 x 里。
• 如果你在循环里修改 x（比如 x = 100;），原容器 a 不会发生任何改变，因为 x 只是一个副本。

2. 加 &：for (auto& x : a)#

• 这里的 & 是引用的意思。x 是原容器中元素的别名。
• 它不会复制元素，而是直接“指”向原容器里的那个元素。
• 如果你在循环里修改 x（比如 x = 100;），原容器 a 里面的值会被真正修改。

3. 加 const &：for (const auto& x : a)#

• 引用（不拷贝）+ 常量（不能修改）。
• 如果你只是想遍历打印，不想修改原数据，或者容器的元素非常大（比如是结构体、长字符串），强烈推荐这样写。这样既避免了拷贝（省内存、速度快），又保证了数据安全。