Outline: in this assignment you will implement both the Map and the Unordered Map abstract data types

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

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.

$3.$ Unique keys $$ no two elements in the container can have equivalent keys.

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$)$;

o 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$)$;

o 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$)$;

o remove from map element at iterator position and rebalance the underlying tree.

$$ void erase$($iterator first, iterator last$)$;

o remove from map a range of elements between first and last and rebalance the underlying tree.

$$ void clear$()$;

o remove and destroy all elements from map

$$ iterator find$($const key$\_$type& k$)$;

o 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;

o return true if map is empty.

$$ int size$()$ const;

o return number of elements in map container.

$$ int max$\_$size$()$ const;

o return max number of elements map can hold

$$ iterator findMin$()$; and iterator findMax$()$; $($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\mathrm{.}8\mathrm{.}3)$ of the Weiss textbook gives some hints on how to go about creating a BST iterator.