c++ - C++ STL 容器的空间复杂度

Question

我找到了各种资源，这些资源列出了各种 C++ STL 容器的时间复杂度。在哪里可以找到使用 C++ STL 容器所涉及的空间复杂性？

我确实知道，对于大多数容器而言，该关系与包含的元素数量成线性关系。但是使用哈希函数的容器呢？在这种情况下是否可以做出任何保证？

Answer 1

每个 STL 容器都有两个复杂性界限来源。第一个是标准要求。一个很好的(而且几乎总是正确的)来源是 cppreference.com，例如http://en.cppreference.com/w/cpp/container如果您本身没有标准。其次，标准中未指定的内容由实现定义。考虑到它们的多用途特性，这些实现大多非常高效。

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

快速查看标准(23.2.1 一般容器要求)说:

All of the complexity requirements in this Clause are stated solely in terms of the number of operations on the contained objects.

第 23.2.5 节(无序关联容器)指出:

The worst- case complexity for most operations is linear, but the average case is much faster.

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

Constructs an empty unordered_map using the specified hash function, key equality func- tion, and allocator, and using at least n buckets. If n is not provided, the number of buckets is implementation-defined. Then inserts elements from the range [f, l). max_load_factor() returns 1.0. Complexity: Average case linear, worst case quadratic

二次时间发生在病态的坏散列函数上。平均情况是您应该期望的，即线性时间意味着线性空间。最坏的情况发生在 HashMap 溢出并需要重建时(是的，handwaivlyly 说)。

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

Complexity: Average case O(1), worst case O(size()).

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

希望能澄清一些事情。