Home > Backend Development > C++ > Is `std::list::size()` Always O(1)?

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

Barbara Streisand
Release: 2024-11-24 04:30:10
Original
254 people have browsed it

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()); }
Copy after login

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&amp; __sz() const _NOEXCEPT
    {return __size_alloc_.first();}
Copy after login

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!

Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Latest Articles by Author
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template