C 中的 std::list::size() 真的是 O(1) 吗？

std::list::size() 真的是 O(n) 吗？

人们对 std 的时间复杂度提出了担忧C 中的 ::list::size() 。有些人认为它可能依赖于实现，尽管标准没有指定其复杂性。

特定于实现的行为

在早期版本的 C 中， std 的复杂性： :list::size() 根据所使用的 STL 实现而变化。 Microsoft Visual Studio V6 以恒定的复杂度实现它，而 GCC 到 4.1.0 使用基于距离的方法，导致 O(n) 复杂度。

标准化和复杂性

在 C 11 中，n2923 引入了一项更改，要求所有标准容器 .size() 操作都具有恒定的时间复杂度 (O(1))。现在这是一个明确的要求，确保跨实现的性能一致。

GCC 实现

然而，尽管有标准化，std::list::size( 的实现）在 GCC 4.8 版本之前继续采用 O(n) 算法。这在原始问题链接的博客文章中有详细解释。

GCC 5.0 中的更新

值得注意的是，这个问题在 GCC 5.0 中已得到解决，并且之后。在 C 11 模式下，std::list::size() 在 GCC 5.0 及更高版本中正确实现，复杂度为 O(1)。

libc 实现

中与 GCC 的方法相比，libc 的 std::list::size() 实现自诞生以来一直针对 O(1) 复杂度进行了持续优化。

以上是C 中的 std::list::size() 真的是 O(1) 吗？的详细内容。更多信息请关注PHP中文网其他相关文章！