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中文網其他相關文章！