c++ - vector::clear 的复杂性是否未指定？

Question

根据 Is `std::vector<primitive>::clear()` a constant time operation? 的讨论，注意到C++标准似乎没有指定vector::clear的运行时间。

它指定 list::clear(线性；§23.3.5.4.5)、.clear 的运行时间，用于有序(表 102)和无序关联容器(表 103)(均为线性)。但是，似乎缺少 vector::clear (尽管其他 vector 成员，例如 .data 和 .swap似乎具有特定的复杂性)。

真的没有具体说明，还是我遗漏了什么？

Answer 1

Is it really unspecified, or did I miss something?

是的。目前，它确实未指定。

There is an open library issue for this ，其文本包含指向 StackOverflow 上相关问答的链接。 Jonathan Wakely 对该问题的回答阐明了发生了什么。

根据链接提案，clear() 的复杂度要求应该对所有序列容器linear。但是，必须记住，复杂性要求只是上限。根据 C++11 标准的第 17.5.1.4/7 段:

Complexity requirements specified in the library clauses are upper bounds, and implementations that provide better complexity guarantees satisfy the requirements.

这允许进行可能的优化，但不强制它们。

即使链接的提案被接受，我们也不能假设 clear() 对于非类元素的序列容器具有 O(1) 复杂度，尽管这似乎是一种自然而常见的优化策略(dasblinkenlight 对 this question on SO 的回答证实了这一点)。

实现将被允许采用此策略(根据 17.5.1.4/7)，但他们不会要求这样做，因为在标准中没有这样的约束(也不是它建议)指定。