4
\$\begingroup\$

I am currently working in a project (I have simplified it for the sake of question) that requires a container to store students and retrieve them as fast as possible or access them with \$O(1)\$ if possible. I will also be deleting students from any place but always adding them at the end of the queue.

I have three structs: Student, Class and University.

  • Student: has name and age
  • Class: has name of course and array of shared pointers of size 2
  • University: has deque of Students and deque of class

#include <memory>
#include <deque>
#include <string>
#include <iostream>

constexpr size_t SIZE = 150;


struct Student{
    std::string name;
    size_t age;

    Student(std::string n, size_t a){
        name = n;
        age = a;
    }
    ~Student(){
        std::cout << __func__ << std::endl; 
    }
};

struct Class{
    // Lets assume that each class has 2 student for the sake of argument
    // and exactly 2.
    std::shared_ptr<Student> my_class[2];
    std::string course;

    Class(std::string c, std::shared_ptr<Student> n0, std::shared_ptr<Student> n1){

        course = c;
        my_class[0] = n0;
        my_class[1] = n1;
    }
};

struct University{

    std::deque<std::shared_ptr<Student>> student_deq;
    std::deque<std::shared_ptr<Class>> class_deq;

    void add_student(std::string n, size_t a){
        student_deq.push_back(std::make_shared<Student>(n, a));
    }

    void add_class(std::string c, size_t i, size_t j){
        class_deq.push_back(std::make_shared<Class>(c, student_deq[i], student_deq[j])); 
    }
};

int main(){

    University u;

    for(size_t i = 0; i < SIZE; i++){
        u.add_student("Xyz", i);
    } 

    for(size_t j = 0; j < SIZE; j++){
        if(j+1 == SIZE)
            u.add_class("abc", j, 0);
        else u.add_class("abc", j, j+1);
    }
    std::cout << u.student_deq[9]->name << std::endl;
return 0;
}

I have some questions:

  1. Do you think my choice of deque as a data structure (container) is appropriate?

    I want the retrieve (from anywhere) / add (to end)/ remove (from anywhere) to be \$O(1)\$. I use deque because unlike vector it does not have to copy all the data from beginning of the array in case the memory grows and have to allocate new slab of contiguous memory. Since deque is made of small chunks of contiguous memory not all chunks need to be copied (at least that is what I think of). Also the retrieve and add to end is \$O(1)\$ in case of deque. I know remove is \$O(n)\$: \$n\$ being size of one of the chunk of contiguous memory the item reside in.

    I think I could also use HashMap (unordere_map) but I read somewhere that hash_map does not necessarily give \$O(1)\$ because of collision when data gets huge and also my student number will definitely grow hugely (e.g. 100,000 and up also for sake of argument). I also heard that implementing hash function to avoid collision is complex.

    I also think I can't use std::map since retrieval is \$O(ln)\$.

  2. Do you think the use of shread_ptr inside the deque for memory management is a good design choice?

    I used sharad_ptr so that I don't have to do the manual delete of the allocated memory. I also make the class store the shared_ptr rather than a copy of the student because the Student class may contain other information that might be costly to copy. Also a student can be in more then one class ( This way instead of creating multiple copy shared_ptr will only increase the count - Here also I am not sure is it really necessary to increase count because since there will only be one copy I was also thinking about passing by const ref so that we dont have the overhead of increasing the count itself)

  3. Is there a container which gives \$O(1)\$ for retrieval, adding to the end and removal from anywhere in the container (of-course except hash map as I discussed about it above) or anything that is close enough that provide these features?

\$\endgroup\$
  • \$\begingroup\$ When you talk about O(1) retrieval what are you looking it up by? By the index or by the student's name? If you are looking up the student by their name, a deque will not be O(1) retrieval. \$\endgroup\$ – Tolli Oct 16 '16 at 23:23
  • 1
    \$\begingroup\$ @Tolli by index and sure if I look by index name it won't be O(1) it will rather be O(n) \$\endgroup\$ – solti Oct 17 '16 at 0:38
  • 1
    \$\begingroup\$ I'm surprised that you are looking up by index. How do you know what index you want? Especially since you want to be able to remove from anywhere in the list. When you do that, all the indexes from that point in the list on will have decreased by one. \$\endgroup\$ – Tolli Oct 17 '16 at 2:38
  • \$\begingroup\$ @Tolli U r right .. so to take care of that I have update() function which subtract the index by length of items removed .. I know that is not the best solution but thats what I have so far in my mind .. not sure there is any more improvement then that .. hopefully there is :/ \$\endgroup\$ – solti Oct 17 '16 at 17:01
  • 1
    \$\begingroup\$ Personally I would not use a pointer (too dangerious). But a class could hold an array of student ID. You can then look the student up at the university using the ID. Now just because you hold the ID in the class does not mean a getter function would return an ID when you ask for a student the class would use the ID to look up the student internally and return a reference (this time a C++ reference) to the student. But that may be overthinking it at this level. \$\endgroup\$ – Martin York Oct 17 '16 at 21:16
