Creating a tree of vectors

[itsmeandnobodyelse]

Hmm. I thought that is what the deque is for. What is the advantage of a HAT? Plus he has to keep each chunk of the array associated with a key value such as a course number as well. So he needs some kind of ordered tree. Anyway - good luck. If I were the OP I'd have to ask a few more questions about that assignment. I couldn't do it based on the original post. I assume that there was a lecture on the topic so the OP must have more info than us about the teachers expectations.

The advantage is that it doesn't need as much contiguous memory as for a normal array. You know that std::vector guarantees that the internal array can be used for a normal C array. So, if you need 1 million elements for a vector<T> you need contiguous memory for at least 1 million times sizeof(T). In a HAT you would have 1 array with 1024 pointers to 1025 internal arrays each of them only 1024 (2^10) times sizeof(T) in size. And the chunk size wouldn't grow before 2^20 elements were reached. Then the factor would increase from 1024 to 2048.

     [ p0, p1, p2, ..., pm-1]
p0 [ t0, t1, t2, ...,  tm-1]          [ 
p1 [ tm, tm+1, ..., t2m-1]
...

Assume after adding elements to a vector a new array for 2 million elements must be allocated, and you need contiguous memory for that (note, the old array still is allocated as you need rto copy the old elements to the new array). There is a good chance that this request will fail.

For a HAT in the same case you only would need new chunks for 2048 elements and you can free the old arrays after copied a pair of them to the new chunk.

The indexed access for a HAT is a little bit slower as for a dynamic C array. See http://wapedia.mobi/en/Hashed_array_tree for more information.

The implementation of a HAT in C++ is not very difficult. Because the size m of the arrays is a power of two number, a linear index fastly could be computed to a pair of indices needed for accessing the internal HAT arrays.

I used a HAT class for about 10 years with my own library of C++ containers and it was very convenient. Nowadays I use mostly STL containers because they were available on each platform. But in case of huge data amounts I surely would consider to reusing my HAT class.

Regards, Alex

Regards, Alex