Outline: in this you will implement both the Map and the Unordered Map abstract data types as C++ classes, using a self-balancing BST and a hash table respectively as the underlying data structures. You will then use your maps to solve some well-known programming problems (part 3). Part 1: Map ADT - maps are associative containers that store elements formed by a combination of key type and mapped type. The keys are used to sort and uniquely identify the elements, while the values store the content associated to the key. The map has the following properties: 1. Associative - elements in the container are referenced by their key and not by their absolute position in the container. 2. Ordered - elements in the container follow a strict order at all times. Unique keys - no two elements in the container can have equivalent keys. 3. Implement a map ADT using a self-balancing BST (AVL or red-black tree) as the underlying data structure. In addition to the big 5, it must support the following operations: (where value_type is a pair) • • • mapped_type& operator () (const key_type& k); о if k matches the key of an element in the container, return a reference to its mapped value. If k does not match the key of an element in the container, insert a new element with key k and value constructed using the default constructor of mapped_type and return that instead. iterator insert (iterator position, const value_type& val); о insert val into map at position. If the key already exists, return an iterator to that pre-existing element. Must also verify that the insert operation does not violate the order property of the map. void erase (iterator position); ○ void erase (iterator first, iterator last); remove from map element at iterator position and rebalance the underlying tree. • remove from map a range of elements between first and last and rebalance the underlying tree. void clear(); о • • о remove and destroy all elements from map iterator find (const key_type& k); о search container for element with key equivalent to k, return an iterator to that element if found otherwise an iterator to map::end. bool empty() const; о return true if map is empty. • • int size() const;B о return number of elements in map container. int max_size() const; return max number of elements map can hold iterator find Min(); and iterator find Max(); (self-explanatory) Must also provide an iterator inner class that provides the following methods with the expected behaviour: • begin • end ++ (increment) * (dereference) Your iterator must support an infix traversal of the tree (it should print out a sorted list when used in a range-based 'for' loop). Page 176 (section 4.8.3) of the Weiss textbook gives some hints on how to go about creating a BST iterator. See the C++ std::map reference: https://cplusplus.com/reference/map/map/for further details and usage examples. Part 2: Unordered Map - similar to maps, unordered maps are associative containers that store key-value pairs. However, the unordered map is implemented using a hash table instead of a tree, which allows for 0 (1) find and remove. The drawback is that the elements are no longer ordered, so it does not support find Min or find Max, and cannot produce a sorted output using iterator traversal. Implement an unordered map ADT using a hash table (separate chaining or double hashing) as the underlying data structure. You may use std libraries for the linked list (separate chaining) and hash functions. If the hash table becomes overloaded (λ > 0.5) it should allocate more space and rehash all the existing elements. Don't forget the big 5! • • • mapped_type& operator () (const key_type& k); if k matches the key of an element in the container, the function returns a reference to its mapped value. If k does not match the key of any element, insert a new key-value pair with key k and value constructed using mapped_type default constructor and return a reference to the new mapped_type object. Pair insert (const value_type& val); insert val into the unordered map. Return a pair object whose first element is either an iterator pointing to the newly inserted element or a pre-existing element with equivalent key, and a bool value indicating if the new element was successful inserted or not (false if the key already exists). int erase (const key_type& k); о remove the element with key k from the map. Return 1 if erase succeeded and 0 if it failed (because k did not exist). void clear() noexcept; о remove and destroy all elements in the container. iterator find (const key_type& k); о search container for element with key k, return an iterator to it if found, otherwise return iterator to unordered_map: : end. bool contains (const key_type& k); • • • о search container for element with key k, return true if found, false otherwise. return bool indicating whether or not the container is empty. bool empty() const noexcept; о int size() const noexcept; return number of elements in the container. int max_size() const noexcept; Return maximum number of elements the container can hold As with the map, unordered map must provide an iterator. However, the unordered map iterator need not print the elements in order, it can simply traverse elements of the hash table (skipping empty spots). See the C++ std::unordered_map reference: https://cplusplus.com/reference/unordered map/unordered map/for further details and usage. Part 3: Programming problems Use your unordered map to solve the following leetcodes, provide your solution code: • two sum, longest substring without repeating characters substring with concatenation of all words Use your map (tree implementation) to solve: • Sliding window maximum