我找到了各种资源,这些资源列出了各种 C++ STL 容器的时间复杂度。在哪里可以找到使用 C++ STL 容器所涉及的空间复杂性?
我确实知道,对于大多数容器而言,该关系与包含的元素数量成线性关系。但是使用哈希函数的容器呢?在这种情况下是否可以做出任何保证?
最佳答案
每个 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 是桶的数量。
希望能澄清一些事情。
关于c++ - C++ STL 容器的空间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/25670131/