Synopsis

• Read the lab writeup on Instructure Canvas.
• There are two parts to this lab.
• The lab is due on December 1, 2020 at 23:59:59.

Requirements

• Basic knowledge of std::map. I cover this down below if you aren't aware of how they work.

Side Files

Usually, for lab "lectures", I prepare a digital copy of my notes to write on the whiteboard. I have made these public:

• 2020-11-18 - Score Database.pdf - Everything you need. Details on lab assignment. How to submit. Diagrams. Various examples.
  
  

Now for some fun. You know how BSTs (Binary Search Trees) work, and you have implemented them. So now you get to use a built-in data structure which implements these really efficiently. This is my favourite data structure because of the sheer amount of flexibility it gives.

Introducing the std::map. This is a BST/Associative Array-like structure (usually) implemented via Red-Black Trees. You don't have to know how those work, and you will never implement them (I did in C... and it was painful). Just know that they have the same properties you are used to (sorting, etc), but they are also balanced to guarantee a O(lg N) time complexity for insertions, deletions, and searching every time.

Map properties

They have the following properties:

• Stores Key/Value pairs.
• Templated. Allows for custom key and value types.
• As it's a BST, it's always sorted by key.
  • key type requires an operator< overload to work.
• Keys are unique. No duplicates are allowed. (If you want that, look into multimap).
• Unique find() function to perform a binary tree traversal to find a key in O(lg N) time. This is way faster than std::find()'s O(N) time.

Example 1: Basic Insertion

Let's start easy. This is a deceivingly easy example that should give you an idea of what we can do. But take it with caution and read on after. Let's insert a pair in and print it out. Behold the following C++ program:

//C++ Includes
#include <iostream>
#include <string>
#include <map>

using namespace std;

int main() {
	//Declare map where data stored inside are string/int pairs.
	map<string, int> m;

	//Insert "test"/2 pair.
	m["test"] = 2;

	//Get the value out by looking up the key.
	cout << m["test"] << endl;
}

Running this gives the following output:

2

Get the idea? All it's doing is storing a value in the map, and we can reference this value by looking up its key.

Example 2: Iteration

Now let's insert some more elements and print all of them out in sorted order. We'll need an iterator for this. Remember, BSTs are sorted. So simply iterating through and printing out the values is good enough to get the sorted values.

Iterators in STL usually are universal in syntax. However, because maps have a key and a value, their iterators hold two values, not one. Assuming you name the iterator it, you may access these via:

• it->first - Gives the key
• it->second - Gives the value

With this in mind, let's give it a spin.

//C++ Includes
#include <iostream>
#include <string>
#include <map>

using namespace std;

int main() {
	//Declare map where data stored inside are string/int pairs.
	map<string, int> m;
	map<string, int>::iterator it;

	//Insert some data.
	m["test"   ] = 1;
	m["hello"  ] = 2;
	m["clara"  ] = 3;
	m["cs140"  ] = 4;
	m["is cool"] = 5;

	//Lexicographical Printing of Key/Value pairs
	for (it = m.begin(); it != m.end(); it++)
		cout << it->first << ": " << it->second << endl;
}

Running this gives the following output:

clara: 3
cs140: 4
hello: 2
is cool: 5
test: 1

Have you notice? The keys are printed out in sorted order, just as expected.

Examples 3 & 4: operator[] flaw

So, don't get used to inserting via operator[]. I showed that intentionally for the sake of an easy example. It's actually fine to insert via it. But using it to find is the issue. Let's take a look at what happens if we try to access an invalid key... Will it crash?

//C++ Includes
#include <iostream>
#include <string>
#include <map>

using namespace std;

int main() {
	//Declare map where data stored inside are string/int pairs.
	map<string, int> m;

	//Get the value out by looking up non-existant key.
	cout << m["cs140"] << endl;
}

Running this gives the following output:

0

So what happened? Why is it printing out 0? Well, map's operator[] will try to find the key/value pair. But, if it is unable to do so, it will just insert it into the tree with the default value of value (int() = 0). So if you fail to find a value, you'll end up inserting on accident.

Obviously, this is bad, as you'll have occasions where you'll print the entire map out, and see bad values in. Here's an example of that:

//C++ Includes
#include <iostream>
#include <string>
#include <map>

using namespace std;

int main() {
	//Declare map where data stored inside are string/int pairs.
	map<string, int> m;
	map<string, int>::iterator it;

	//Insert some data.
	m["test"   ] = 1;
	m["hello"  ] = 2;
	m["clara"  ] = 3;
	m["cs140"  ] = 4;
	m["is cool"] = 5;

	//Stupidly insert something bad
	if (m["bad"] == 2) {
		cout << "This will never happen" << endl;
	}

	if (m["worse"] == 0) {
		cout << "Hi. You've coded something horrible." << endl;
	}

	//Lexicographical Printing of Key/Value pairs
	for (it = m.begin(); it != m.end(); it++)
		cout << it->first << ": " << it->second << endl;
}

Running this gives the following output:

Hi. You've coded something horrible.
bad: 0
clara: 3
cs140: 4
hello: 2
is cool: 5
test: 1
worse: 0

Realistically, I don't think anyone would use maps like this. But there's three bad things going on here:

• m["bad"] was inserted when trying to compare with 2. This if-statement failed, because the default value of 0 was returned instead.
• m["worse"] was inserted when trying to compare with 0. This if-statement worked, because the default value of 0 was returned instead.
• When iterating through the map m, those "accidental" insertions are printed as well, as they were inserted into the map during those if-statement calls.

