你的中文表达看起来像是用翻译软件从别的语言翻译过来的。–某位网友

一、背景

  这是在最近的面试期间遇到的一个比较有趣的问题，我在当时用了这种方法进行了回答（文章做了一些拓展研究），完全的临场发挥。自认为没什么用，所以作为八股文系列推出，但是夹杂了一些符号化的东西，希望给大家带来不同的体验。

  这是一个大多数编程语言在解决实际问题的时候会遇到的一个问题（八股文的场景是一个极端场景，和实现有关），问题如下：

在 C++ 的 STL 中，vector 进行 push_back 的时候是如何工作的？（后面聊到了 push_back 时扩容的问题，这是这篇的主题）

  我不想谈这类八股文问题的“标准”答案，因为没有任何意思，我想先谈谈遇到这种没有见过的八股问题该如何打开思路（当然这不是重点）。凡是涉及到“策略”的八股文问题，考虑模型、复杂度在面试中就够了。

  以以上问题为例，这里的模型是关于 vector 的，涉及到的操作有“读”和“写”，建立在“某种”理想的环境下；复杂度包括实现这种“策略”的复杂度、“策略”的时间复杂度和空间复杂度（要综合考虑“读”和“写”）；在此基础上你能得到关于其它拓展问题的答案，不管是“策略”的缺点和优点，或者是如何改进“策略”（这个靠运气，可能会突然想出来，玄学）。

二、问题的泛化

  从通用问题的角度来考虑的话，这个问题其实是在描述一个动态内存增长策略的问题，我们可以这样描述这个问题：

在我们需要使用变长内存空间时，待写入内容大于目前剩余大小时，我们该如何控制内存的增长，保证最优的读写速度（缓存友好的一个好处）？

  这个问题的复杂之处在于它隐藏了很多子问题，而这些问题的解决方案取决于实际工程需要。

  举例来说，如果你知道未来的数据一定小于某个大小，且通常情况下，这个大小不那么大，那么一次性分配足够的大小无疑是最明智的选择，既可以保证安全，又可以保证性能。一个常见的例子就是，目前所有 Windows 操作系统的路径长度是不大于 260 个字节的（但也是变长的），在这种场景下，进行路径相关的操作，261 字节（考虑空字符结尾）是绝对足够的，261 在大多数场景下对性能的影响也微乎其微，“不增长”作为控制增长的手段是极为合理的。

  即使你不知道你未来数据的上限，在通用解决方案下，上面的特例也会对优化产生正面的作用。

  通常来说，在现代的大多数程序语言中，当前的表达式产生的效果应该只影响它直接和间接表达的内容，而不会预测的影响下一个尚未编写的表达式表达的内容。

  结合这个问题来说，第一次内存大小的分配总是发生在需要使用的 0 时刻或之前。那么 ，

• 0 时刻之前按照常用大小来预先分配某个最小大小（目前，大多数关于内存空间的申请在速度优化中，都采用了这个策略，例如 malloc 函数，大多数实现下，申请小的内存时，实际申请的大小至少是某个数值）

• 0 时刻之后按照实际使用进行分配

  在实际的实现中，前者是被普遍使用的。原因不仅仅是和硬件访问的相关优化有关；实际上，在大多数学科中（包括硬件本身的设计考虑中），预先为常见场景做优化甚至产生相关场景的专用模块是非常常见的（例如，GPU 的产生、标准件的产生、建筑和电气工程里的冗余设计）。因此，在研究这个问题的过程中，我们会假设在第一次分配时（即使还没有使用），初始的大小为 $T$，且根据实现 $T_0 >0,T>T_0$，其中 $T_0$ 是当前环境下最优的最小分配大小。

  我们研究的这个问题，综合来看的，和以下因素有关：

  定义：”单位大小“：指计量具体内存模型中，某个基准大小（不一定是最小的）。这里一般是 $1$ 字节（取决于实现的模型中的大小）

1. 0 时刻预先分配的大小 $T$，$T$ 的值表示和”单位空间“大小，这里的 ${T}\geqslant{0}$
2. $t$ 表示所有已分配可供使用的“单位大小”
3. $u$ 表示现已使用的“单位大小”
4. $n$ 表示第 $n$ 次增加容量
5. $f$ 表示“一种关系”，这种关系描述 $t,u,n$ 如何影响“扩容策略”

  离散函数 $t=f(t,u,n)$ ，描述了模型内相关数值的变化。左侧 $t$ 的含义与第二条相同，只不过右侧 $t$ 的值是 $f$ 影响施加前的值，左侧 $t$ 的值为 $f$ 作用施加后的值，有一个时间前后的关系。

  表达式 $T=f(T,0,0)$ ，作为初始条件，表示了 0 时刻（未被使用，未扩容）时的状态。

  这种符号表示缺失了很多的约束，没有对空间的“形态”的要求，实际上，在这个极少约束条件下找出最优解是不可能的.实际上，我们可以说，几乎所有的“内存形态”（具象的来说就是不同数据结构的“形态”）的尺寸变化都可以用 $t=f(t,u,n)$ 这种符号来表示。

  显然研究“连续内存空间的扩容”问题，我们的约束是很严格的，条件也会很理想化。例如，这种结构的“形态”的实现是在逻辑上连续的（比如说数组，一般这种逻辑结构都可以进行“随机访问”），“读”和“写”的规则也有严格的要求。

