FizzyOrange@programming.dev
on 25 Oct 2024 14:31
collapse
Zero surprises. It’s the same as in any other language.
CodeMonkey@programming.dev
on 25 Oct 2024 16:57
nextcollapse
I was a bit surprised that deque is implemented as a linked list and not, for example, a ring buffer. It would mean that index reads would be constant time (though insert and delete at an index would be linear time), the opposite of using a linked list.
eager_eagle@lemmy.world
on 26 Oct 2024 11:34
collapse
But a ring buffer is a FIFO data structure that can be implemented using linked lists. What ring buffer implementation did you have in mind?
FizzyOrange@programming.dev
on 26 Oct 2024 14:17
nextcollapse
Standard ring buffers or circular buffers are implemented as continuous vectors, with a read and write pointer.
eager_eagle@lemmy.world
on 26 Oct 2024 18:41
collapse
Since VecDeque is a ring buffer, its elements are not necessarily contiguous in memory.
FizzyOrange@programming.dev
on 26 Oct 2024 23:54
collapse
No that’s a subtly different thing. The storage is a contiguous vector, but because it is a ring buffer there must be one pair of adjacent elements that are not contiguous in memory. That’s what that comment is saying.
But because it is only one discontinuity it doesn’t affect algorithmic complexity, so it is still O(1) to access elements, unlike a linked list which is O(N).
If you google “circular buffer” there will be loads of diagrams that make it really obvious how it works.
CodeMonkey@programming.dev
on 30 Oct 2024 13:04
collapse
I am used to seeing ring buffers implemented using an array. They are FIFO if you write to the maximum offset and read from the minimum offset but they are double ended if you have a method to read from the maximum offset and write to the minimum offset.
threaded - newest
Zero surprises. It’s the same as in any other language.
I was a bit surprised that
dequeis implemented as a linked list and not, for example, a ring buffer. It would mean that index reads would be constant time (though insert and delete at an index would be linear time), the opposite of using a linked list.But a ring buffer is a FIFO data structure that can be implemented using linked lists. What ring buffer implementation did you have in mind?
Standard ring buffers or circular buffers are implemented as continuous vectors, with a read and write pointer.
Rust’s
VecDequeis a ring buffer: doc.rust-lang.org/std/…/struct.VecDeque.htmlNo that’s a subtly different thing. The storage is a contiguous vector, but because it is a ring buffer there must be one pair of adjacent elements that are not contiguous in memory. That’s what that comment is saying.
But because it is only one discontinuity it doesn’t affect algorithmic complexity, so it is still O(1) to access elements, unlike a linked list which is O(N).
If you google “circular buffer” there will be loads of diagrams that make it really obvious how it works.
I am used to seeing ring buffers implemented using an array. They are FIFO if you write to the maximum offset and read from the minimum offset but they are double ended if you have a method to read from the maximum offset and write to the minimum offset.
And thank god for that. Theoretical computer science is still good ;)