Counter

In this lab, you'll implement the map abstract data type. This map uses strings as keys and integers as values, and supports fast lookup and

update by key. This makes it perfect for a very common programming task: counting things.

This map also supports iterators, and iterating over the map should visit the keys in insertion order. The first key added to the map will be

the first key visited, the second the second, and so on until reaching the most recently added key at the very end of the iteration. This is a

convenient feature, and lots of languages support it: Ruby's default map type works like this, for example, and Python provides the

OrderedDict type.

Unlike maps that are ordered by key, these maps have an average $O(1)$ runtime for all of their functions. They achieve this by storing their

key$-$value pairs in a doubly$-$linked list, and then using a hash table as an index into that list. The linked list keeps the values in order, and the

hash table lets you jump to any list node in constant time.

The full implementation can be a bit complicated, so I recommend using only the linked list at first, then adding the hash table later. See the

Implementation Guide section for more details.