主页 / 问题 / 571110
Accepted
Malov Vladimir
Asked:2020-09-28 03:40:04 +0000 UTC2020-09-28 03:40:04 +0000 UTC

list::size() 函数的线性复杂度是多少？

  • 772

其实有两个问题。令我自己有些惊讶的是，我了解到获取列表中项目数的时间复杂度std::list::size()是线性的

C++98。复杂性：最高为线性。资源

目前尚不完全清楚是什么原因造成的。为什么每次都要数你的物品？

如果这在早期标准中是必要的，那么由于哪些妥协，才有可能在新标准中实现稳定性保证？

C++11。复杂性：常数。

c++

1 个回答

  1. Best Answer

    std::list::size()这是职能和.之间古老的“利益冲突”的结果std::list::splice()。

    如果一个 partialsplice()从一个std::list到另一个需要一个恒定的执行时间splice()（即简单地将范围的极端元素从一个列表挂钩到另一个列表），那么将不可能立即知道新的大小源容器和接收容器，因为 不知道有多少元素交织在一起。因此，时间常数的要求导致时间splice()线性的要求——两个size()容器中的元素将不得不重新计算。

    相反，如果您需要时间恒定性size()（即实际需要存储的大小），那么您将不得不同意一个较慢splice()的方法，在上述情况下，它将以线性时间计算新的容器大小。

    在 C++98 中，这个问题是悬而未决的。允许实现选择他们认为恒定时间更重要的地方 - atsize()或 at splice()。

    在 C++11 中，我们决定做出一个意志坚定的决定：我们制定一个存储大小，我们保证size()恒定时间，并且，就这样吧，我们在splice().

    这就是解释 C++98 和 C++11 之间区别的原因。

    P.S. GCC 中 C++ 标准库的实现最初是走快走splice()慢路的size()。在 C++11 坚持不同的选项后，GCC 纠正了它自己的实现std::list，但由于向std::list. 更改立即回滚，直到今天std::list，GCC 仍不符合 C++11 要求。std::list::size()有线性的。

    • 18

相关问题