Rust中Vec::len()的时间复杂度是O(1)还是O(n)？

放心用吧！Rust 里 Vec::len() 的时间复杂度确实是 O(1)，完全不用担心频繁调用的性能问题。

为什么是 O(1)？ #

Rust 的 Vec 作为动态数组，内部结构里直接维护了三个核心字段：

• 指向底层数据缓冲区的指针
• 缓冲区的总容量（capacity）
• 当前已存储元素的数量（也就是 len() 返回的值）

调用 v.len() 时，它只是简单地读取并返回这个预存的长度字段，根本不需要遍历整个数组计数。这也是 push()、pop() 和索引访问 [] 能实现 O(1) 复杂度的基础——这些操作都依赖快速获取当前长度来定位元素、判断扩容时机。

关于文档的补充 #

你提到《The Book》没特意说明这点，其实是因为对于 Rust 的基础集合类型来说，len() 是常数时间属于默认的“行业常识”，类似 Java 的 ArrayList、Python 的 list 等动态数组实现，都会维护长度字段来保证 O(1) 的长度查询。

关于频繁调用的建议 #

你担心内部函数里频繁调用的性能问题？完全没必要额外存储返回值。这类简单的字段读取操作，Rust 编译器会做极致优化，甚至可能直接把长度值嵌入到后续逻辑中，几乎没有性能开销。

内容的提问来源于stack exchange，提问作者kevlarr