A map or a dictionary, also known as an associative array, is a data structure in which key$-$value pairs can be inserted; then you can access any value by supplying the key. It's like an array in which you can access elements with perhaps a string index $($key$)$ or any other type of index. We assume that the keys are unique so if you insert a key$-$value pair and the key already exists then you just overwrite the value.

Write a C$++$ template class to represent a map. To avoid name collisions you can call your class 'Dict'. Use a BST to implement your class. You will need to create a C$++$ template class for the BST$.$ You can modify the code that we presented in class for the BST$.$ Test your map$/$dictionary with the following main function:

$```$

#include

#include

#include "Dict.hpp$"$

using namespace std;

int main$()$

$\{$

Dict phone$\_$directory;

phone$\_$directory.add$("$Tom$",4236)$;

phone$\_$directory.add$("$Pat$",4237)$;

cout $$ "Tom $"$ "Ext.: $"$ phone$\_$directory$["$Tom$"]$ endl;

cout $$ "Pat $"$ "Ext.: $"$ phone$\_$directory$["$Pat$"]$ endl;

Dict id$\_$numbers;

id$\_$numbers.add$(1023\backslash$overline$\{0\}4,$ "Tom"$)$;

id$\_$numbers.add$(102305,$ "Pat"$)$;

cout $$ id$\_$numbers $[102304]$ endl;

cout $$ id$\_$numbers$[102305]$ endl;

return $0$;

$\}$

$```$ In this case your program should output:

Tom Ext.: $4236$

Pat Ext.: $4237$

Tom

Pat

Submit all source files needed to build and run your program to Gradescope.