This assignment will give you practice with the built-in Standard Template Library (STL) vector, linked list, and map (hash table) by comparing their performances. Your program will read a text file and build three concordances, one with a sorted vector, one a sorted linked list, and one with a map.
A concordance is an alphabetical list of words from a document and their frequencies. Your input data will be a text file of the U.S. constitution and its amendments: http://www.cs.sjsu.edu/~mak/CMPE180A/assignments/11/USConstitution.txt This file is already uploaded to CodeCheck.
Your program should read each word of the text. If the word is not already in the concordances, enter the word with an initial count of 1 into both the vector, list, and map versions. If the word already exists in the concordance, increment the word's count by one in each concordance. The words in the concordance must be unique, and, of course, all three versions must end up with the same words and counts. Word comparisons should not be case-sensitive. Do not include numbers or punctuation marks.
Your program should keep track of how much time it takes to enter all the words into each concordance. For each word, compute the elapsed time only of the operation of either entering a new word into the concordance or incrementing the count of an existing word. Do not include the time to read the word from the input text file. Compare the total insertion times for the vector vs. the list vs. the map. The timings should be in microseconds (ms).
After building the three concordances, your program should compare the total time it takes to do 10,000 random word searches in each concordance. Since the vector-based concordance will be sorted, use a binary search.
Your program should use a list of words, both in and not in the concordance, to make (untimed) spot checks of the completed concordances to make sure they all agree on the frequency counts of those words.
Use iterators to iterate over the completed vector, list, and the map versions of the concordance in parallel to ensure that they contain the same data (words and counts) in the same order. Note that the elements of an STL map are always sorted by their keys.