11–20 of 121 posts
- this is going to have problems with non-trivial types. (Think about destructors or move constructors like std::unique_ptr). If you don't want to deal with them, at least add a static_assert(std::is_trivially_copyable::value == true);
- front() doesn't return a reference and it doesn't even return the front
- adding iterators (begin()/end()) will let it play nice with for( : ) loops and , etc.
https://www.boost.org/doc/libs/develop/doc/html/container/no...
Earlier quoted context omitted.
The elements are completely contiguous, which can be nice for passing off (subslices) to other APIs, maximum speed iteration, etc.
Does it have to move or resize when one of the sides reaches the end of the array? I presume that would be slower than a ring buffer that only grows when it's completely filled?
is it just me or benchmarks report link is dead and hence there's no way to see the comparison
That one and at least one other simply links to #, which means same page no anchor. And this is commonly done as a placeholder link before you have the link in place you intended to put there.
Whereas a dead link for me would be one that leads elsewhere and results in 404 (page moved, file not yet created, etc) or an expired or not yet registered domain.
But I get what you mean, and I agree OP should update those links to point somewhere :)
[0] - https://github.com/opensource-apple/CF/blob/master/CFArray.c [1] - https://ciechanow.ski/exposing-nsmutablearray/
Earlier quoted context omitted.
Does it have to move or resize when one of the sides reaches the end of the array? I presume that would be slower than a ring buffer that only grows when it's completely filled?
Both are O(1) datastructures, but indexing a ring buffer is slightly more costly compared to this and insertion is slightly more costly for this than a ring. Probably usually works out in favor of this design though for net performance usually?
I recently developed a new data structure called the Shift-To-Middle Array, designed as an alternative to std::deque, std::vector, and linked lists. My goal was to optimize insertion and deletion at both ends, while also improving cache locality and performance compared to traditional implementations. What is the Shift-To-Middle Array? Unlike std::deque, which uses a fragmented block-based structure, the Shift-To-Mid…
I always assumed deque implementations were ring buffers that double in size once full so that prepend/append operations are amortized O(1).
Interesting! This is the kind of thing I like. I'm having a hard time understanding the description. If I understand right, it's kind of like an inside-out gap buffer, or a hybrid of a gap buffer and a ring buffer? Is the free space in the array always contiguous? If not, is the non-free space? How is it different from ExpandingRingBuffer?
Once the head reaches the front of the allocation or the tail reaches the rear of the allocation, it triggers a resize. The resize creates a new allocation with double the size and copies the original elements to the middle of this new allocation.
Earlier quoted context omitted.
The elements are completely contiguous, which can be nice for passing off (subslices) to other APIs, maximum speed iteration, etc.
Does it have to move or resize when one of the sides reaches the end of the array? I presume that would be slower than a ring buffer that only grows when it's completely filled?
Yes, it resizes when that happens, to double the size.
Interesting! This is the kind of thing I like. I'm having a hard time understanding the description. If I understand right, it's kind of like an inside-out gap buffer, or a hybrid of a gap buffer and a ring buffer? Is the free space in the array always contiguous? If not, is the non-free space? How is it different from ExpandingRingBuffer?
It starts by adding the first element to the middle of the allocation and then the head and tail grow outwards as more elements are added at either end. Once the head reaches the front of the allocation or the tail reaches the rear of the allocation, it triggers a resize. The resize creates a new allocation with double the size and copies the original elements to the middle of this new allocation.
It still seems like that involves copying that a straightforward ring buffer avoids.