c++ - C++ 标准规定的时间复杂度的操作可以动态分配内存吗？

Question

C++ 标准没有规定内存分配的时间复杂度，因为这超出了其范围(通常取决于操作系统的行为)，但这是否意味着具有指定复杂度的任何内容都无法动态分配内存？

例如，标准库中的大多数容器都需要具有恒定时间复杂度的默认构造函数，因此任何抢占式动态分配内存的实现都会违反标准。 (该特定行为是否可取并不是重点——这只是一个听起来有些合理的例子。)是这样吗？

Answer 1

该标准明确规定了其规定的“时间复杂度”中包含的内容:

23.2.1[container.requirements.general]/2

All of the complexity requirements in this Clause are stated solely in terms of the number of operations on the contained objects. [ Example: the copy constructor of type vector <vector<int> > has linear complexity, even though the complexity of copying each contained vector<int> is itself linear. — end example ]

对于该子句之外的函数，明确说明了复杂性要求，例如

25.4.3.1[lower.bound]/3 (即std::lower_bound)

Complexity: At most log2(last - first) + O(1) comparisons.

(请注意，仅计算比较:lower_bound 可以，并且对于前向迭代器，将执行线性扫描)

所以，是的，复杂性由标准规定的算法可以动态分配内存，或者做任何他们想做的事情，只要它们满足实际的约束。