https://github.com/thanknoah/DynamicArray/tree/main basically my own smaller implementation of std::vector, growth factor of 1.5x, standard features like get(), insert(), reserve, remove, size etc etc
#Dynamic array project
cloud wave
runic spoke
how did you decide on the growth factor?
sizeOfEachElement seems redundant because you can always use sizeof(T)
cloud wave
how did you decide on the growth factor?
*2
cloud wave
Times it by 2
Ive measured peformance against std::vector in terms of insert time and it really varies depending on what algorithim i use for growth
Ive noticed that with types that are trivally copyable e.g int, char, etc it is faster to insert compared to std::string
glad saffron
i love writing datastructures so i'll review this in a bit
using g++ 14.2.0 this does not compile
main.cpp: In member function ‘void DynamicArray<T>::insert(T&&)’:
main.cpp:48:33: error: ‘memcpy’ is not a member of ‘std’; did you mean ‘wmemcpy’?
48 | std::memcpy(newMemoryBlock, data.memory, data.memoryUsage);
| ^~~~~~
| wmemcpy
main.cpp:51:59: error: ‘memcpy’ is not a member of ‘std’; did you mean ‘wmemcpy’?
51 | if (!optimizationEnabled) std::memcpy(newMemoryBlock + data.size, &t, data.sizeOfEachElement);
| ^~~~~~
| wmemcpy
the fix is to include cstring
T get(int x) {
if (x > data.size || x < 0 || data.size == 0)
std::runtime_error("DynamicArray error: tried to access out of bounds index.");
return data.memory[x];
}
you make an exception here but never throw it
i believe std::out_of_range would be more appropiate here
for (int i = 0; i < 10; i++) {
d.insert(i);
}
since insert takes T&&, i cant do something like this which is annoying
struct temp {
T* memory;
size_t sizeOfEachElement;
size_t capacity;
size_t memoryUsage;
size_t size;
};
int elementShift;
temp data;
not sure why all the data is in a structure, and why there is so much of it
all you need for a dynamic array is the buffer, length and capacity
inline size_t performance_growth(size_t currentCapacity, size_t minimumSize) {
while (currentCapacity < minimumSize) {
currentCapacity *= 2;
}
return currentCapacity;
}
this seems a little icky to me
data.capacity = sizeof(T) * 16;
data.memory = new T[16];
ideally an empty arraylist would start with no memory allocated
you do not need to make a special case for trivial types, std::copy handles this for you (source: https://en.cppreference.com/w/cpp/algorithm/copy.html)
having iterators would be a nice feature
data.memory[x].~T();
iirc this is ill formed, you should not manually call destructors (someone needs to fact check me though)
glad saffron
Ive measured peformance against std::vector in terms of insert time and it reall...
how did you measure the performance?
in the insert method, optimizationEnabled will never be true, so there are dead branches
no idea what elementShift does, it is always 0
same for memoryUsage, not sure what its for
because the capacity is already how much memory is allocated
cloud wave
i replace T&& with T& so it allows variables to to be passed, i fixed the optimizationEnabled issue and i got rid of the extra memcpy block cuz std copy handlez it already