Is std::list::size() Really O(1) in C ?

Is std::list::size() Really O(n)?

Concerns have been raised regarding the time complexity of std::list::size() in C . Some suggest it might be implementation-dependent, despite the standard not specifying its complexity.

Implementation-Specific Behavior

In earlier versions of C , the complexity of std::list::size() varied depending on the STL implementation used. Microsoft Visual Studio V6 implemented it with constant complexity, while GCC up to 4.1.0 used a distance-based approach, resulting in O(n) complexity.

Standardization and Complexity

In C 11, a change was introduced by n2923, requiring that all standard container .size() operations have constant time complexity (O(1)). This is now an explicit requirement, ensuring consistent performance across implementations.

GCC Implementation

However, despite the standardization, the implementation of std::list::size() in GCC up to version 4.8 continues to employ an O(n) algorithm. This is explained in detail in the blog entry linked in the original question.

Update in GCC 5.0

It's important to note that this issue is resolved in GCC 5.0 and later. In C 11 mode, std::list::size() is properly implemented with O(1) complexity in GCC 5.0 and above.

libc Implementation

In contrast to GCC's approach, libc 's implementation of std::list::size() has been consistently optimized for O(1) complexity since its inception.

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