Use of containers for storing Students

Question

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?

Answer 1

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.