STL 复杂度规范

STL 容器、算法和概念规范包括渐近复杂度规范。例如，迭代器必须采用恒定时间，即由迭代器操作所需的时间不得大于一个固定常量（此常量与迭代器所引用的容器的大小无关）。

显然，如果程序组件忽略复杂度规范，程序仍然会按功能运行。尽管如此，这些规范是 STL 组件与使用它们代码之间的界面的一项重要部分。如果这些规范被忽略，则生成程序的性能通常会使其变得无用。

以 STL 为例vector容器。忽略复杂度规范，实现vector与list相同的底层数据结构，即作为双向链表。但是对于长度为 10,000 的vector，这可能会导致平均计算v[i]的速度大约降低 5,000 倍。对于需要很多vector访问的程序（如典型的计算），这可能会将数分钟的执行时间变成数天。

这并不排除将 STL 算法与不符合标准复杂度规范的容器或迭代器结合起来使用。这偶尔会很有效，特别是如果代码对性能要求不高，或者容器的其他要求使性能规范无法实现。但这有两个潜在问题。首先，该算法可能不再是解决问题时的正确算法，甚至不再是一种合理的方式。另一种算法可能会更好满足容器操作的实际相对成本。其次，该算法当然不可能满足其指定复杂度规范。

STL 中的复杂度规范在必要时是一种过度简化。完整规范会确切地描述一个操作的运行时间与其调用的操作的运行时间如何变化。最终结果对于用户来说难以管理，因为他们必须持续跟踪大量无关的详细信息。对于实现者来说，这也会带来额外的限制，因为对现有算法的整体改进可能无法满足此类详细规范。

概念规范（例如 Forward Iterator 或 Container）指定概念的所有实例应满足的复杂度要求。这是针对操作（例如sort）所要求的最小行为（这些操作针对概念进行了参数化）。任何特定实例（例如vector）在至少某些情况下可能表现得更好。

很难明确指定算法何时满足性能约束。复制vector在 16 位嵌入式处理器上是否需要恒定时间？毕竟，vector限制为小于 65,536 的某个值。所以，复制操作涉及的内存操作数量肯定受一个常数限制。甚至可以想象，在具有分页虚拟内存的机器上，该处理器上的最糟糕情况vector的复制时间可能小于最糟糕的内存访问时间。不过，直观上将vector复制或list遍历描述为常数时间操作是不正确的。即使在该机器上，vector实现为列表不太可能产生满意的性能。（当然，在每次vector访问中循环一次秒的实现也是如此，尽管它显然在常数时间内运行。此处的重点是为了在实现者和用户之间传达正确的意图，而不是防范恶意或愚蠢的实现。）

从根本上说，准确定义渐进算法复杂性的概念对于真实的计算机硬件而言是困难的，而不是对于抽象的机器模型。所以我们确定以下准则

对于算法A 具有运行时间 O(f(n))，必定有一个相应的算法A'，它在指针和size_t类型任意长的机器上都是正确的，例如A 和A' 在实际硬件上执行基本相同的一系列操作。（在简单的情况下，A 和A' 将相同。在其他情况下，A 可能根据地址受限的知识得到简化。）对于足够大的输入尺寸n，A' 最多需要时间Cf(n)，其中C 是一个常数，既独立于n 又独立于地址大小。（假定指针、size_t和ptrdiff_t操作需要花费与大小无关的常数时间。）
所有容器或迭代器复杂性规范均指摊销复杂度。单独一个操作可能比指定的用时更长。但是，对同一容器或迭代器执行的任何足够长的操作序列最多用时不会超过指定的相应操作成本之和。
算法指定最差情况或平均情况性能，并标识出哪种情况。除非另有说明，否则平均值假定容器元素是从大于容器大小的具有可能值的有限类型中选择的，并且容器元素独立地均匀分布。
操作f 的复杂性规范假定f 调用的操作最多需要指定运行时间。但是，如果在期望情况下被调用的操作不比指定的慢对数因子，则算法通常仍然是适当的。
如果操作比当前 STL 中函数F 担心的更为耗时，则F 最多会按增加的成本比例降低速度。不满足此特性任何未来的操作将使该特性显式化。
若要精确说明这一点，假设指定 F 使用时间 f(m) 作为大小 m 的输入。F 使用操作 G_k，且在输入大小 n 上指定运行时间为 g_k(n)。如果在上下文中使用 F，其中每个 G_k 比预期速度慢最多为因子 h(n)，则 F 最多以因子 h(m) 慢下来。之所以如此，是因为当前算法从不将操作 G_k 应用于明显大于 m 的输入。