Is std::list::size() Truly O(1) in All Implementations?

std::list::size(): Truly O(n)?

Despite some individuals claiming that std::list::size() possesses linear complexity, the truth regarding its complexity is implementation-dependent. The C standard doesn't specify complexity requirements for this function.

Implementation Variations

• Microsoft Visual Studio VC : In older versions (such as VC6), size() indeed had constant complexity because it simply returned the stored size in its internal data structure.
• GNU Compiler Collection (GCC): Historically (up to GCC 4.1.0), size() used an O(n) approach by iterating over the list to count the number of elements.

Current State in GCC

In C 11, the C standard mandates that the size() operation for all standard containers, including std::list, must have constant complexity (O(1)). This is to ensure consistent and efficient runtime behavior across platforms and implementations.

Implementation in Libstdc

Despite the C 11 mandate, the implementation of size() in libstdc (the standard library used by GCC) remained O(n) in GCC versions up to 4.8. This was done for performance reasons and to minimize the overhead of maintaining an additional size field in the list structure.

Update: O(1) Implementation in GCC 5.0

With the release of GCC 5.0, the implementation of size() for std::list was finally optimized to achieve O(1) complexity in C 11 mode. This was achieved by introducing an internal size field that tracks the number of elements in the list, providing constant-time access to the size information.

Conclusion

While the complexity of std::list::size() was a topic of debate in the past, the current C standard requires O(1) complexity for all standard containers. The implementation in GCC 5.0 and later versions adheres to this requirement, ensuring efficient and predictable execution of size() for std::list.

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