3
\$\begingroup\$

Do you think my choice of deque as a data structure (container) is appropriate?

Seems good.

I want the retrieve (from anywhere) / add (to end)/ remove (from anywhere) to be O(1)O(1).

See: What are the complexity guarantees of the standard containers?

So std:: deque does not provide a O(1) erase (remove).

I use deque because unlike vector it does not have to copy all the data from beginning of the array in case the memory grows and have to allocate new slab of contiguous memory. Since deque is made of small chunks of contiguous memory not all chunks need to be copied (at least that is what I think of). Also the retrieve and add to end is O(1)O(1) in case of deque. I know remove is O(n)O(n): nn being size of one of the chunk of contiguous memory the item reside in.

All that is correct. Just does not make removal O(1). Because the chunks can be large m. The removal of an item is O(m) where m is the size of the chunk.

I think I could also use HashMap (unordere_map)

That does support all the requirements you need.

but I read somewhere that hash_map does not necessarily give O(1)O(1) because of collision when data gets huge and also my student number will definitely grow hugely (e.g. 100,000 and up also for sake of argument).

Yes collisions will add time. But they do not change the complexity. It still remains O(1).

I also heard that implementing hash function to avoid collision is complex.

It is exceedingly complicated to do correctly and you should never do this. Use the standard one. Only implement a hash function if that is your actual job (or you are some kind of maths genius). This is too easy to get wrong so use a good well known hash (the one provided by the standard is fine).

I also think I can't use std::map since retrieval is O(ln)O(ln).

Correct.

Do you think the use of shread_ptr inside the deque for memory management is a good design choice?

No. Given the choice between dynamic/automatic variables you should always prefer automatic variables.

But you don't provide enough details to provide a good answer either. Personally I would have one entity that owns all the students (say the University). Then you classes can contain references to the object owned by the university (ie they could iterators as a reference).

I used sharad_ptr so that I don't have to do the manual delete of the allocated memory.

That's a good thing and correct usage if you are using dynamic memory. But as stated above I don't think dynamic memory is the correct solution.

I also make the class store the shared_ptr rather than a copy of the student because the Student class may contain other information that might be costly to copy.

Sure. You should not have two copies of the same data. That will just introduce consistency issues. But that still does not require dynamic memory allocation. The class store can store so other type of reference to the object (Note: I use the term reference at the conceptual level not the C++ language level).

Also a student can be in more then one class ( This way instead of creating multiple copy shared_ptr will only increase the count - Here also I am not sure is it really necessary to increase count because since there will only be one copy I was also thinking about passing by const ref so that we dont have the overhead of increasing the count itself).

Don't do that. The whole point of using the shared pointer is to make sure it correctly exists when you access it. If you do this it could be destroyed and then you try and access it via a class and get undefined behavior. A better solution here would be to use a std::weak_ptr. But I still prefer my technique of using a reference (even if that means more work cleaning up).

Is there a container which gives O(1)O(1) for retrieval, adding to the end and removal from anywhere in the container (of-course except hash map as I discussed about it above) or anything that is close enough that provide these features?

See the provided link above.

\$\endgroup\$
  • \$\begingroup\$ I really appreciate your elaborated answer and the link .. I think I will go with automatic variable while storing student object in the studet_deq as you suggested .. Also as @Tolli pointed out erasing element from the deque increases another problem ( where I have to call the update function, which takes care of fixing the broken indexing) I am now thinking of using unordere_map .. I will update by comparing both (deque and unordere_map aka hash_map) of my approach. \$\endgroup\$ – solti Oct 17 '16 at 17:29
  • \$\begingroup\$ When you say "Then your classes can contain references to the object owned by the university (ie they could iterators as a reference). ... Note: I use the term reference at the conceptual level not the C++ language level)." what do really mean here .. do you mean classes store the address aka pointers to the students that are stored in universtiy and not reference because (stackoverflow.com/questions/1164266/…) it seems we cannot create array of reference \$\endgroup\$ – solti Oct 17 '16 at 18:13
  • \$\begingroup\$ When I say classes store the address aka pointers to the students I mean : struct Class now has Student* my_class[2]; \$\endgroup\$ – solti Oct 17 '16 at 18:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.