Description
Here is a C++ class definition for an abstract data type Map from stringto double, representing the concept of a function mapping strings to doubles. (For example, we could represent a collection of students and their GPAs: “Fred” maps to 2.956, “Ethel” maps to 3.538, “Lucy” maps to 2.956, etc.)
We’ll call the strings the keys and the doubles the values. No two keys in the map are allowed to be the same (e.g., so “Fred” appears no more than once), although two keys might map to the same value (as in the example, where both of the keys “Fred” and “Lucy” map to the value 2.956). To make things simpler for you, the case of letters in a string matters, so that the strings Fredand fReDare not considered duplicates. classMap { public: Map(); //Createanemptymap(i.e.,onewithnokey/valuepairs) boolempty(); //Returntrueifthemapisempty,otherwisefalse. intsize(); //Returnthenumberofkey/valuepairsinthemap. boolinsert(conststd::string&key,constdouble&value); //Ifkeyisnotequaltoanykeycurrentlyinthemap,andifthe //key/valuepaircanbeaddedtothemap,thendosoandreturntrue. //Otherwise,makenochangetothemapandreturnfalse(indicating //thateitherthekeyisalreadyinthemap,orthemaphasafixed //capacityandisfull). boolupdate(conststd::string&key,constdouble&value); //Ifkeyisequaltoakeycurrentlyinthemap,thenmakethatkeyno //longermaptothevalueitcurrentlymapsto,butinsteadmapto //thevalueofthesecondparameter;returntrueinthiscase. //Otherwise,makenochangetothemapandreturnfalse. boolinsertOrUpdate(conststd::string&key,constdouble&value); //Ifkeyisequaltoakeycurrentlyinthemap,thenmakethatkeyno //longermaptothevalueitcurrentlymapsto,butinsteadmapto //thevalueofthesecondparameter;returntrueinthiscase. //Ifkeyisnotequaltoanykeycurrentlyinthemapandifthe //key/valuepaircanbeaddedtothemap,thendosoandreturntrue. //Otherwise,makenochangetothemapandreturnfalse(indicating //thatthekeyisnotalreadyinthemapandthemaphasafixed //capacityandisfull). boolerase(conststd::string&key); //Ifkeyisequaltoakeycurrentlyinthemap,removethekey/value
2/12 //pairwiththatkeyfromthemapandreturntrue. Otherwise,make //nochangetothemapandreturnfalse. boolcontains(conststd::string&key); //Returntrueifkeyisequaltoakeycurrentlyinthemap,otherwise //false. boolget(conststd::string&key,double&value); //Ifkeyisequaltoakeycurrentlyinthemap,setvaluetothe //valueinthemapthatthatkeymapsto,andreturntrue. Otherwise, //makenochangetothevalueparameterofthisfunctionandreturn //false. boolget(inti,std::string&key,double&value); //If0<=i<size(),copyintothekeyandvalueparametersthe //keyandvalueofoneofthekey/valuepairsinthemapandreturn //true. Otherwise,leavethekeyandvalueparametersunchangedand //returnfalse. (Seebelowfordetailsaboutthisfunction.) voidswap(Map&other); //Exchangethecontentsofthismapwiththeotherone. }; (When we don’t want a function to change a key or value parameter, we pass that parameter by constant reference. Passing it by value would have been perfectly fine for this problem, but we chose the const reference alternative because that will be more suitable after we make some generalizations in a later problem.)
The three-argument getfunction enables a client to iterate over all elements of a Mapbecause of this property it must have: If nothing is inserted into or erased from the map in the interim, then calling that version of getrepeatedly with the first parameter ranging over all the integers from 0 to size()-1 inclusive will copy into the other parameters every key/value pair from the map exactly once. The order in which key/value pairs are copied is up to you. In other words, this code fragment Mapm; m.insert(“A”,10); m.insert(“B”,44); m.insert(“C”,10); stringall; doubletotal=0; for(intn=0;n<m.size();n++) { stringk; doublev; m.get(n,k,v); all+=k; total+=v; } cout<<all<<total;
must result in the output being exactly one of the following: ABC64, ACB64, BAC64, BCA64, CAB64, or CBA64, and the client can’t depend on it being any particular one of those six. If the map is modified between successive calls to the three-argument form of get, all bets are off as to whether a particular key/value pair is returned exactly once. If nothing is inserted into or erased from the map in the interim, then calling the three-argument form of getrepeatedly with the same value for the first parameter each time must copy the same key into the second parameter each time, so that this code is fine: Mapgpas; gpas.insert(“Fred”,2.956); gpas.insert(“Ethel”,3.538); doublev; stringk1; assert(gpas.get(1,k1,v) && (k1==”Fred” || k1==”Ethel”)); stringk2; assert(gpas.get(1,k2,v) && k2==k1); Notice that the empty string is just as good a string as any other; you should not treat it in any special way: Mapgpas; gpas.insert(“Fred”,2.956); assert(!gpas.contains(“”)); gpas.insert(“Ethel”,3.538); gpas.insert(“”,4.000); gpas.insert(“Lucy”,2.956); assert(gpas.contains(“”)); gpas.erase(“Fred”); assert(gpas.size()==3 && gpas.contains(“Lucy”) && gpas.contains(“Ethel”) && gpas.contains(“”)); Here’s an example of the swapfunction: Mapm1; m1.insert(“Fred”,2.956); Mapm2; m2.insert(“Ethel”,3.538); m2.insert(“Lucy”,2.956); m1.swap(m2); assert(m1.size()==2 && m1.contains(“Ethel”) && m1.contains(“Lucy”) && m2.size()==1 && m2.contains(“Fred”)); When comparing keys for insert, update, insertOrUpdate, erase, contains, and the twoargument form of get, just use the ==or !=operators provided for the string type by the library. These do case-sensitive comparisons, and that’s fine. Here is what you are to do: 1. Determine which member functions of the Map class should be const member functions (because they do not modify the Map), and change the class declaration accordingly.
2. As defined above, the Map class allows the client to use a map that contains only std::strings as keys and doubles as values. Someone who wanted to modify the class to contain keys or values of another type, such as keys being ints and values being ints, would have to make changes in many places. Modify the class definition you produced in the previous problem to use a typedef-defined type for all keys wherever the original definition used a std::stringfor that purpose, and a typedef-defined type for all values wherever the original definition used a doublefor that purpose.
Here’s an example of a use of typedef: typedefintNumber; //defineNumberasasynonymforint intmain() { Numbertotal=0; Numberx; while(cin>>x) total+=x; cout<<total<<endl; } To modify this code to sum a sequence of longs or of doubles, we need make a change in only one place: the typedef. You may find the example using typedefin Appendix A.1.8 of the textbook useful. To make the grader’s life easier, we’ll require that everyone use the same synonym as their typedef-defined names: You must use the name KeyTypefor the name of the type used for keys, and ValueTypefor the name of the type used for values, with exactly those spellings and case.
3. Now that you have defined an interface for a map class where the key and the value types can be easily changed, implement the class and all its member functions in such a way that the key/value pairs in a map are contained in a data member that is an array. (Notice we said an array, not a pointer. It’s not until problem 5 of this homework that you’ll deal with a dynamically allocated array.) A map must be able to hold a maximum of DEFAULT_MAX_ITEMS distinct keys, where constintDEFAULT_MAX_ITEMS=200; (Hint: Define a structure type containing a member of type KeyType and a member of type ValueType. Have Map’s array data member be an array of these structures.) Test your class for a Map that maps std::strings to doubles.
Place your class definition, non-inline function prototypes, and inline function implementations (if any) in a file named Map.h, and your non-inline function implementations (if any) in a file named Map.cpp. (If we haven’t yet discussed inline, then if you haven’t encountered the topic yourself, all your functions will be non-inline, which is fine.)
You may add any private data members or private member functions that you like, but you must not add anything to or delete anything from the public interface you defined in the previous problem, nor may you change the function signatures. There is one exception to this: 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. Your implementation of the Map class must be such that the compiler-generated destructor, copy constructor, and assignment operator do the right things. Write a test program named testMap.cppto make sure your Map class implementation works properly. Here is one possible (incomplete) test program: #include”Map.h” #include #include usingnamespacestd; intmain() { Mapm; //mapsstringstodoubles assert(m.empty()); ValueTypev=-1234.5; assert(!m.get(“abc”,v) && v==-1234.5);//vunchangedbygetfailure m.insert(“xyz”,9876.5); assert(m.size()==1); KeyTypek=”hello”; assert(m.get(0,k,v) && k==”xyz” && v==9876.5); cout<<“Passedalltests”<<endl; } Now change (only) the two typedefs in Map.hso that the Map type will now map ints to std::strings. Make no other changes to Map.h, and make no changes to Map.cpp. Verify that your implementation builds correctly and works properly with this alternative main routine (which again, is not a complete test of correctness): #include”Map.h” #include #include usingnamespacestd; intmain() { Mapm; //mapsintstostrings assert(m.empty()); ValueTypev=”Ouch”; assert(!m.get(42,v) && v==”Ouch”);//vunchangedbygetfailure m.insert(123456789,”Wow!”); assert(m.size()==1); KeyTypek=9876543; assert(m.get(0,k,v) && k==123456789 && v==”Wow!”);
cout<<“Passedalltests”<<endl; } You may need to flip back and forth a few times to fix your Map.hand Map.cppcode so that the only change to those files you’d need to make to change a map’s key and value types is to the two typedefs in Map.h. (When you turn in the project, have the typedefs in Map.hspecify the key type to be std::stringand the value type to be double.) Except in a typedef statement in Map.h, the word doublemust not appear in Map.hor Map.cpp. Except in a typedef statement and in the context of #includein Map.h, the word stringmust not appear in Map.hor Map.cpp. (Implementation note 1: If you declare another structure to help you implement a Map, put its declaration in Map.h(and newMap.hfor Problem 5), since it is not intended to be used by clients for its own sake, but merely to help you implement the Map class.
In fact, to enforce clients not using that structure type, don’t declare it outside of the Map class; instead, declare that helper structure in the private section of Map. Although it would probably be overkill for this structure to have anything more than two public data members, if for some reason you decide to declare any member functions for it that need to be implemented, those implementations should be in Map.cpp(and newMap.cppfor Problem 5).) (Implementation note 2: The swapfunction is easily implementable without creating any additional array or additional Map.)
4. Now that you’ve implemented the class, write some client code that uses it. We might want a class that keeps track of people enrolled in a weight loss program and their weights in pounds. Implement the following class: #include”Map.h” classWeightMap { public: WeightMap(); //Createanemptyweightmap. boolenroll(std::stringname,doublestartWeight); //Ifapersonwiththegivennameisnotcurrentlyinthemap, //thereisroominthemap,andthestartWeightisnotnegative, //addanentryforthatpersonandweightandreturntrue. //Otherwisemakenochangetothemapandreturnfalse. doubleweight(std::stringname)const; //Ifapersonwiththegivennameisinthemap,returnthat //person’sweight;otherwise,return-1. booladjustWeight(std::stringname,doubleamt); //Ifnopersonwiththegivennameisinthemaporif //weight()+amtisnegative,makenochangetothemapandreturn //false. Otherwise,changetheweightoftheindicatedpersonby //thegivenamountandreturntrue. Forexample,ifamtis-8.2, //thepersonloses8.2pounds;ifit’s3.7,thepersongains3.7
//pounds. intsize()const; //ReturnthenumberofpeopleintheWeightMap. voidprint()const; //Writetocoutonelineforeverypersoninthemap. Eachline //hastheperson’sname,followedbyonespace,followedbythat //person’sweight. private: //Someofyourcodegoeshere. }; Your WeightMap implementation must employ a data member of type Map that uses the typedefs KeyTypeand ValueTypeas synonyms for std::stringand double, respectively.
(Notice we said a member of type Map, not of type pointer to Map.) Except for the typedefs, you must not make any changes to the Map.hand Map.cppfiles you produced for Problem 3, so you must not add any member functions to the Map class. Each of the member functions enroll, weight, adjustWeight, size, and printmust delegate as much of the work that they need to do as they can to Map member functions. (In other words, they must not do work themselves that they can ask Map member functions to do instead.) If the compiler-generated destructor, copy constructor, and assignment operator for WeightMap don’t do the right thing, declare and implement them. Write a program to test your WeightMap class. Name your files WeightMap.h, WeightMap.cpp, and testWeightMap.cpp.
The words forand whilemust not appear in WeightMap.hor WeightMap.cpp, except in the implementation of WeightMap::printif you wish. The characters [(open square bracket) and *must not appear in WeightMap.hor WeightMap.cpp, except in comments if you wish. You do not have to change std::stringto KeyTypeand doubleto ValueTypein WeightMap.h and WeightMap.cppif you don’t want to (since unlike Map, which is designed for a wide variety of key and value types, WeightMap is specifically designed to work with strings and doubles). 5. Now that you’ve created a map type based on arrays whose size is fixed at compile time, let’s change the implementation to use a dynamically allocated array of objects. Copy the three files you produced for problem 3, naming the new files newMap.h, newMap.cpp, and testnewMap.cpp. Update those files by either adding another constructor or modifying your existing constructor so that a client can do the following: Mapa(1000); //acanholdatmost1000key/valuepairs Mapb(5); //bcanholdatmost5key/valuepairs Mapc; //ccanholdatmostDEFAULT_MAX_ITEMSkey/valuepairs KeyTypek[6]={alistofsixdistinctvaluesoftheappropriatetype}; ValueTypev =avalueoftheappropriatetype; //Nofailuresinsertingpairswith5distinctkeysintob for(intn=0;n<5;n++) assert(b.insert(k[n],v)); //Failureifwetrytoinsertapairwithasixthdistinctkeyintob
assert(!b.insert(k[5],v)); //WhentwoMaps’contentsareswapped,theircapacitiesareswapped //aswell: a.swap(b); assert(!a.insert(k[5],v) && b.insert(k[5],v)); Since the compiler-generated destructor, copy constructor, and assignment operator no longer do the right thing, declare them (as public members) and implement them. Make no other changes to the public interface of your class. (You are free to make changes or additions to the private members and to the implementations of the member functions.)
Change the implementation of the swapfunction so that the number of statement executions when swapping two maps is the same no matter how many key/value pairs are in the maps. (You would not satisfy this requirement if, for example, your swap function caused a loop to visit each pair in the map, since the number of statements executed by all the iterations of the loop would depend on the number of pairs in the map.) The character [(open square bracket) must not appear in newMap.h(but is fine in newMap.cpp). Test your new implementation of the Map class. (Notice that even though the file is named newMap.h, the name of the class defined therein must still be Map.) Verify that your WeightMap class still works properly with this new version of Map.
You should not need to change your WeightMap class or its implementation in any way, other than to include “newMap.h”instead of “Map.h”. (For this test, be sure to link with newMap.cpp, not Map.cpp.) (Before you turn in WeightMap.h, be sure to restore the include to “Map.h” instead of “newMap.h”.) Turn it in By Monday, January 18, there will be a link on the class webpage that will enable you to turn in this homework.
Turn in one zip file that contains your solutions to the homework problems. (Since problem 3 builds on problems 1 and 2, you will not turn in separate code for problems 1 and 2.) If you solve every problem, the zip file you turn in will have nine files (three for each of problems 3, 4, and 5). The files must meet these requirements, or your score on this homework will be severely reduced: Each of the header files Map.h, WeightMap.h, and newMap.hmust have an appropriate include guard. In the files you turn in, the typedefs in Map.hand newMap.hmust define KeyTypeto be a synonym for std::stringand ValueTypeto be a synonym for double. If we create a project consisting of Map.h, Map.cpp, and testMap.cpp, it must build successfully under both Visual C++ and either clang++ or g++. If we create a project consisting of Map.h, Map.cpp, WeightMap.h, WeightMap.cpp, and testWeightMap.cpp, it must build successfully under both Visual C++ and either clang++ or g++. If we create a project consisting of newMap.h, newMap.cpp, and testnewMap.cpp, it must build
successfully under both Visual C++ and either clang++ or g++. If we create a project consisting of newMap.h, newMap.cpp, and testMap.cpp, where in testMap.cppwe change only the #include”Map.h”to #include”newMap.h”, the project must build successfully under both Visual C++ and either clang++ or g++. (If you try this, be sure to change the #includeback to “Map.h”before you turn in testMap.cpp.) The source files you submit for this homework must not contain the word friendor vector, and must not contain any global variables whose values may be changed during execution. (Global constants are fine.) No files other than those whose names begin with testmay contain code that reads anything from cinor writes anything to cout, except that for problem 4, WeightMap::printmust write to cout, and for problem 5, the implementation of the constructor that takes an integer parameter may write a message and exit the program if the integer is negative. Any file may write to cerr(perhaps for debugging purposes); we will ignore any output written to cerr. You must have an implementation for every member function of Map and WeightMap. If you can’t get a function implemented correctly, its implementation must at least build successfully.
For example, if you don’t have time to correctly implement Map::eraseor Map::swap, say, here are implementations that meet this requirement in that they at least allow programs to build successfully even though they might execute incorrectly: boolMap::erase(constKeyType&value) { returntrue; //notcorrect,butatleastthiscompiles } voidMap::swap(Map&other) { //doesnothing;notcorrect,butatleastthiscompiles } Given Map.hwith the typedef for the Map’s key type specifying std::stringand the typedef for its value type specifying double, if we make no change to your Map.cpp, then if we compile your Map.cppand link it to a file containing #include”Map.h” #include #include #include usingnamespacestd; voidtest() { Mapm; assert(m.insert(“Fred”,2.956)); assert(m.insert(“Ethel”,3.538)); assert(m.size()==2); ValueTypev=42; assert(!m.get(“Lucy”,v) && v==42);
assert(m.get(“Fred”,v) && v==2.956); v=42; KeyTypex=”Lucy”; assert(m.get(0,x,v) && ((x==”Fred” && v==2.956) || (x==”Ethel” && v==3.538))); KeyTypex2=”Ricky”; assert(m.get(1,x2,v) && ((x2==”Fred” && v==2.956) || (x2==”Ethel” && v==3.538)) && x!=x2); } intmain() { test(); cout<<“Passedalltests”<<endl; } the linking must succeed. When the resulting executable is run, it must write Passedall testsand nothing more to coutand terminate normally. If we successfully do the above, then in Map.hchange the Map’s typedefs to specify intas the key type and std::stringas the value type without making any other changes, recompile Map.cpp, and link it to a file containing #include”Map.h” #include #include #include usingnamespacestd; voidtest() { Mapm; assert(m.insert(10,”diez”)); assert(m.insert(20,”veinte”)); assert(m.size()==2); ValueTypev=”cuarentaydos”; assert(!m.get(30,v) && v==”cuarentaydos”); assert(m.get(10,v) && v==”diez”); v=”cuarentaydos”; KeyTypex=30; assert(m.get(0,x,v) && ((x==10 && v==”diez”) || (x==20 && v==”veinte”))); KeyTypex2=40; assert(m.get(1,x2,v) && ((x2==10 && v==”diez”) || (x2==20 && v==”veinte”)) && x!=x2); } intmain()
{ test(); cout<<“Passedalltests”<<endl; } the linking must succeed. When the resulting executable is run, it must write Passedall testsand nothing more to coutand terminate normally. Given newMap.hwith the typedef for the Map’s key type specifying std::stringand the typedef for its value type specifying double, if we make no change to your newMap.cpp, then if we compile your newMap.cppand link it to a file containing #include”newMap.h” #include #include #include usingnamespacestd; voidtest() { Mapm; assert(m.insert(“Fred”,2.956)); assert(m.insert(“Ethel”,3.538)); assert(m.size()==2); ValueTypev=42; assert(!m.get(“Lucy”,v) && v==42); assert(m.get(“Fred”,v) && v==2.956); v=42; KeyTypex=”Lucy”; assert(m.get(0,x,v) && ((x==”Fred” && v==2.956) || (x==”Ethel” && v==3.538))); KeyTypex2=”Ricky”; assert(m.get(1,x2,v) && ((x2==”Fred” && v==2.956) || (x2==”Ethel” && v==3.538)) && x!=x2); } intmain() { test(); cout<<“Passedalltests”<<endl; } the linking must succeed. When the resulting executable is run, it must write Passedall testsand nothing more to coutand terminate normally. If we successfully do the above, then in newMap.hchange the Map’s typedefs to specify intas the key type and std::stringas the value type without making any other changes, recompile newMap.cpp, and link it to a file containing #include”newMap.h”
#include #include #include usingnamespacestd; voidtest() { Mapm; assert(m.insert(10,”diez”)); assert(m.insert(20,”veinte”)); assert(m.size()==2); ValueTypev=”cuarentaydos”; assert(!m.get(30,v) && v==”cuarentaydos”); assert(m.get(10,v) && v==”diez”); v=”cuarentaydos”; KeyTypex=30; assert(m.get(0,x,v) && ((x==10 && v==”diez”) || (x==20 && v==”veinte”))); KeyTypex2=40; assert(m.get(1,x2,v) && ((x2==10 && v==”diez”) || (x2==20 && v==”veinte”)) && x!=x2); } intmain() { test(); cout<<“Passedalltests”<<endl; } the linking must succeed. When the resulting executable is run, it must write Passedall testsand nothing more to coutand terminate normally.
During execution, your program must not perform any undefined actions, such as accessing an array element out of bounds, or dereferencing a null or uninitialized pointer. Notice that we are not requiring any particular content in testMap.cpp, testWeightMap.cpp, and testnewMap.cpp, as long as they meet the requirements above. Of course, the intention is that you’d use those files for the test code that you’d write to convince yourself that your implementations are correct. Although we will throughly evaluate your implementations for correctness, for homeworks, unlike for projects, we will not grade the thoroughness of your test cases. Incidentally, for homeworks, unlike for projects, we will also not grade your program commenting.