三、约束

  通用场景下的问题分析通常会使模型变得复杂，当我们引入过多的可变因素时，整个问题就会变得复杂起来，因此，我们需要几个限制条件。

  需要注意的是，这些条件是理想化的，具体的实施在不同层次上可能取决于硬件的实现、操作系统的实现、操作系统中关于内存分配和释放库的实现。虽然这种设定过于理想，但在实际实施中，有比较大的概率可能会遇到这些情况，但问题却往往出在少数概率的时候（计算机科学和工程实践中的“墨菲定律”）。

  约束一：关于内存延续性的约束，这个约束可谓是以下讨论的基础。我们假定前一次释放的内存即：$t_{n-1}$ 和本次需要扩容时的内存大小 $t_n$ 是连续的。

  约束二：我们假设内存的总大小和可被使用的大小是无限的。即，当 $n\to \infty$ 时， $t=f(t,u,n)$ 始终成立。

  以上约束保证了我们可以用很多种不同的策略来控制内存的分配情况，当然更复杂条件的模型也可以依照此方法建立，结合具体的工程实践定制不同的内存分配方案也并不是完全无法实施，前提是是不考虑时间和经济成本。以下的讨论均建立在以上约束之上。

四、特殊增长模式下的讨论

  我们可以显然的意识到，以固定长度进行增长显然不是一个好的策略，我们可以通过互联网搜索得到很多关于固定长度增长的讨论，对相关读写操作的时间和空间的讨论也可以轻易的搜索到；与此同时我们也可以看到许多关于指数性增长的讨论，一般来说大多数实现目前更倾向于指数性增长，即：$t_n = x{t_{n-1}}$ 的这种模式，每次扩容时，总会分配一个上次大小 $x$ 倍的空间，然后复制之前的内容至新的空间。

  在互联网上，有许多这样的讨论，无外乎是关于 $x$ 的取值，有经典的 $x=2$ 和 $x=1.5$ 这种取法。唯一的区别是，2 倍的增长是比较通用的实现，它几乎（注意）可以在所有情况下满足特定的时间和空间复杂度，但缺点却是没有考虑到对以释放内存的利用，容易造成较多的内存碎片（我们这里不考虑上述约束）。在约束成立的条件下，1.5 可以保证在三次重新释放之后的连续内存在第四次扩容时被利用，但是为什么呢，这是我们要讨论的问题（我在这里把这个问题反过来了，实际上，我是在不知道这个得情况下推导出一些数值的）。

  显然下界是 $x>1$ ，因为我们需要保证内存是正向增长的。因此，已知了下界，我们需要再求一个上界，一个内存重复利用的上界，我们假设当 $n\to \infty$ 时，前 $n-2$ 已释放内存之和（注意，$n-1$ 次分配的内存还未释放，因为是连续的，所以可以这样使用）刚好足够第 $n$ 次使用（即，之前释放内存永远无法被利用），那么，我们有式 4-1：

\[t_n = t_0 + t_1 + \cdots +t_{n-2}\]

  我们选用$t_n = x{t_{n-1}}$ ，其中 $t_0 = T$ ,因此式 4-2

\[T{x^n} = T + Tx +\cdots +T{x^{n-2}}\]

  化简得式 4-3

\[x^n = 1+x+\cdots +x^{n-2}\]

  即，以下两式式 4-4、4-5成立，

\[x^n = \sum_{i=0}^{n-2} x^i\] \[x^{n+1} = \sum_{i=0}^{n-1} x^i\]

  做减法得式 4-6

\[x^{n+1} - x^n = x^{n-1}-1\]

  两边同除以 $x^{n-1}$ 得式 4-7

\[x^2-x = 1 - \frac{1}{x^{n-1}}\]

  当 $n\to \infty$ 时，$\frac{1}{x^{n-1}}\to 0$

  得式 4-8

\[x^2-x-1=0\]

  解方程，忽略负数解，可得上界为 $\frac{\sqrt{5}+1}{2}$

  因此，$x$ 的取值范围为

\[1<x<\frac{\sqrt{5}+1}{2}\]

  当 $x \ge \frac{\sqrt{5}+1}{2}$ 时，之前释放内存永远无法被利用，$x=2$ 也包含在其中。

  当我们需要验证某个取值可以在多少次释放后被利用时，我们可以简单替换式 4-7 中的 $=$ 为 $\le$ （推导从替换式 4-1 的 $=$ 为 $\le$ 开始），即

\[x^2-x \le 1 - \frac{1}{x^{n-1}}\]

  变形得

\[n \ge 1-\log_{x}({1+x-x^2})\]

  当 $x=1.5$ 时，$ n \ge 1- \log_{1.5}0.25$，即，$ n \ge 1- \log_{1.5}0.25$，计算得 $ n \ge 4.419$

  我们可以说在第 $n$ 次扩容时，我们可以重复使用前 $n-1$ 次释放的空间，在 $x=1.5$ 的例子中，我们可以说在第 5 次扩容时，我们可以重复使用前 4 次被释放的内存。我们可以验证 当 $x=1.3$ 时， $ n \ge 2.884$，我们可以说在第 3 次扩容时，我们可以重复使用前 2 次被释放的内存。具体公开的数据可以参考 Facebook 实现得 folly 来验证。

五、漏掉的内容

  要写的内容太多了，漏了好多，想了解详情的，可以面基。