所有实现中 std::list::size() 真的都是 O(1) 吗？

std::list::size()：真正的 O(n)？

尽管有些人声称 std： :list::size() 具有线性复杂度，其复杂度的真相取决于实现。 C 标准没有指定此函数的复杂性要求。

实现变体

• Microsoft Visual Studio VC : 在旧版本中（例如 VC6），size() 确实具有恒定的复杂性，因为它只是返回存储的其内部数据结构中的大小。
• GNU 编译器集合 (GCC)： 历史上（直到 GCC 4.1.0），size() 使用 O(n ) 通过迭代列表来计算数量的方法

GCC 中的当前状态

在 C 11 中，C 标准要求所有标准的 size() 操作容器，包括 std::list，必须具有恒定的复杂性 (O(1))。这是为了确保跨平台和实现的一致且高效的运行时行为。

Libstdc 中的实现

尽管有 C 11 规定，size() 的实现libstdc（GCC 使用的标准库）中的 在 GCC 4.8 版本中仍然保持 O(n) 。这样做是出于性能原因，并最大限度地减少在列表结构中维护额外大小字段的开销。

更新：GCC 5.0 中的 O(1) 实现

随着 GCC 5.0 的发布，size() 的实现std::list 最终经过优化，在 C 11 模式下实现了 O(1) 复杂度。这是通过引入一个跟踪列表中元素数量的内部大小字段来实现的，提供对大小信息的恒定时间访问。

结论

虽然std::list::size() 的复杂度在过去是一个争论的话题，当前的 C 标准要求所有标准的复杂度为 O(1)容器。 GCC 5.0 及更高版本中的实现遵循此要求，确保 size() 对于 std::list.

的高效且可预测的执行

以上是所有实现中 std::list::size() 真的都是 O(1) 吗？的详细内容。更多信息请关注PHP中文网其他相关文章！