THthreeducks·Mar 24, 2025
> I recently developed a new data structure
Congratulations, you have discovered the array deque!
https://en.wikipedia.org/wiki/Double-ended_queue#Implementat...
I'd like to point out a performance optimization. On resize, you create a new array with double the size and copy all the old elements to the middle of the new array with more space at the beginning AND at the end: https://github.com/attilatorda/Shift-To-Middle_Array/blob/05...
However, in practice, it is often the case that most operations append elements at either the front OR back, but rarely at both ends equally. For example, imagine a FIFO queue, where elements are popped from the front and pushed from the back. Therefore, it is more efficient to only reserve space at the back if the last operation was push_back or at the front if the last operation was push_front.
One could
Read the rest
also carry along statistical information about the number of push_back and push_front operations and balance the space allocated at the front and back accordingly.
In addition to ksherlock's points, there are also the following issues:
- Vector implementations usually use size_t instead of int. Your implementation will fail for arrays larger than 2147483647, while size_t usually goes up to 18446744073709551615.
- On memory allocation failure, you should throw std::bad_alloc instead of calling std::exit.
- The front() function is missing a return statement. Turn on compiler warnings: -Wall -Wextra. For testing, -g -fsanitize=address,undefined is also helpful.
- You are mixing delete[] with malloc'ed memory in shrink_to_fit.
- You should implement copy constructor, move constructor, copy asignment and move assignment functions. See rule of five: https://en.cppreference.com/w/cpp/language/rule_of_three#Rul...
- Switching features on or off is usually done with macros instead of comments.
- 2 is not the best growth factor because it makes it harder for the memory allocator to reuse memory. More modern implementations use smaller growth factors: https://en.wikipedia.org/wiki/Dynamic_array#Growth_factor
- A more reasonable initial capacity would be 0 instead of 16, as is common for all major std::vector implementations. An initial capacity of 16 wastes a lot of space when a large number of ShiftToMiddleArrays are allocated.
- The compiler will most-likely ignore your inline instructions and decide on its own whether inlining is done or not, so might as well remove them.
- Why are there two versions of the data structure? (ShiftToMiddleArray.cpp and ShiftToMiddleArray.h)
- Some functions are just wrappers for other functions (pop_front = remove_head, pop_back = remove_tail). Why?
LLMs can point out most of those issue, so you should use them to discover potential issues. Of course, make sure to double-check with more reliable sources once you know that a certain class of problems exists.