Example 5: Proper Insertion

There's four ways I can think of to insert pairs into a map. Here they are:

//C++ Includes
#include <iostream>
#include <string>
#include <map>

using namespace std;

int main() {
	//Declare map where data stored inside are string/int pairs.
	map<string, int> m;
	map<string, int>::iterator it;

	//Method 1: operator[]
	m["test"] = 1;

	//Method 2: make_pair<...> (Manual Template Specification)
	m.insert(make_pair<string, int>("hello", 2));

	//Method 3: make_pair (Let compiler guess template parameters)
	m.insert(make_pair("clara", 3));

	//Method 4: pair<...> (Call upon std::pair, template req.)
	m.insert(pair<string, int>("cs140", 4));

	//Lexicographical Printing of Key/Value pairs
	for (it = m.begin(); it != m.end(); it++)
		cout << it->first << ": " << it->second << endl;
}

Running this gives the following output:

clara: 3
cs140: 4
hello: 2
test: 1

For this lab, I don't care what method you use as long as it works. When I code, I prefer to explicitly tell the compiler what I want, rather than having it guess. So you'll frequently see me using method 2.

Example 6: Finding if value exists in map

So, using map.operator[] is out of the question for finding if a key is in the map, since it'll insert automatically. This is where we can utilise map.find() (documentation). It works exactly like how you think. It'll start at the root of the BST, and traverse down exactly O(lg n) times until it hits the value we want, and return an iterator to it.

"Right Clara... and what if the key doesn't exist?"

Simple. It returns map.end(). Please do not associate this with NULL. It's implementation-defined (may be different depending on what computer you're on). If you are checking if a key exists, check it with map.end().

Of course, #TeachBySledgehammer. Here's an example:

//C++ Includes
#include <iostream>
#include <string>
#include <map>

using namespace std;

void find_key(map<string, int> &m, const string &key) {
	map<string, int>::iterator it;

	cout << "find(" << key << ")... ";

	it = m.find(key);

	if (it == m.end())
		cout << "not found" << endl;
	else
		cout << "found. value: " << it->second << endl;
}

int main() {
	//Declare map where data stored inside are string/int pairs.
	map<string, int> m;

	//Insert some pair
	m.insert(make_pair<string, int>("test", 1));

	//Search for key that obviously doesn't exist...
	find_key(m, "cs140");

	//Search for key that obviously does exist...
	find_key(m, "test");
}

Running this gives the following output:

find(cs140)... not found
find(test)... found. value: 1

Obviously, you can skip the iterator definition and just do if (m.find(key) == m.end()) as well. Though, you'd have no way of retrieving the value if you needed it.

Example 7: Class as key

Recall that this is a templated data structure. It can take any type thrown into it. However, if you wish to use a class as a key, you must overload operator<. Furthermore, it must be a const function, as keys inserted into maps are read only. They can't be changed. Values can.

Once again, #TeachBySledgehammer. Here's a simple class that stores an integer. We'll use that as a key for a map. Behold:

//C++ Includes
#include <iostream>
#include <string>
#include <map>

using namespace std;

// Class Prototype
class int_key {
	public:
		int_key(int = 0);

		bool operator<(const int_key &) const;

		const int &get_key() const;

	private:
		int key;
};

//Constructor
int_key::int_key(int v) {
	key = v;
}

//Operator Overload (operator<)
bool int_key::operator<(const int_key &rhs) const {
	return key < rhs.key;
}

//Getter
const int &int_key::get_key() const {
	return key;
}

int main() {
	//Declare map where data stored inside are int_key/double pairs.
	map<int_key, double> m;
	map<int_key, double>::iterator it;

	//Objects to insert into the tree (containing 16 and 9 respectively)
	int_key obj_a(16), obj_b(9);

	//Perform insertion
	m.insert(make_pair( obj_a, 0.123 ));
	m.insert(make_pair( obj_b, 0.456 ));

	//Print out everything
	for (it = m.begin(); it != m.end(); it++)
		cout << it->first.get_key() << ": " << it->second << endl;
}

Running this gives the following output:

9: 0.456
16: 0.123

By the way, if you're using C++11 or newer, my method 2 preference (make_pair<int_key, double>(...)) will fail to compile here. It requires make_pair<int_key &, double>(...) instead. This change makes it not compile on C++98. Fun! At that point, as shown above, just use make_pair(...) and let the compiler figure it out. Since we allow both C++98 and C++11, if there is an issue here and the TAs see it, they will not deduct for it. And if they do, let me know.

"But Clara! Why is only operator< needed and not > or ==?"

Less code for you to write. You can get the other operators from operator<. Here's how:

• operator<: A < B
• operator>: B < A
• operator==: !(A < B) && !(B < A)
• operator!=: (A < B) || (B < A)
• operator<=: !(B < A)
• operator>=: !(A < B)

The developers of std::map take advantage of this to get every other operator that they need out of operator<. It's quite elegant, honestly. In C++20, this is taken a step further, as you can generate all 6 operators via <=> (Spaceship Operator / 3-way comparison). That's way out of the scope of this lab though. Just implement operator<.

I hope this little introduction to maps helps. You'll need it for your lab assignment. ;)

We will be following these guidelines.

Submission

You know the drill by now. Submit a TAR file containing Rank_byname.cpp and Rank_byscores.cpp. You can make this by running the following command:

UNIX> tar -cvf lab8.tar Rank_byname.cpp Rank_byscores.cpp