Ex$2.$ Class Design

$35$ points

Overview

You are asked in this exercise to complete the design of a given class. Note the following:

The correctness and efficiency of your solution will depend on your choice of the data members.

Your data members are expected to be STL containers $($list$,$ set, vector, map, stack, or queue$).$ The idea is to choose the right container and delegate the work to it in the appropriate function.

Your Task

Complete the implementation of class Classmates, by adding the appropriate data members and implementing the provided operations $($according to the specified running times$).$

Insert

void insert$($string class$\_$name, vector students$)$

This function inserts a new class with the IDs of the students enrolled in that class.

NOTE: If the class was added before, the list of student IDs is replaced with the new one. Moreover, if one of the students from the previous class no longer has any classes then they remain as a student but don't have any active classes $($i$.$e$.$ they aren't removed from Classmates$).$

This function must run in

$$

$($

$$

$($

log

$$

$+$

log

$$

$)$

$)$

O$($m$($logn$+$logm$)),$ where

$$

n is the number of stored classes,

$$

m is the number of stored students.

Print

void print$()$ const;

This function prints the classes and students in the following format, where classes and IDs must be sorted in lexicographic order:

class$1$ : $\{$id$1,$ id$2,$ id$3,...\}$

class$2$ : $\{$id$1,$ id$2,$ id$3,...\}$

$...$

Check Enrollment

bool in$\_$class$($string class$\_$name, string id$)$

This function checks if the given student is enrolled in the given class. If the class is not a known class or if the student is not in the class, the function returns false.

This function must run in

$$

$($

log

$$

$+$

log

$$

$)$

O$($logn$+$logm$),$ where

$$

n is the number of stored classes,

$$

m is the number of stored students.

Get Classes For A Student

set get$\_$classes$($string id$)$

This function returns all the classes the student is enrolled in$.$ If the student is unknown, the function throws a string exception.

This function must run in

$$

$($

log

$$

$+$

$$

$)$

O$($logm$+$n$),$ where

$$

n is the number of stored classes,

$$

m is the number of stored students.

Get Student Classmates

set get$\_$classmates$($string id$)$

This function returns the ids of the students who took classes with the given student. If the student is unknown, the function throws a string exception.

This function must run in

$$

$($

$$

log

$$

$+$

$$

log

$$

$)$

O$($mlogm$+$mlogn$),$ where

$$

n is the number of stored classes,

$$

m is the number of stored students.

#include

#include

#include

using namespace std;

class Classmates $\{$

private:

$//$ add your data members here

public:

$//$ Inserts a new class with the IDs of the students enrolled in it$.$

$//$ If the class was inserted before, the list of student IDs is

$//$ replaced with the new one$).$

$//$

$//$ This function must run in O$($m$($logn $+$ logm$)),$ where $n$ is the

$//$ number of stored classes, and $m$ is the number of stored students.

void insert$($string class$\_$name, vector students$)$;

$//$ prints the classes and students in the following format:

$//$ class$1$ : $\{$id$1,$ id$2,$ id$3,...\}$

$//$ class$2$ : $\{$id$1,$ id$2,$ id$3,...\}$

$//...$

$//$ Classes and IDs must be sorted in lexicographic order

void print$()$ const;

$//$ Checks if the given student is enrolled in the given class.

$//$ If the class is not a known class or if the student is not in the

$//$ class, the function returns false.

$//$

$//$ This function must run in $O$(\backslash$log n $+\backslash$log m$)$$$,$ where $n$ is the

$//$ number of stored classes, $m$ is the number of stored students.

bool in$\_$class$($string class$\_$name, string id$)$;

$//$ Returns all the classes the student is enrolled in$.$ If the student

$//$ is unknown, the function throws a string exception.

$//$

$//$ This function must run in $O$(\backslash$log m $+$ n$)$$$,$ where $n$ is the

$//$ number of stored classes, $m$ is the number of stored students.

set get$\_$classes$($string id$)$;

$//$ This function returns the ids of the students who took classes

$//$ with the given student. If the student is unknown, the function

$//$ throws a string exception.

$//$

$//$ This function must run in $O$($m$\backslash$log m $+$ m$\backslash$log n$)$$$,$ where $n$ is

$//$ the number of stored classes, $m$ is the number of stored students.

set get$\_$classmates$($string id$)$;

$\}$;