The default way to implement dynamic arrays is to use realloc. Once len == capacity we use realloc to grow our array. This can cause copying of the whole array to another heap location. I don't want this copying to happen, since I'm designing a dynamic array that should be able to store large amount of elements, and the system that would run this code won't be able to handle such a heavy operation.

Is there a way to achieve that?

I'm fine with loosing some performance - O(logN) for search instead of O(1) is okay. I was thinking that I could use a hashtable for this, but it looks like I'm in a deadlock since in order to implement such a hashtable I would need a dynamic array in the first place.

Thanks!

CodePudding user response：

Not really, not in the general case.

The copy happens when the memory manager can't increase the the current allocation, and needs to move the memory block somewhere else.

One thing you can try is to allocate fixed sized blocks and keep a dynamic array pointing to the blocks. This way the blocks don't need to be reallocated, keeping the large payloads in place. If you need to reallocate, you only reallocate the array of reference which should be much cheaper (move 8 bytes instead 1 or more MB). The ideal case the block size is about sqrt(N), so it's not working in a very general case (any fixed size will be some large or some small for some values).

CodePudding user response：

I ended up with the following:

1. Implement "small dynamic array" that can grow, but only up to some maximum capacity (e.g. 4096 words).
2. Implement an rbtree
3. Combine them together to make a "big hash map", where "small array" is used as a table and a bunch of rbtrees are used as buckets.
4. Use this hashmap as a base for a "big dynamic array", using indexes as keys

While the capacity is less than maximum capacity, the table grows according to the load factor. Once the capacity reached maximum, the table won't grow anymore, and new elements are just inserted into buckets. This structure in theory should work with O(log(N/k)) complexity.