Scribd
Upload
19 views2 pages

Assignment 05 w24

Uploaded by

Hamid Baghernia
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
19 views2 pages

Assignment 05 w24

Uploaded by

Hamid Baghernia
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

CS304 Assignment 5: Map and Unordered Map

Outline: in this assignment 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 (40%) – 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<const key_type, mapped_type>)

• 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.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 (40%) – 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 𝑂(1) find and remove. The
drawback is that the elements are no longer ordered, so it does not support findMin or findMax, 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);


o 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<iterator, bool> insert(const value_type& val);
o 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);
o 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;
o remove and destroy all elements in the container.
• iterator find(const key_type& k);
o 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);
o search container for element with key k, return true if found, false otherwise.
• bool empty() const noexcept;
o return bool indicating whether or not the container is empty.
• int size() const noexcept;
o return number of elements in the container.
• int max_size() const noexcept;
o 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 (20%)

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

You might also like