`std::list::size()` 總是 O(1) 嗎？

list::size() 真的是 O(1) 嗎？

雖然 std::list::size 曾經是正確的() 在不同的實作中表現出不同的複雜性，C 11 已經標準化了它的行為。容器要求的表 96 要求所有標準容器上的 .size() 操作具有恆定的複雜度 (O(1))。

但是，一個值得注意的例外是 5.0 版本之前的 gcc 的 libstdc 實作。儘管符合 C 11 標準要求，但其 .size() 函數採用 O(N) 演算法，如以下摘錄所示：

size_type
size() const _GLIBCXX_NOEXCEPT
{ return std::distance(begin(), end()); }

此決定源自於 libstdc 內的最佳化考量。維護單獨的元素計數而不是遍歷列表可以提高某些用例的效能，儘管它與標準複雜性要求相矛盾。

另一方面，Libc 的實作正確地遵循O(1)複雜度，如以下程式碼片段所示：

_LIBCPP_INLINE_VISIBILITY
size_type size() const _NOEXCEPT     {return base::__sz();}

...

__compressed_pair<size_type, __node_allocator> __size_alloc_;

_LIBCPP_INLINE_VISIBILITY
const size_type&amp; __sz() const _NOEXCEPT
    {return __size_alloc_.first();}

總之，雖然C 11 標準要求O(1)複雜度std::list::size()，5.0 版本之前的gcc 的libstdc 實作仍然是異常，而是採用O(N) 演算法。

以上是`std::list::size()` 總是 O(1) 嗎？的詳細內容。更多資訊請關注PHP中文網其他相關文章！