C ++, как я могу реализовать хэш-набор из хеш-таблицы, используя дочерний класс шаблона шаблонного класса?

У меня есть школьное задание для реализации hash_set и hash_map, мне дали main.cpp, в котором есть код для проверки этих классов (вставки, удаления, поиска, печати и т. Д.). Мне также дали базовый класс hash_table, который является шаблонным классом, и мне просто сказали «заставить работать hash_set и hash_map на основе кода тестирования с новыми собственными классами».

Без более подробной информации, я предполагаю, что должен реализовать набор и карту на основе hash_table, который, по словам учителя, может быть завершен в 40 строках кода (ват ??) между двумя новыми классами … но я не могу даже заставить класс hash_set наследовать hash_table, так как это шаблон. Я могу получить его компиляцию нормально, не делая класс hash_set шаблоном, пока я не создам его экземпляр, так как тестовый код передает ему тип шаблона в объявлении. Но если я попытаюсь сделать класс самим типом шаблона, чтобы компенсировать это, все сломается, и я не смогу отследить источник ошибки. Я нахожусь около 8 часов в этом проекте, который предположительно должен быть 1-часовым проектом, так что я нахожусь в конце концов здесь.

Вот оригинальный main.cpp с тестовым кодом (hash_map закомментирован, потому что я еще даже не начал его: /)

//
//  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;
}

И это оригинальный файл класса hash_table:

//
//  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) */

Я знаю, что файл hash_table длинный, и у меня есть неплохое представление о том, что делать дальше, поскольку hash_set на самом деле нужно только реализовать функцию поиска во вставке, чтобы убедиться, что список уникален, но на самом деле не портит порядок хеширования. или что-то еще (я не совсем уверен, как реализовать сам хэш, но я предполагаю, что наследование будет хорошо уладить это), и hash_map разрешит нулевой ключ и любые нулевые значения …. но сначала что-то должно скомпилироваться ,

Это то, что я сейчас использую в качестве класса hash_set, просто пытаюсь получить простой конструктор, который использует конструктор родительского класса с правильным типом (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__

В настоящее время я получаю ту же ошибку: с этим точным кодом он говорит мне, что «WSUHashSet — это не шаблон», что хорошо, потому что мой класс в порядке, но плохо, потому что я не могу просто отредактировать main.cpp, чтобы не рассматривать его как шаблон.

Когда я пытаюсь сделать это шаблоном, вот так:

#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__

Мне действительно нужно какое-то направление здесь. Я не могу позволить себе тратить на это гораздо больше времени, так как это не единственный урок, и я чувствую, что это должно быть довольно просто. Теория имеет смысл, но реализация заставляет меня чувствовать, что я слепо бродил по кругу.

Спасибо

РЕДАКТИРОВАТЬ: фактическая ошибка компилятора

WSUHashSet.h строка 19: ошибка: WSUHashSet не является шаблоном

Видимо, вставка в блок кода привела к путанице. Вот фактическая строка (19 в кодовых блоках), которая нарушает компиляцию:

WSUHashSet(std::initializer_list<std::string> init) :  WSUHashTable(init)
{
insert(init);
}