vector何时何地分配N*K额外空间？有无标准或实现参考指南？

C++标准没有强制规定具体的增长因子数值，但明确了两个核心约束：一是vector的**容量(capacity)**必须不小于当前元素数量(size)；二是push_back、emplace_back这类尾部插入操作的分摊时间复杂度必须为O(1)——这直接要求增长因子必须大于1（固定增量会导致分摊O(n)时间），所以1.5倍、2倍这类常见策略都符合标准要求。

下面是需要执行额外存储空间分配的构造函数和成员方法：

一、构造函数中的预分配 #

• 固定大小构造函数：比如vector(size_type n, const T& val)，标准允许仅分配刚好容纳n个元素的空间，但多数实现会额外按增长因子预分配一部分空间，避免后续少量插入就触发扩容。当然，也可以选择严格分配n的空间，这取决于你对内存占用和扩容频率的平衡策略。
• 范围构造函数：vector(InputIt first, InputIt last)，如果输入迭代器是随机访问类型（比如数组指针），可以直接计算出元素总数，此时通常会一次性分配元素总数 + 额外预留空间（按增长因子），避免逐个插入时多次触发扩容。

二、触发扩容的成员方法 #

当当前容量不足以容纳操作后的元素数量时，这些方法会触发重新分配：

• push_back()/emplace_back()：当size() == capacity()时触发扩容，新容量按增长因子计算（比如1.5倍原容量）。
• insert()/emplace()：如果插入后元素总数超过当前容量，就会扩容。如果是批量插入（比如insert(pos, n, val)），新容量通常取max(size() + n, capacity() * 增长因子)，平衡内存占用和重分配次数。
• resize()：如果新指定的size大于当前capacity，需要扩容到至少新size的空间，部分实现会在此基础上额外预留。
• reserve()：这是唯一由用户主动触发扩容的方法，当传入的参数大于当前capacity时，会分配足够的空间；如果参数小于等于当前capacity，则无操作。

三、核心标准规则 #

• 每次扩容后，原有的迭代器、指针、引用都会失效，因为内存地址发生了变化。
• 扩容操作必须保证分摊时间复杂度符合要求，这是选择增长因子大于1的根本原因。

内容的提问来源于stack exchange，提问作者interesting