HW5 Set Data Structure Solution

Summary




One of the benefits of data structures is to organize data and have automatic actions on the data. For this homework assignment, you are to experiment with your own implementation of a Set.




Skills Expected




All previous skills up to now



Templates



Assignment Description




Design and create a “Set” class that keeps track of only unique values (“key”) as well as how many times a user has attempted to add a “key” to the structure (“counter”). This Set data structure should be able to keep track of any objects (use templates) and use the object’s == overload to determine whether it’s a unique instance or a duplicate instance.




For example, if the user attempts to add “Cat 1”, “Cat 2”, “Cat 3”, “Cat 2”




The set would only contain one instance of “Cat 1”, “Cat 2”, “Cat 3” and that the user attempted to enter “Cat 2” twice.

Grading Criteria




One example object with templated data o [2 Points] Proper header file
o [1 Point] Ability to handle all objects (use of template)

o [1 Point] Constructor that takes in data for the object (enforce invariants)




o [2 Points] == overload for the object

Set class
[2 Points] Proper header file
[1 Point] Ability to handle all objects (use of template)
[2 Points] Insert keeps track of only unique values (“key”)
[1 Point] Insert also keeps track of how many times a user has attempted to add a “key” to the structure (“counter”)
[1 Point] A way to obtain the “counter” for a given “key”
[2 Points] A way to display the “top 3” keys in the structure (With the top 3 highest counters)



Driver

[1 Point] Written instructions on how to execute your program
[1 Point] Screen capture of program execution o [1 Point] Creation of a valid example object



o [2 Points] Demonstration of use of Set (e.g. attempt to enter in 10 objects where at least two are “duplicates” of things already in the Set)

o [1 Point] Adding an item that already exists in the set (also demonstrate increase in the “counter” for that specific “key”)

o [1 Point] Demonstration of “top 3” in Set

o [1 Point] Print out everything that is in the set (key + counter)

[2 Points] Big-O Analysis of the “Insert” and “Top 3” functions