UPDATED. I have previously posted this question but have reposted for quality and accuracy. Please modify the given code to meet the following specifications:

1) Augment the hash_table class with a private subclass called "key_line" which uses a string to hold a key (word) and a vector of integers to keep track of all the line numbers where the key is found in the input file. You will neither need to implement a constructor or a destructor (the defaults will do fine), but you must implement a key_line::inuse() member function that indicates whether the object holds a key or not. You will also need to overload the comparison operator, i.e., operator==(). That's it for key_line which should be based on a struct instead of a class to make it readily available to the hash_table member functions.

2) Remove all template references used by the hash_table class which should be modified to explicitly use the key_line subclass. This includes making member functions qprobe(), insert(), and resize() all use key_line::inuse() when checking to see if an entry exists.

3) Modify the hash_table::insert() function to add a key if not present in the hash table. Update each key_line object to have it maintain a sorted list of all unique line numbers for it (no That is, search the line number vector mentioned above and if not found, add the new line number at the end of the list. Use std::find() to carry out the search.

4) Add a public member function hash_table::find() that returns a constant reference to the vector of line numbers associated with the hash table entry for a given key. If the key is not found, a reference to an empty vector is returned. You deal with this in the main program.

Given Code:

#include <...> using namespace std; typedef unsigned int uint; template class hash_table { public: hash_table(); void insert(const Tkey &); private: int hash(const Tkey &); int nextprime(int); int qprobe(const Tkey &); void resize(); int num_inuse; int max_inuse; vector table; }; template hash_table::hash_table() { int N = 23; table.assign(N, Tkey()); num_inuse = 0; max_inuse = N/2; // quadratic probe max value } template void hash_table::insert(const Tkey &key) { int index = qprobe(key); if (table[index] == Tkey()) { table[index] = key; if (++num_inuse >= max_inuse) resize(); } } See previous page for hash() function template code. template int hash_table::nextprime(int N) { int i = 2; while (i*i <= N) { if (N%i == 0) { N++; i = 1; } i++; } return max(3,N); } template int hash_table::qprobe(const Tkey &key) { int index = hash(key); int k = 0; while (table[index] != Tkey() && table[index] != key) { index += 2*(++k) - 1; index = index % table.size(); } return index; } template void hash_table::resize() { vector tmp_table; for (int i=0; i<(int)table.size(); i++) { if (table[i] != Tkey()) tmp_table.push_back(table[i]); } int N = nextprime(2*table.size()); table.assign(N, Tkey()); num_inuse = 0; max_inuse = N/2; for (int i=0; i<(int)tmp_table.size(); i++) { Tkey &key = tmp_table[i]; table[ qprobe(key) ] = key; num_inuse++; } }