Is `std::list::size()` Always O(1)?

Is list::size() Truly O(1)?

While it was once true that std::list::size() exhibited variable complexity across implementations, C 11 has standardized its behavior. Table 96 of the Container Requirements mandates constant complexity (O(1)) for .size() operations on all standard containers.

However, a notable exception remains gcc's libstdc implementation prior to version 5.0. Despite the C 11 standard requirement, its .size() function employs an O(N) algorithm, as seen in the following excerpt:

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

This decision stems from optimization considerations within libstdc . Maintaining a separate count of elements rather than traversing the list improves performance for some use cases, although it contradicts the standard complexity requirement.

Libc 's implementation, on the other hand, correctly adheres to the O(1) complexity, as illustrated by the following code snippet:

_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& __sz() const _NOEXCEPT
    {return __size_alloc_.first();}</size_type>

In conclusion, while the C 11 standard mandates O(1) complexity for std::list::size(), gcc's libstdc implementation prior to version 5.0 remains an anomaly, employing an O(N) algorithm instead.

The above is the detailed content of Is `std::list::size()` Always O(1)?. For more information, please follow other related articles on the PHP Chinese website!