The file sets has a slew of keys each on their own line. The file results has unique words and the frequency space separated.

Project 2: DIY STL

For this task you will be making 12 different implementations of the classic "associative" containers. (An invitation to explore good software engineering and project management.)

Specifically I want you to implement the following 4 abstract data types in 3 ways each:

You should implement the ADT/API of those 4, 3 separate times with a different data structure under the hood each time:

Do some timing on your code and report on which data structure performed the best for each ADT.

Just to be extremely clear, you will implement:

Details of the APIs

For this project we will allow unordered keys. In no case will we require an ordering of the keys.


The abstract data type (ADT) Set is the CS equivalent of a mathematical set.

It allows you to add keys (but not values), test for inclusion of a key, remove a key, and test for an empty set.

For the sake of your sanity I'll let you limit your keys to strings (as opposed to generic templates).

To summarize you need to provide the following methods:

Extra Credit: Write a Set Set::Union(Set other_set) function and a Set Set::Intersection(Set other_set) function.

MultiSet (Bag)

A multiset is just like a set, but you can add the same key many times. In this case we add one feature count(key) to return the number of times key appears in our "Bag".

To summarize you need to provide the following methods:

Extra Credit: implement a string MSet::draw_random(), so you can Monte Carlo simulate those math problems about bags with red and blue marbles.

Map (Dictionary)

This is my favorite ADT. A map is the typical key/value pair storage device (I've given you a sample associative array in the notes). In this case we will save values under a key, then retrieve a value by referencing the key.

For your sanity you can make all keys strings and all values ints.

The functions you should implement:


The MultiMap acts just like the Map but allows inserting many values for each key. So you can have many values saved under the same key.

The functions you should implement:

Extra Credit: A feature which I want but is too subtle is removing a single key/value pair. To do this you would need some sort of iterator and the ability to delete the key/value pair at a location. (See the STL erase example.)


You have the freedom to implement more than I've asked for. For instance overriding << or creating any other features you would like. In your presentation state the additional features you are most proud of so we know and appreciate your work.

Extra Resources