I have a school assignment to implement a hash_set and a hash_map, I am given a main.cpp that has code to test these classes (inserts, deletes, searches, prints, etc). I am also given a base hash_table class that is a templated class, and just told to "make the hash_set and hash_map work based on the testing code with new classes of their own".
Without more specific details, I assume I am supposed to implement the set and map based on the hash_table, which the teacher said the project could be completed in 40 lines of code (wat??) between the two new classes...but I can't even get the hash_set class to inherit the hash_table since it's a template. I can get it compiling ok without making the hash_set class a template, until I instantiate it, since the testing code is passing it a template type in the declaration. But if I try to make the class a template type itself to compensate for this, everything breaks and I can't track down the source of the error. I'm about 8 hours into this project which should supposedly be a 1 hour project, so I'm at wits end here.
Here is the original main.cpp with the testing code (hash_map is commented out because I haven't even started that yet :/ )
//
// main.cpp
// CS3100Project05_HashCollections
#include "WSUHashTable.h"
//#include "WSUHashMap.h" // Uncomment to test WSUHashMap
#include "WSUHashSet.h" // Uncomment to test WSUHashSet
#include <iostream>
int main(int argc, const char * argv[])
{
///////////////////////////////////////////////////////////////////
/// Part 1 :TEST HASH TABLE ///
///////////////////////////////////////////////////////////////////
{
WSUHashTable<int> example = {1, 2, 3, 4, 1};
std::cout << "Part 1a: Expected output is in any order " <<
"\"1 2 3 4\"\n";
for(int n : example)
{
std::cout << n << ' ';
}
std::cout << std::endl;
std::cout << std::endl;
std::cout << "Part 1b: Expected output is \"Found 2\"\n";
{
auto search = example.find(2);
if(search != example.end())
{
std::cout << "Found " << (*search) << '\n';
}
else
{
std::cout << "Not found\n";
}
}
std::cout << std::endl;
std::cout << "Part 1c: Expected output is \"Not found\"\n";
example.erase(2);
{
auto search = example.find(2);
if(search != example.end()) {
std::cout << "Found " << (*search) << '\n';
}
else {
std::cout << "Not found\n";
}
}
std::cout << std::endl;
}
///////////////////////////////////////////////////////////////////
/// Part 2: TEST HASH SET ///
///////////////////////////////////////////////////////////////////
/***** Uncomment to test WSUHashSet */
{
WSUHashSet<std::string> stringSet = {"1", "2", "3", "4"};
std::cout << "Part 2a: Expected output is \"Found \"2\"\"\n";
{ // Test find() that succeeds
auto search = stringSet.find("2");
if(search != stringSet.end()) {
std::cout << "Found \"" << (*search) << "\"\n";
}
else {
std::cout << "Not found\n";
}
}
std::cout << std::endl;
std::cout << "Part 2b: Expected output is \"Not found\"\n";
stringSet.erase("2");
{ // Test find() that fails
auto search = stringSet.find("2");
if(search != stringSet.end())
{
std::cout << "Found \"" << (*search) << "\"\n";
}
else
{
std::cout << "Not found\n";
}
}
std::cout << std::endl;
WSUHashSet<double> doubleSet = {
1.1, 2.2, 3.2, 4.4, 5.5, 6.1, 7.2, 8.4, 9.9
};
std::cout << "Part 2c: Expected output is in any order " <<
"\"5.5 7.2 8.4 9.9 1.1 2.2 3.2 4.4 6.1\"\n";
for(auto n : doubleSet )
{ // Test using implicit iterators
std::cout << n << ' ';
}
std::cout << std::endl;
std::cout << std::endl;
std::cout << "Part 2d: Expected output is in any order " <<
"\"5.5 7.2 8.4 9.9 4.4 6.1\"\n";
// Part 7: Using explicit iterators while mutating set
for(auto it = doubleSet.begin(); it != doubleSet.end(); )
{ // erase every number less than 4.0
if(*it < 4.0)
{
it = doubleSet.erase(it);
}
else
{
++it;
}
}
for(auto n : doubleSet)
{
std::cout << n << ' ';
}
std::cout << std::endl;
std::cout << std::endl;
}
///////////////////////////////////////////////////////////////////
/// Part 3: TEST HASH MAP ///
///////////////////////////////////////////////////////////////////
/***** Uncomment to test WSUHashMap *
{
WSUHashMap<int, std::string> dict = {{1, "one"}, {2, "two"}};
dict.insert({3, "three"});
dict.insert(std::make_pair(4, "four"));
dict.insert({{4, "another four"}, {5, "five"}});
std::cout << "Part 3a: Expected output is " <<
"\"inserting 1 -> \"another one\" failed\"\n";
bool ok = dict.insert({1, "another one"}).second;
std::cout << "inserting 1 -> \"another one\" "
<< (ok ? "succeeded" : "failed") << '\n';
std::cout << std::endl;
std::cout << "Part 3b: Expected output is " <<
"\"contents: " <<
"1 => one " <<
"2 => two " <<
"3 => three " <<
"4 => four " <<
"5 => five\"\n";
std::cout << "contents: ";
for(auto& p : dict)
{
std::cout << " " << p.first << " => " << p.second << ' ';
}
std::cout << std::endl;
}
*****/
return 0;
}
And this is the original hash_table class file:
//
// WSUHashTable.h
// CS3100Project05_HashCollections
#ifndef __CS3100Project05_HashCollections__WSUHashTable_H
#define __CS3100Project05_HashCollections__WSUHashTable_H
#include <vector>
#include <utility>
#include <algorithm>
#include <iterator>
#include <cassert>
//////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////
template <
typename elementT,
typename Hash = std::hash<elementT>
>
class WSUHashTable
{
private:
///////////////////////////////////////////////////////////////////
typedef elementT bucket_t;
///////////////////////////////////////////////////////////////////
static const std::size_t initialCapacity = (1 << 2);
constexpr static float maxLoadFactor = 0.73f;
///////////////////////////////////////////////////////////////////
std::size_t mSize; // Number of elements in table
std::vector<bucket_t> mStorage; // Storage for elements
std::vector<bool> mIsValidFlags;
public:
///////////////////////////////////////////////////////////////////
class iterator : public std::iterator<
std::input_iterator_tag, elementT>
{
friend class WSUHashTable<elementT, Hash>;
const WSUHashTable<elementT, Hash> *mHashTablePtr;
std::size_t mIndex;
////////////////////////////////////////////////////////////////
iterator(
const WSUHashTable<elementT, Hash> &hashTable,
std::size_t index = 0
) :
mHashTablePtr(&hashTable),
mIndex(index)
{
}
////////////////////////////////////////////////////////////////
std::size_t getIndex() const
{
return mIndex;
}
public:
////////////////////////////////////////////////////////////////
iterator(const iterator &other) :
mHashTablePtr(other.mHashTablePtr),
mIndex(other.mIndex)
{
}
////////////////////////////////////////////////////////////////
iterator& operator++()
{
++mIndex;
while(mIndex < mHashTablePtr->mIsValidFlags.size() &&
!mHashTablePtr->mIsValidFlags[mIndex])
{ // Skip over empty buckets
++mIndex;
}
return *this;
}
////////////////////////////////////////////////////////////////
iterator operator++(int)
{
const_iterator tmp(*this);
operator++();
return tmp;
}
////////////////////////////////////////////////////////////////
bool operator==(const iterator& rhs)
{
return mIndex == rhs.mIndex;
}
////////////////////////////////////////////////////////////////
bool operator!=(const iterator& rhs)
{
return mIndex != rhs.mIndex;
}
////////////////////////////////////////////////////////////////
const elementT &operator*()
{
return mHashTablePtr->mStorage[mIndex];
}
};
///////////////////////////////////////////////////////////////////
typedef const iterator const_iterator;
private:
typedef std::pair<const_iterator, bool> _findResult;
///////////////////////////////////////////////////////////////////
std::size_t _calculatedIndex(const elementT &element) const
{
return (Hash()(element) % mStorage.size());
}
///////////////////////////////////////////////////////////////////
// Returns a pair containing iterator to bucket where element
// should be and flag indicating whether it is there.
_findResult _find( const elementT &element ) const
{
std::size_t index = _calculatedIndex(element);
while(mIsValidFlags[index] &&
((mStorage[index] < element) || (element < mStorage[index])))
{ // Loop until element is found or an empty bucket is found
++index;
index %= mStorage.size();
}
return _findResult(
const_iterator(*this, index), mIsValidFlags[index]);
}
///////////////////////////////////////////////////////////////////
void _doubleCapacityAndRehash()
{
const std::size_t oldSize = mIsValidFlags.size();
// Save off mStorage by moving contents instead of copying
std::vector<bucket_t> oldStorage = std::move(mStorage);
std::vector<bool> oldIsValidFlags = std::move(mIsValidFlags);
// Replace mStorage and mIsValidFlags with empty storage with
// twice the size/capacity.
mStorage = std::move(std::vector<bucket_t>(oldSize * 2));
mIsValidFlags = std::move(std::vector<bool>(oldSize * 2));
// We are going to re-insert everything, so strat with size 0
mSize = 0;
for(std::size_t i = 0; i < oldSize; ++i)
{ // Insert values from all valid buckets in old storage
if(oldIsValidFlags[i])
{
insert(oldStorage[i]);
}
}
}
public:
///////////////////////////////////////////////////////////////////
WSUHashTable() :
mSize(0),
mStorage(initialCapacity),
mIsValidFlags(initialCapacity)
{
}
///////////////////////////////////////////////////////////////////
WSUHashTable(const WSUHashTable &other) :
mSize(other.mSize),
mStorage(other.mStorage),
mIsValidFlags(other.mIsValidFlags)
{
}
///////////////////////////////////////////////////////////////////
template< class InputIt >
WSUHashTable(InputIt first, InputIt last) :
mSize(0),
mStorage(initialCapacity),
mIsValidFlags(initialCapacity)
{
while(first != last)
{
insert(*first);
++first;
}
}
///////////////////////////////////////////////////////////////////
WSUHashTable(std::initializer_list<elementT> init) :
mSize(0),
mStorage(initialCapacity),
mIsValidFlags(initialCapacity)
{
insert(init);
}
///////////////////////////////////////////////////////////////////
std::size_t size() const
{
return mSize;
}
///////////////////////////////////////////////////////////////////
/// Inserts element(s) into the container, if the container doesn't
/// already contain an an equivalent element.
/// Returns a pair consisting of an iterator to the inserted
/// element (or to the element that prevented the insertion) and a
/// bool denoting whether the insertion took place.
std::pair<const_iterator, bool> insert( const elementT &element )
{
if(mSize > (maxLoadFactor * mStorage.size()))
{ // resize to make room for insertion
_doubleCapacityAndRehash();
}
_findResult result = _find(element);
if(result.second)
{ // element is present
return std::pair<const_iterator, bool>(result.first, false);
}
const std::size_t index = result.first.getIndex();
mStorage[index] = element;
mIsValidFlags[index] = true;
++mSize;
return std::pair<const_iterator, bool>(result.first, true);
}
///////////////////////////////////////////////////////////////////
/// Inserts element(s) into the container, if the container doesn't
/// already contain an an equivalent element.
/// Returns a pair consisting of an iterator to the inserted
/// element (or to the element that prevented the insertion) and a
/// bool denoting whether the insertion took place.
///
/// An && argumnet signals an "emplace" operation in C++11. The
/// value will be moved via std::move() instead of copied.
std::pair<const_iterator, bool> insert( elementT &&element )
{
if(mSize > (maxLoadFactor * mStorage.size()))
{ // resize to make room for insertion
_doubleCapacityAndRehash();
}
_findResult result = _find(element);
if(result.second)
{ // element is present
return std::pair<const_iterator, bool>(
result.first, false);
}
const std::size_t index = result.first.getIndex();
mStorage[index] = std::move(element);
mIsValidFlags[index] = true;
++mSize;
return std::pair<const_iterator, bool>(result.first, true);
}
///////////////////////////////////////////////////////////////////
void insert( std::initializer_list<elementT> ilist )
{
for(const elementT &element : ilist)
{
insert(element);
}
}
///////////////////////////////////////////////////////////////////
/// Returns iterator following the last removed element.
const_iterator erase( const_iterator pos )
{
const std::size_t index = pos.getIndex();
if(mIsValidFlags[index])
{ // element is present
mIsValidFlags[index] = false;
--mSize;
}
return ++iterator(pos);
}
///////////////////////////////////////////////////////////////////
// Returns the number of elements erased (it will be zero or one).
std::size_t erase(const elementT &element)
{
_findResult result = _find(element);
if(result.second)
{ // element is present
mIsValidFlags[result.first.getIndex()] = false;
--mSize;
return 1;
}
return 0;
}
///////////////////////////////////////////////////////////////////
const_iterator find( const elementT &element ) const
{
_findResult result = _find(element);
if(result.second)
{ // element was found
return result.first;
}
return end();
}
///////////////////////////////////////////////////////////////////
const_iterator begin() const
{
std::size_t index = 0;
while(index < mIsValidFlags.size() && !mIsValidFlags[index])
{ // Skip over empty buckets
++index;
}
return const_iterator(*this, index);
}
///////////////////////////////////////////////////////////////////
const_iterator end() const
{
return const_iterator(*this, mStorage.size());
}
};
#endif /* defined(__CS3100Project05_HashCollections__WSUHashTable_H) */
I know the hash_table file is long, and I have a decent idea on how to proceed, since a hash_set really only needs to implement a search function within the insert to make sure the list is unique, but doesn't really mess with hash order or anything (I'm not really sure how to implement the hash itself, but I assume the inheritance will sort that out nicely), and the hash_map will allow a null key and any null values....but first something has to compile.
This is what I have currently as my hash_set class, just trying to get a simple constructor that uses the parent class's constructor with the correct type (std::string):
#ifndef __WSUHashSet__
#define __WSUHashSet__
#include <vector>
#include <utility>
#include <algorithm>
#include <iterator>
#include "WSUHashTable.h"
/*template<
typename elementT,
typename Hash = std::hash<elementT>
>*/
class WSUHashSet : public WSUHashTable<std::string> {
private:
public:
WSUHashSet(std::initializer_list<std::string> init) : WSUHashTable(init)
{
insert(init);
}
};
#endif //__WSUHashSet__
Currently I get the same error: with this exact code it tells me that "WSUHashSet is not a template", which is good because my class is fine, but bad because I can't just edit the main.cpp to not treat it as a template.
When I try to make it a template, like this:
#ifndef __WSUHashSet__
#define __WSUHashSet__
#include <vector>
#include <utility>
#include <algorithm>
#include <iterator>
#include "WSUHashTable.h"
template<
typename elementT,
typename Hash = std::hash<elementT>
>
class WSUHashSet<elementT> : public WSUHashTable<std::string> {
private:
public:
WSUHashSet<elementT>::WSUHashSet(std::initializer_list<std::string> init) : WSUHashTable(init)
{
insert(init);
}
};
#endif //__WSUHashSet__
I really need some direction here. I can't afford to spend a lot more time on this as it's not my only class, and I feel like this should be fairly simple. The theory makes sense, but the implementation makes me feel like I'm blindly wandering in circles.
Thanks
EDIT: the actual compliler error is
WSUHashSet.h line 19: error: WSUHashSet is not a template
Apparently the pasting into the code block here caused confusion. Here's the actual line (19 in codeblocks) that is breaking the compilation:
WSUHashSet(std::initializer_list<std::string> init) : WSUHashTable(init)
{
insert(init);
}
