Maps and Sets FAQ

The subscript operator is used to access the value associated with a particular key in the map. For example, if I have the following map of strings to integers:

 
	myMap<string,int>
	Key -> Value
	-------------
	"a" -> 60
	"b" -> 20
	"c" -> 90
	"d" -> 400
					

Then I can access the value associated with "c" as follows:

	cout << myMap["c"]; //outputs "90"

The operator should return a reference to the object contained at the given key. This allows you to change what is stored in the map simply using the assignment operator, as follows:

	myMap["c"] = 42; //changes the value at key "c" to 42

What if the key doesn't exist in the map? In this case, the key is created. In other words, to insert a new key, just use the subscript operator, like this:

	myMap["e"] = 50; //inserts "e" as a new key and assigns it the value 50

If you don't use the assignment operator with a new key, the key will still be inserted, but it's value will be uninitialized.

The underlying data structure in a map is an array. To access a position in an array, you use an integer. However, to access a position in a map, you use a key value, which can be any type of object. The purpose of a hash function is to convert the key value passed into the map into an integer that can be used in the underlying array. Ideally, a hash function would create a unique value for every possible key. In practice, you will usually end up with collisions (where two keys produce the same hash value), but there are several methods to deal with collisions, as seen on the main lab page. Your goal is to make the best hash function as possible, but be aware you will still have occasional collisions.

In the case of this lab, you will only be using strings as the key, so you need some way to convert a string into an integer. Without giving you the answer, consider the fact that all characters have an associated ASCII numerical value. Also, consider that "tac" and "cat" would collide if you simply add the ASCII values for your hash. Also, the formula on the main lab page under "Hashing" is a good place to start looking. (hint, hint). Good luck!

Behind the scenes, a string is actually just an array of individual chars. So, to access an individual char from the string, simply use brackets (the subscript operator). For example, to get the first character from a string, you would use the following code:

 
	string s = "Hello";
	cout << s[0] << endl; // prints out 'H'
					

So what if you need the number associated with that character? It's actually very simple to access. In C++, chars are actually just numbers already. You can add, subtract, multiply, and divide them like any other number (except they cannot get as large). If I want to add the first two characters of a string, I could do something like this:

 
	string s = "Hello";
	int x = s[0] + s[1]; // x = 173 because the ASCII value of H is 72 and the ASCII value of e is 101
					

That test case is testing to make sure you are doing your own error checking. If a Pokemon has a move that is never mapped in your map or your set, and then you use that move in a battle, you will fail the test case if you aren't checking for this. You might consider just returning an empty string in your set if there is nothing there.

Don't forget that when using a list you can't use an iterator, you need to use a const_iterator. If you were to use one of these in a for loop, it would look something like this:

for(typename list::const_iterator iter = myList.begin(); iter != myList.end(); iter++)

That is totally up to you. If you are confident your BST from the last lab has no bugs then it should be very simple to implement. If there are bugs that you don't know about, you will probably find them on the rehash test cases. If you are less confident in your BST, or you can't find the bugs that you are getting, a list is probably a better option.

Note that a list has many handy funtions that would help you implement a set, like:
.size(): Returns the size of the list.
.clear(): Clears the list.
.sort(): Puts the list in order.
.unique(): Gets rid of any duplicates in the list (note that this only works if .sort() has already been called before this.)
.push_back(): pushes back an item into the end of the list.

This is something that can be solved by remembering things that we have done in the previous labs. The reason your toString() stopped working once you had a set is because the compiler doesn't know how to output a set object.

cout << myMap[index].second; 

This works if your second is a string but if it's an object that you've written it will not compile. You will have to tell your compiler what to do if you try to use "<<" to put a Set into an output stream. **Refer to Lab 2 for a good example of this**