`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中文网其他相关文章！