Description
Homework 1 gave you extensive experience with the Map type using both arrays and dynamicallyallocated arrays.
In this project, you will re-write the implementation of the Map type to employ a doubly-linked list rather than an array. You must not use arrays.
You will also implement a couple of algorithms that operate on maps. Implement Map yet again Consider the Map interface from problem 2 of Homework 1: typedefTheTypeOfTheKeysGoesHereKeyType; typedefTheTypeOfTheValuesGoesHereValueType; classMap { public: Map(); boolempty()const; intsize()const; boolinsert(constKeyType&key,constValueType&value); boolupdate(constKeyType&key,constValueType&value); boolinsertOrUpdate(constKeyType&key,constValueType&value); boolerase(constKeyType&key); boolcontains(constKeyType&key)const; boolget(constKeyType&key,ValueType&value)const; boolget(inti,KeyType&key,ValueType&value)const; voidswap(Map&other); }; In problem 3 of Homework 1, you implemented this interface using an array.
For this project, implement this Map interface using a doubly-linked list. (You must not use the listclass template from the C++ library.) For the array implementation of problem 3 of Homework 1, since you declared no destructor, copy constructor, or assignment operator, the compiler wrote them for you, and they did the right thing.
For this linked list implementation, if you let the compiler write the destructor, copy constructor, and assignment operator, they will do the wrong thing, so you will have to declare and implement these public member functions as well: Destructor When a Map is destroyed, the nodes in the linked list must be deallocated. Copy constructor When a brand new Map is created as a copy of an existing Map, enough new nodes must be allocated to hold a duplicate of the original list.
When an existing Map (the left-hand side) is assigned the value of another Map (the righthand side), the result must be that the left-hand side object is a duplicate of the right-hand side object, with no memory leak of list nodes (i.e. no list node from the old value of the lefthand side should be still allocated yet inaccessible). Notice that there is now no a priori limit on the maximum number of key/value pairs in the Map (so insertOrUpdateshould always return true).
Also, as in Homework 1, if a Map has a size of n, then the values of the first parameter to the three-parameter form of getfor which that function retrieves a key and a value and returns true are 0, 1, 2, …, n-1; for other values, it returns false without setting its second and third parameters. Another requirement is that as in Problem 5 of Homework 1, the number of statement executions when swapping two maps must be the same no matter how many key/value pairs are in the maps.
Implement some map algorithms Using only the public interface of Map, implement the following two functions. (Notice that they are non-member functions; they are not members of Map or any other class.) boolcombine(constMap&m1,constMap&m2,Map&result); When this function returns, resultmust consist of pairs determined by these rules: If a key appears in exactly one of m1and m2, then resultmust contain a pair consisting of that key and its corresponding value. If a key appears in both m1and m2, with the same corresponding value in both, then resultmust contain a pair with that key and value. When this function returns, resultmust contain no pairs other than those required by these rules. (You must not assume resultis empty when it is passed in to this function; it might not be.)
If there exists a key that appears in both m1and m2, but with different corresponding values, then this function returns false; if there is no key like this, the function returns true. Even if the function returns false, resultmust be constituted as defined by the above rules.
For example, suppose a Map maps strings to doubles. If m1consists of the three pairs (in any order) “Fred” 123 “Ethel” 456 “Lucy” 789 and m2consists of (in any order) “Lucy” 789 “Ricky” 321 then no matter what value it had before, resultmust end up as a map consisting of (in any order) “Fred” 123 “Ricky” 321 “Lucy” 789 “Ethel” 456 and combinemust return true. If instead, m1were as before, and m2consisted of “Lucy” 654 “Ricky” 321
then no matter what value it had before, resultmust end up as a map consisting of (in any order) “Fred” 123 “Ricky” 321 “Ethel” 456 and combinemust return false. voidsubtract(constMap&m1,constMap&m2,Map&result); When this function returns, resultmust contain a copy of all the pairs in m1whose keys don’t appear in m2; it must not contain any other pairs. (You must not assume resultis empty when it is passed in to this function; it may not be.)
For example, if m1consists of the three pairs (in any order) “Fred” 123 “Ethel” 456 “Lucy” 789 and m2consists of (in any order) “Lucy” 789 “Ricky” 321 “Ethel” 654 then no matter what value it had before, resultmust end up as a map consisting of “Fred” 123 If English is not your native language, make extra sure you spell the name of this function correctly: it’s subtract, not substract. Be sure these functions behave correctly in the face of aliasing: What if m1and resultrefer to the same Map, for example? Other Requirements Regardless of how much work you put into the assignment, your program will receive a zero for correctness if you violate these requirements: Your class definition, declarations for the two required non-member functions, and the implementations of any functions you choose to inline must be in a file named Map.h, which must have appropriate include guards.
The implementations of the functions you declared in Map.hthat you did not inline must be in a file named Map.cpp. Neither of those files may have a main routine (unless it’s commented out). You may use a separate file for the main routine to test your Map class; you won’t turn in that separate file. Except to add a destructor, copy constructor, assignment operator, and dumpfunction (described below), you must not add functions to, delete functions from, or change the public interface of the Map class. You must not declare any additional struct/class outside the Map class, and you must not declare any public struct/class inside the Map class.
You may add whatever private data members and private member functions you like, and you may declare private structs/classes inside the Map class if you like. The source files you submit for this project must not contain the word friendor the character [(open square bracket). You must not use any global variables whose values may be changed during execution. If you wish, you may add a public member function with the signature voiddump()const. The intent of this function is that for your own testing purposes, you can call it to print
information about the map; we will never call it. You do not have to add this function if you don’t want to, but if you do add it, it must not make any changes to the map; if we were to replace your implementation of this function with one that simply returned immediately, your code must still work correctly. The dumpfunction must not write to cout, but it’s allowed to write to cerr. Map.cppmust not contain the word stringor double. (Map.hmay contain them only in the typedef statements, and must contain #includeif a typedef statement contains the word string.)
Your code must build successfully (under both Visual C++ and either clang++ or g++) if linked with a file that contains a main routine. You must have an implementation for every member function of Map, as well as the nonmember functions combineand subtract. Even if you can’t get a function implemented correctly, it must have an implementation that at least builds successfully.
For example, if you don’t have time to correctly implement Map::eraseor subtract, say, here are implementations that meet this requirement in that they at least build successfully: boolMap::erase(constKeyType&value) { returnfalse; //notcorrect,butatleastthiscompiles } voidsubtract(constMap&m1,constMap&m2,Map&result) { //doesnothing;notcorrect,butatleastthiscompiles } You’ve probably met this requirement if the following file compiles and links with your code. (This uses magic beyond the scope of CS 32.) #include”Map.h” #include #defineCHECKTYPE(f,t){autop=(t)(f);(void)p;} static_assert(std::is_default_constructible