rust
rust copied to clipboard
rust-lang
VecDeque missing time complexity docs
Location
std::collections::VecDeque - functions like front, back, etc. https://doc.rust-lang.org/std/collections/struct.VecDeque.html
Summary
I think there's missing time complexity (big O notation) for functions as front, back, front_mut, capacity, clear, pop_back, pop_front, push_back, push_front, etc.
We don't seem to document those for other collections either, only the methods that can be directly compared, so we probably should try to set an actual policy on these before we document them, considering that VecDeque has more implementation variance.
We don't seem to document those for other collections either, only the methods that can be directly compared, so we probably should try to set an actual policy on these before we document them, considering that VecDeque has more implementation variance.
are PRs for changes like this welcomed?
Err, changes like what exactly? For a proposed policy or for the comparable operations?
Oh. Yes, I think opening a PR documenting the time complexity guarantees for VecDeque for the operations that have time complexity docs on other types in std might be helpful, though it might also... start a discussion by T-libs-api on this topic!
Having time complexity for every operation of every std data structure would be amazing.
I claimed this.
The style of describing complexity isn't consistent across collections yet, hashset uses a # performance section, linked_list uses "This ... is O(n)" and VecDeque also has inconsistencies.
The existing VecDeque functions mix between the in description "This .. is O(1)" and using a # complexity section.
I prefer using the style of using the # complexity section, but is there an existing standard outside of std::collections?
I ran a ripgrep on rust/library/alloc with rg -e O\*?\(.*\) -C 5 to see what other documentation for complexity is already exists.