Creating a tree of vectors
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 6 of 6

Thread: Creating a tree of vectors

  1. #1
    Join Date
    Oct 2009
    Posts
    17

    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:

  2. #2
    Join Date
    Aug 2005
    Location
    San Diego, CA
    Posts
    1,054

    Lightbulb Re: Creating a tree of vectors

    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.

  3. #3
    Join Date
    Oct 2009
    Posts
    577

    Smile Re: Creating a tree of vectors

    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

  4. #4
    Join Date
    Aug 2005
    Location
    San Diego, CA
    Posts
    1,054

    Lightbulb Re: Creating a tree of vectors

    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.

  5. #5
    Join Date
    Oct 2009
    Posts
    577

    Smile Re: Creating a tree of vectors

    Quote Originally Posted by kempofighter View Post
    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

  6. #6
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,357

    Re: Creating a tree of vectors

    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).
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center