C++ STL容器的空间复杂性

Question

我找到了各种资源来争取各种C++ STL容器的时间复杂性.在哪里可以找到使用C++ STL容器所涉及的空间复杂性？

我知道,对于大多数容器而言,这种关系与所包含的元素数量呈线性关系.但是使用哈希函数的容器呢？在这种情况下可以做出任何保证吗？

Answer 1

每个 STL 容器都有两个复杂性界限来源。第一个是标准的要求。cppreference.com 是一个很好的（而且几乎总是正确的）来源，例如，如果您没有标准本身，则可以使用http://en.cppreference.com/w/cpp/container 。其次，标准中未指定的内容是实现定义的。鉴于其多用途性质，这些实现大多非常有效。

用简短的答案来回答你的问题：是的，你可以期待线性空间。但细节有点复杂。

快速浏览一下该标准（23.2.1 一般容器要求）说：

本条款中的所有复杂性要求仅根据所包含对象的操作数量来说明。

第 23.2.5 节（无序关联容器）指出：

大多数操作的最坏情况复杂度是线性的，但平均情况要快得多。

该标准继续并更详细地定义了无序关联容器的某些方面。当仔细观察操作的复杂性时，我们可以对空间进行一些推断。进一步挖掘（23.5.4.2 unordered_map 构造函数）揭示了：

使用指定的哈希函数、键相等函数和分配器并使用至少 n 个存储桶构造一个空的 unordered_map。如果未提供 n，则存储桶的数量是实现定义的。然后插入范围 [f, l) 中的元素。max_load_factor() 返回 1.0。复杂性：平均情况是线性的，最坏情况是二次的

对于病态的糟糕哈希函数，会出现二次时间。平均情况是您应该期望的，即线性时间意味着线性空间。最坏的情况发生在哈希图溢出并需要重建时（是的，手动地说）。

对于元素访问，我们得到类似的东西：

复杂度：平均情况 O(1)，最坏情况 O(size())。

此外，该标准还规定实现必须使用分桶数据结构。元素被散列到桶中。这些存储桶也需要空间，并且根据初始化 unordered_map 的方式，存储桶的数量是实现定义的。因此，高效的实现将使用 O(n+N) 空间，其中 n 是元素的数量，N 是桶的数量。

希望这能澄清一些事情。