CS 112 Lab 11: The STL set and map Containers

Objectives:

In this exercise, you will:
  1. Use the STL set container to store a set of values.
  2. Use the STL map container to create an associative array whose items are string values, and whose indices are also string values.
  3. Use iterators to access the items in these containers.

Introduction

Today's exercise is to complete a simple "account manager" application. The application reads a file containing user-name and password information, and then allows a system administrator to perform a variety of operations, including: The application presents a menu from which the user can select the operation s/he wishes to perform. To validate a user's menu-choice, our project uses a tree-based data structure -- the STL set. For example, if the valid menu choices are a, b, c, d, e, f, and q, and we store these choices in a set named myValidChoices, then we might (simplistically) visualize this set as follows:

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.

Getting Started

Begin by creating a new project for this week's files. Download manageUserAccounts.cpp, AccountManager.h, AccountManager.cpp, AccountManagerTester.h, AccountManagerTester.cpp, Menu.h, Menu.cpp, MenuTester.h, MenuTester.cpp, tester.cpp, Exception.h, accountInfo.txt, and testAccountInfo.txt. Import these files into your project, open the Menu-related files, and personalize their opening documentation. Then take a few minutes to look them over, to become familiar with their contents.

Part I. The Menu Class

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 choices
Save/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

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'}.

The Menu::containsChoice() Method

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.

Part II. The AccountsManager Class

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 passwords
and 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:

The deleteAccount() Method

In tester.cpp, uncomment the two lines that declare and run the AccountManagerTester. Save/compile, run the test, and verify that we fail 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 the test.

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.

The ChangeUserName() Method

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.

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.

The ChangePassword() Method

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.

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.

The Final Test

Your AccountManager should now be passing all of its tests. Congratulation!

As a final test, comment out the main() function in tester.cpp. Then uncomment the main() function in manageUserAccounts.cpp, and save/compile your project. If all is well, you should be able to run your project and test your methods to see if they work properly. If not, debug your project, using either the debugger, the AccountManager::printAccount() method, or both.

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.

Turn In

Copy your project to a new /home/cs/112/current/yourUserName/lab11 folder.

I hope that these exercises have helped you learn more about data structures and C++, and that what you have learned through them will be beneficial to you in the future.

All the best!

-Joel.


CS > 112 > Labs > 11


This page maintained by Joel Adams.