我在哪里找到操作的复杂性

Question

在此答案中，提到的是用于执行的字符串 s.chars().count()获得字符的数量是O（n）操作。对于简单的ASCII字符串，使用s.len()获取字节数。当使用检查以确保所有这些字节实际上都是ASCII时，这可能是安全的。

我想知道该操作的复杂性是什么。它可能仍然必须像C中的C中找到字符串的末端，并且是O（n）。

我试图查找它，并找到了std::string::String的文档， 适用于适当的s。但是，它没有说明其复杂性。查看源，它只是执行此self.vec.len()。因此，我们去查看矢量文档，发现这只是返回存储的长度self.len，这确实是O（1）操作。

这是很多工作。现在， s是std :: str呢？我试图做同样的事情，但陷入了混乱。

生锈的操作复杂性是否更容易访问？

类似的python列表很棒。

Answer 1

除了收藏的性能部分，我认为当前没有像您所引用的Python这样的常见列表。

对于str，确定其长度是O（1）操作，因为字符串切片由指针和长度组成：

// We can re-build a str out of ptr and len. This is all unsafe because
// we are responsible for making sure the two components are valid:
let s = unsafe {
    // First, we build a &[u8]...
    let slice = slice::from_raw_parts(ptr, len);
    // ... and then convert that slice into a string slice
    str::from_utf8(slice)
};

Answer 2

String和 str为所有操作提供相同的复杂性。实际上，String上的大多数操作（包括chars()）实际上是在str上操作，该操作使用了从String到str的隐式转换（该转换是免费的）。