To determine whether or not a character is present in this set, the STL find(value) method does a binary search down through this tree until it either locates value, or reaches the bottom of the tree. It should be evident that the maximum time to for such a search is O(lg(n)), where n is the number of items in the set.
Our application also stores (userName, password) pairs in an STL map -- a tree-based data structure that provides a similar O(lg(n)) access time. For example, if we have a map<string, string> named myAccounts and we write:
myAccounts["anne"] = "enna"; myAccounts["bill"] = "llib"; myAccounts["carol"] = "laroc";then we might (simplistically) visualize our map as follows:
Because it associates one value (e.g., the user-name) with another value (e.g., the password), and supports the array-subscript notation, an STL map is sometimes called an associative array. However where a normal array requires O(1) time to access a random value and O(n) time to find a value (or determine that it is not there), a map requires O(lg(n)) time to access a random value and O(lg(n)) time to find a value (or determine it is not there).
The exercise will provide you with a "skeleton" application, which you will then complete by adding additional functionality.
Make sure you have accepted the GitHub assignment at this time. See the schedule.
When dealing with menu-driven systems, one thing that can go wrong is if the user enters an invalid choice -- something that is not on the menu. When this happens, the program must detect it and take a remedial action.
One way to detect such problem is to build a Menu class that, besides "remembering" its menu, "remembers" its set of valid menu choices. Then when the user enters a choice, we can validate their choice by checking whether or not their choice is an element of that set.
As you can see, our Menu class contains two instance variables: a string storing the menu, and a set to store those menu choices that are valid:
string myValue; // the menu that is displayed set<char> myValidChoices; // the valid menu choicesSave/compile your project, and verify that everything compiles without errors.
Then run your project's tests, and verify that it fails the tests. We are failing these tests because (i) we are not initializing myValidChoices, and (ii) our Menu::containsChoice() method is incompletely defined. Fixing these problems is our first task.
The Menu constructor currently initializes our myValue member; it must also initialize myValidChoices so that it stores the valid menu choices. To do so, we can use the insert() method:
setVariable.insert(value);
that inserts a single value into a set.
In Menu.cpp, add insert() messages to make myValidChoices represent the set {'a', 'b', 'c', 'd', 'q'}.
To let a program conveniently check whether or not a given character is a valid menu choice, the Menu class provides a boolean method containsChoice(choice) that returns true if and only if choice is a valid menu choice. Currently, this method is a stub-definition that returns false. Your next task is to revise this stub so that is returns true if and only if choice is in the set myValidChoices.
We can accomplish this using the find() method:
set<type>::iterator it = setVariable.find(value)
If value is present in the set, the method returns an iterator pointing to that value; otherwise, it returns setVariable.end(). Moreover, the find() method requires just O(lg(n)) comparisons to either locate the value or to determine that the value is not in the set.
Using this information, revise the definition of containsChoice(choice) so that it returns true if and only if choice is present in myValidChoices. (Hint: you should be able to do this with a single line of code.)
In the file MenuTester.cpp, the runTests() method tests both the Menu constructor and the containsChoice() method. Save/compile your project, and when it is free of compilation errors, run the tests. When your project passes all tests, continue.
Your Menu class now provides us with the ability to:
Since Menu has passed our tests, close the Menu-related files and open the AccountManager-related files. Take a few minutes to look over these files, and examine the tests they contain. The file AccountManager.h contains the declaration of class AccountManager. This class uses an STL map to store (userName,password) pairs:
map<string, string> myAccounts; // maps userNames to passwordsand provides an efficient (O(lg(n))) way to retrieve the stored information.
The AccountManager constructor has been defined for you, as have the createNewAccount() methods:
In tester.cpp, uncomment the two lines that declare and run the AccountManagerTester. Save/compile, run the test. Examine the definition of runTests() and you'll see it presently invokes just testCreateAndDelete(). If you examine the test in testCreateAndDelete(), you'll see the problem is that AccountManager.cpp contains just a stub definition for the AccountManager::deleteAccount() method. Your next task is to add statements to this stub so that it passes all future tests.
Using information from the C++ Reference, take a stab at defining this method so that it passes the tests. Here is a hint in case you get stuck.
Continue when your method passes all tests.
In AccountManagerTester.cpp, uncomment the definition and declaration of testChangeUser(). Save/compile, and run the test (which should fail). This test-method tests the changeUserName() method, whose definition is just a stub. Your next task is to add statements to this method so that it passes the tests.
Note that we cannot simply get an iterator to the correct <userName, password> account-pair and then use it->first to change the userName. The reason is that the userName in the pair is the key whose value determines the position of the account-pairs within our map's binary search tree. If we could change that key to an arbitrary value, we could violate the ordering of the nodes in the tree.
Instead, we will need to get an iterator to the correct pair, use it->second to retrieve and save the password, erase the existing account-pair from the tree, and then create a new account-pair with the new user-name and the saved password.
Using information from the C++ Reference, take a stab at defining this method so that it passes the tests. This one is more involved than deleteAccount(), so here is a hint in case you get stuck.
Continue when your method passes all tests.
In AccountManagerTester.cpp, uncomment the definition and declaration of testChangePassword(). Save/compile, and run the test (which should fail). The problem is the changePassword() method, whose definition is just a stub. Your next task is to add statements to this method so that it passes the tests.
Note that since the password is the second part of the account-pair, we can change this part of the pair and not violate the ordering of the nodes in our map's binary search tree.
Using information from the C++ Reference, take a stab at defining this method so that it passes the tests. This one is similar to deleteAccount(), so give it a try on your own. Only use this hint if you get stuck.
Continue when your method passes all tests.
Your AccountManager should now be passing all of its tests. Congratulations!
When your project is working and has been thoroughly tested, if you would like the AccountManager class to auto-save the changes you make back to the accountInfo.txt file, uncomment the AccountInfo destructor code.
Congratulations! You now have a simple (userName,password) account manager!
As you can see from this exercise, the STL set<Type> is a data structure in which you can store arbitrary items of the given Type, through which you can search in O(lg(n)) time.The STL map is a data structure in which you can store pairs of items of arbitrary types, associating the first item with the second item. A map object acts as an associative array: using the first item as an index (e.g., mapObject[firstItem]), you can retrieve the second item in O(lg(n) time. Just as a mathematical function F(D) -> R maps specific values from a domain set D to specific values from a range set R, an object whose type is map<Domain, Range> can be thought of as mapping items from Domain to items from Range.
Submit your project to Github as normal!