Where do I find the complexity of an operation?

Question

In this answer it is mentioned that for a string doing s.chars().count() to get the number of characters is an O(n) operation. For simple ASCII strings getting the number of bytes using s.len() works as well. When using a check to make sure that all those bytes are actually ASCII this is probably safe.

I want to know what the complexity of that operation is. It might still have to find the end of the string like in C and be O(n).

I tried to look it up and found the documentation of the std::string::String, which applies for appropriate s. However it doesn't state its complexity. Looking at the source it just does this self.vec.len(). So we go to look at the vector docs and find that this simply returns a stored length self.len meaning that this is indeed an O(1) operation.

That was a lot of work though. Now what about the case that s is a std::str? I tried to do the same but got stuck in this mess.

Is there a more easily accessible ressource for operation complexities in Rust?

Something like this list for Python would be great.

Answer 1

Other than the performance section on collections I don't think there currently is a common list like the Python one you referenced.

As for str, determining its length is an O(1) operation, because a string slice consists of a pointer and length:

// 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 and str offer the same complexity guarantees for all actions. In fact, most operations on String (including chars()) are actually operations on str that use the implicit conversion from String to str (that conversion is free since they share the same low-level representation).