gpt4 book ai didi

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

转载 作者:IT老高 更新时间:2023-10-28 23:20:16 26 4
gpt4 key购买 nike

根据 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似乎具有特定的复杂性)。

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

最佳答案

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),但他们不会要求这样做,因为在标准中没有这样的约束(也不是它建议)指定。

关于c++ - vector::clear 的复杂性是否未指定?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14970747/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com