5 ms·
Writing into a vector is O(n), writing into a LL is O(1), assuming you have an iterator to the location to write to. If you don't, then it becomes O(n), and wr
by jki275 8y ago
Writing into a vector is O(n), writing into a LL is O(1), assuming you have an iterator to the location to write to. If you don't, then it becomes O(n), and writing into a vector can be O(1) if you're writing to the end.
C++ stl, LL appending is always O(1) and writing into a vector is O(n). There are plenty of caveats to this and the documentation should be referenced.
He's right btw that insert into a vector is generally faster in the C++ stl than insert into a LL. I don't recall off the top of my head why that is, just remember it's the case.
- manfredo 8y agoData locality is a big reason. Sure, it's O(N) writes, but those writes are neatly lined up in such a way that the likelihood of a cache miss is low. As opposed to a linked list, where just traversing to the middle may entail multiple round trips to main memory.
- jki275 8y agoYeah -- O(1) and O(n) are definitely simplifications and never tell the whole story.
- tdsamardzhiev 8y agoIt's not strictly related to C++ and/or STL. This is how computers work nowadays.
- jki275 8y agoWell, my comments were specifically based on C++ and the STL. There are so many implementations that one has to define the discussion.