我找到了各种资源来争取各种C ++ STL容器的时间复杂性。在哪里可以找到使用C ++ STL容器所涉及的空间复杂性？
我知道，对于大多数容器而言，这种关系与所包含的元素数量呈线性关系。但是使用哈希函数的容器呢？在这种情况下可以做出任何保证吗？
每个STL容器都有两个复杂边界源。第一个是标准的要求。一个好的（几乎总是正确的）来源是cppreference.com，例如如果你没有自己的标准，http://en.cppreference.com/w/cpp/container。其次，标准中未指定的内容是实现定义的。鉴于它们的多用途性质，这些实现大多非常有效。
用简短的回答回答你的问题：是的，你可以期待线性空间。但细节有点复杂。
快速浏览标准（23.2.1一般容器要求）说：
本条款中的所有复杂性要求仅根据所包含对象的操作数量来说明。
第23.2.5节（无序关联容器）声明：
大多数操作的最坏情况复杂性是线性的，但平均情况要快得多。
该标准继续并更详细地定义了无序关联容器的某些方面。仔细观察操作的复杂性，我们可以推断出空间的某些东西。进一步挖掘（23.5.4.2 unordered_map构造函数）揭示：
使用指定的哈希函数，密钥相等函数和分配器构造一个空的unordered_map，并使用至少n个桶。如果未提供n，则桶的数量是实现定义的。然后插入范围[f，l）中的元素。 max_load_factor（）返回1.0。复杂性：平均情况线性，最坏情况二次
对于病态错误的哈希函数，发生二次时间。平均情况是您应该期望的，即线性时间意味着线性空间。最糟糕的情况发生在哈希映射溢出并需要重建时（是的，请小心地说）。
对于元素访问，我们得到类似的东西：
复杂性：平均情况O（1），最差情况O（size（））。
此外，该标准表示实现必须使用分块数据结构。元素被散列到桶中。这些存储桶也需要空间，并且根据初始化unordered_map的方式，存储桶的数量是实现定义的。因此，有效的实现将使用O（n + N）空间，其中n是元素的数量，N是桶的数量。
希望能澄清一点事情。
我一直在寻找关联容器set的空间复杂性的答案。希望这可以帮助。
以下内容部分回答了这个问题。
set在这篇文章space complexity of stl set?，由于set（一种红黑树）的数据结构，空间复杂性通常是O(n)
mapmap和set的数据结构都是红黑树，因此map的空间复杂度通常是O(n)，但它取决于现实世界的情况（参见：space complexity of a map）。