Creating a tree of vectors

I understand the assignment for the most part, but I have never heard of creating a tree of vectors. After searching online I found someone asking the same question in another forum, but not getting any responses. I don't need code necessarily, just some advice on how to approach this. Thanks.

A registrar gives you a task of developing a data structure so that a student registration
information such as enrollment date, name, enrollment status (enrolled, withdrawn), submitted
fee (full, partial, none), grade (‘A’, ‘B’, ‘C’, ‘D’, ‘F’) can be inserted and deleted by giving the course
number and the social security number of a student. You ask professor Bansal, and he tells you to
create a search-tree of vectors (arranged by course-number) where each tree node contains the
course number and a pointer to the corresponding vector. Each vector contains the information
about the students. Each vector node is a struct containing following fields: (social security
number, name, enrollment date, enrollment status, submitted fee, and grade). Write a program
library to perform the following operations:

So he wants an associative array of some kind where the key is course number and the value is the array of student records associated with the course? Do you have to make the tree yourself or use an existing associative container such as std::map? If you can just use std::map I think that it is easy.

First you have one big set of the student objects that is sorted by SSN. Yes I mean std::set. The set uses a predicate that sorts students by SSN. You have your map of courseNumber to vector<student>. you can easily find students by SSN in the set by creating a temp student object with the applicable SSN. So when the user says add these students to this course you build up a vector by copying the student records from the master into the vector. Then you can insert or update the value in the associative array which in the case of your map is a tree of vectors.

If you have to write your own code for the so-called "tree" good luck. I would recommend doing it with the std::map first to keep things simple and then later you can substitute it with your own concoction. Of course those are just ideas. There are many ways of doing it.

Those 'tree of vectors' are better known as 'Hashed Array Tree' or HAT where you should find a lot of samples in the web.

The idea is to allocating smaller junks of memory when the array was growing by dividing the array into 2^(n-1)+1 to 2^n sub-arrays where n = log2(array_size-1) + 1.

If doing so the requirement for contiguous memory even for huge arrays significantly was reduced while the access to the HAT elements nearly is as fast as with a normal vector.

Regards, Alex

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.

Quote:

---

Originally Posted by kempofighter

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.

Code:

---

    [ 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

itsmeandnobodyelse, I think that kempofighter's point is that the HAT that you describe sounds like a possible implementation of a std::deque (i.e., we're not talking about std::vector any more).