The goal of this assignment is to reinforce hash tables in C++. Specifically, the assignment is to implement the author's table2 using the STL list class instead of the author's list class. The table2.h and the test file testtab2.cpp will be provided for you. You do not need to implement the overloaded = function for table 2. The rest of the functions need to be implemented.
table2.h
// FILE: table2.h // TEMPLATE CLASS PROVIDED: Table // This class is a container template class for a Table of records. // The template parameter, RecordType, is the data type of the records in the // Table. It may any type with a default constructor, a copy constructor, // an assignment operator, and an integer member variable called key. // // CONSTRUCTOR for the Table template class: // Table( ) // Postcondition: The Table has been initialized as an empty Table. // // MODIFICATION MEMBER FUNCTIONS for the Table class: // void insert(const RecordType& entry) // Precondition: entry.key >= 0. Also if entry.key is not already a key in // the table, then the Table has space for another record // (i.e., size( ) < CAPACITY). // Postcondition: If the table already had a record with a key equal to // entry.key, then that record is replaced by entry. Otherwise, entry has // been added as a new record of the Table. // // void remove(int key) // Postcondition: If a record was in the Table with the specified key, then // that record has been removed; otherwise the table is unchanged. // // CONSTANT MEMBER FUNCTIONS for the Table class: // bool is_present(const Item& target) const // Postcondition: The return value is true if there is a record in the // Table with the specified key. Otherwise, the return value is false. // // void find(int key, bool& found, RecordType& result) const // Postcondition: If a record is in the Table with the specified key, then // found is true and result is set to a copy of the record with that key. // Otherwise found is false and the result contains garbage. // // size_t size( ) const // Postcondition: Return value is the total number of records in the // Table. // // VALUE SEMANTICS for the Table template class: // Assignments and the copy constructor may be used with Table objects. // // DYNAMIC MEMORY USAGE by the Table template class: // If there is insufficient dynamic memory, then the following functions // can call new_handler: the copy constructor, insert, the assignment // operator.
#ifndef TABLE2_H #define TABLE2_H #include // Provides size_t #include // Provides the STL list class
namespace main_savitch_12B
{ template class table { public: // MEMBER CONSTANT -- See Appendix E if this fails to compile. static const std::size_t TABLE_SIZE = 811; // CONSTRUCTORS AND DESTRUCTOR table( ); table(const table& source); ~table( ); // MODIFICATION MEMBER FUNCTIONS void insert(const RecordType& entry); void remove(int key); // CONSTANT MEMBER FUNCTIONS void find(int key, bool& found, RecordType& result) const; bool is_present(int key) const; std::size_t size( ) const { return total_records; } private: std::list data[TABLE_SIZE]; // std::size_t total_records; // HELPER MEMBER FUNCTION std::size_t hash(int key) const; }; }
#include "table2.template" // Include the implementation
#endif
testtab2
// FILE: table2.h // TEMPLATE CLASS PROVIDED: Table // This class is a container template class for a Table of records. // The template parameter, RecordType, is the data type of the records in the // Table. It may any type with a default constructor, a copy constructor, // an assignment operator, and an integer member variable called key. // // CONSTRUCTOR for the Table template class: // Table( ) // Postcondition: The Table has been initialized as an empty Table. // // MODIFICATION MEMBER FUNCTIONS for the Table class: // void insert(const RecordType& entry) // Precondition: entry.key >= 0. Also if entry.key is not already a key in // the table, then the Table has space for another record // (i.e., size( ) < CAPACITY). // Postcondition: If the table already had a record with a key equal to // entry.key, then that record is replaced by entry. Otherwise, entry has // been added as a new record of the Table. // // void remove(int key) // Postcondition: If a record was in the Table with the specified key, then // that record has been removed; otherwise the table is unchanged. // // CONSTANT MEMBER FUNCTIONS for the Table class: // bool is_present(const Item& target) const // Postcondition: The return value is true if there is a record in the // Table with the specified key. Otherwise, the return value is false. // // void find(int key, bool& found, RecordType& result) const // Postcondition: If a record is in the Table with the specified key, then // found is true and result is set to a copy of the record with that key. // Otherwise found is false and the result contains garbage. // // size_t size( ) const // Postcondition: Return value is the total number of records in the // Table. // // VALUE SEMANTICS for the Table template class: // Assignments and the copy constructor may be used with Table objects. // // DYNAMIC MEMORY USAGE by the Table template class: // If there is insufficient dynamic memory, then the following functions // can call new_handler: the copy constructor, insert, the assignment // operator.
#ifndef TABLE2_H #define TABLE2_H #include // Provides size_t #include // Provides the STL list class
namespace main_savitch_12B
{ template class table { public: // MEMBER CONSTANT -- See Appendix E if this fails to compile. static const std::size_t TABLE_SIZE = 811; // CONSTRUCTORS AND DESTRUCTOR table( ); table(const table& source); ~table( ); // MODIFICATION MEMBER FUNCTIONS void insert(const RecordType& entry); void remove(int key); // CONSTANT MEMBER FUNCTIONS void find(int key, bool& found, RecordType& result) const; bool is_present(int key) const; std::size_t size( ) const { return total_records; } private: std::list data[TABLE_SIZE]; // std::size_t total_records; // HELPER MEMBER FUNCTION std::size_t hash(int key) const; }; }
#include "table2.template" // Include the implementation
#endif
