c++ - HashTable... 错误:静态断言失败:std::hash 不专门用于此类型

Question

我今天早些时候发帖并且能够解决我的很多错误。但是，我仍然有一个错误，我终生无法弄清楚。我基本上只是试图将一个 Symbol 对象插入到一个 HashTable 中，并且我不断地收到这条消息:

In file included from /opt/local/include/gcc47/c++/bits/basic_string.h:3032:0,
                     from /opt/local/include/gcc47/c++/string:54,
                     from /opt/local/include/gcc47/c++/bits/locale_classes.h:42,
                     from /opt/local/include/gcc47/c++/bits/ios_base.h:43,
                     from /opt/local/include/gcc47/c++/ios:43,
                     from /opt/local/include/gcc47/c++/ostream:40,
                     from /opt/local/include/gcc47/c++/iostream:40,
                     from Driver.cpp:1:
    /opt/local/include/gcc47/c++/bits/functional_hash.h: In instantiation of 'struct std::hash<Symbol>':
    SeparateChaining.h:143:33:   required from 'size_t HashTable<HashedObj>::myhash(const HashedObj&) const [with HashedObj = Symbol; size_t = long unsigned int]'
    SeparateChaining.h:56:51:   required from 'bool HashTable<HashedObj>::insert(HashedObj&) [with HashedObj = Symbol]'
    Driver.cpp:135:26:   required from here
    /opt/local/include/gcc47/c++/bits/functional_hash.h:60:7: error: static assertion failed: std::hash is not specialized for this type

更具体地说……错误:

error: static assertion failed: std::hash is not specialized for this type

这是我的 Driver.cpp 文件:

#include <iostream>
#include <iomanip>
#include <cassert>
#include <fstream>
#include <string>
#include <vector>
#include <time.h>
#include <unistd.h>
#include <map>
#include <cstdlib>
#include <cmath>
#include "SeparateChaining.h"

using namespace std;

int TABLE_SIZE; //I know it's a global, but it allows the Table Size to be taken in within main() and used in hash()

size_t hash(const string & key);

class Symbol
{
private:
    int key;
    int type;
    string data;
public:
    const string & getData() const
    {
        return data;
    }
    int getType() 
    {
        return type;
    }
    int getKey()
    {
        return labs(key);
    }
    void setType(int Type)
    {   
        type = Type;
    }
    void setData(string Data)
    {
        data = Data;
    }
    void setKey(int Key)
    {
        key = Key;
    }
    bool operator== (const Symbol & rhs) const
    {
        return getData() == rhs.getData();
    }

    bool operator!= (const Symbol & rhs) const
    {
        return !(*this == rhs);
    }
};


int main()
{
    HashTable<Symbol> hashtable(TABLE_SIZE);
    Symbol temp;
    vector<Symbol> symbols;
    string s;
    int t;
    int hash_key_array[TABLE_SIZE]; //array to hold hash key values

    ifstream file;
    file.open("symbols.txt");

    if(!file)
    {
        cout << "System failed to open file.";
    }
    else
    {
        cout << "File successfully opened" << endl;
    }

    //for loop to read in the string name and the integer that follows the string name from symbols.txt
    while(file >> s)
    {
        temp.setData(s);
        file >> t;
        temp.setType(t);
        symbols.push_back(temp);
    }

    for(int i = 0; i < symbols.size(); i++)
    {
        cout << symbols[i].getData() << "\n";
        cout << symbols[i].getType() << "\n";
    }

    cout << "What would you like the table size to be?" << endl;
    cout << "Note: If the table size is greater than the number of objects" <<
    " in the symbols.txt file, it will inevitably throw a segmentation fault" << endl;
    cin >> TABLE_SIZE;

    for(int j = 0; j < TABLE_SIZE; j++)
    {
        temp.setData(symbols[j].getData());
        cout << temp.getData() << endl;

        temp.setType(symbols[j].getType());
        cout << temp.getType() << endl;

        temp.setKey(::hash(symbols[j].getData()));
        cout << "The key is: " << temp.getKey() << endl;

        cout << endl;

        hash_key_array[j] = temp.getKey();


        for (int i = 0; i < TABLE_SIZE; i++)
        {
            if (i != j)
            {
                if (hash_key_array[i] == hash_key_array[j])
                {
                    cout << endl;
                    cout << "Collision occurred at " << hash_key_array[i] << endl;
                    //rehash();
                    //cout << "The new key is: " << temp.getKey() << endl;
                    break;
                }
            }
        }

    hashtable.insert(temp);


    }
}

size_t hash(const string & key)
{
    size_t hashVal = 0;

    for(char ch : key)
    {
        hashVal = 37 * hashVal + ch;
    }
    return labs(hashVal);
}

还有我的头文件.... SeperateChaining.h:

#ifndef SEPARATE_CHAINING_H
#define SEPARATE_CHAINING_H

#include <vector>
#include <list>
#include <string>
#include <algorithm>
#include <functional>
//#include "Hash.h"
using namespace std;

// SeparateChaining Hash table class
//
// CONSTRUCTION: an approximate initial size or default of 101
//
// ******************PUBLIC OPERATIONS*********************
// bool insert( x )       --> Insert x
// bool remove( x )       --> Remove x
// bool contains( x )     --> Return true if x is present
// void makeEmpty( )      --> Remove all items
int nextPrime( int n );
bool isPrime( int n );


template <typename HashedObj>
class HashTable
{
  public:

    //Uses the whatever value table_size has
    //Otherwise, it will make a hash table of size 101
    explicit HashTable( int TABLE_SIZE )
    { 
        currentSize = 0;
        theLists.resize(TABLE_SIZE); 
    }

    bool contains( const HashedObj & x ) const
    {
        //represents the correct list in the hash table vector to start looking through
        auto & whichList = theLists[ myhash( x ) ];

        //returns whatever you wanted to search for in the table provided it is there
        return find( begin( whichList ), end( whichList ), x ) != end( whichList );
    }

    void makeEmpty( )
    {
        for( auto & thisList : theLists )
            thisList.clear( );
    }

    bool insert(HashedObj & temp )
    {
         //represents the correct list in the hash table vector to start looking through
        auto & whichList = theLists[myhash( temp )];

        //goes through the beginning and end of the list, and if it
        //doesn't get to the end, then it found the object you wanted to insert in the hash table already
        //prevents duplicate insertions
        if( find( begin( whichList ), end( whichList ), temp ) != end( whichList) )
            return false;

        //otherwise, it has gotten to the end of the list without finding a duplicate
        //and puts what you want to insert in the list
        whichList.push_back( temp );

        // Rehash; see Section 5.5
        if( ++currentSize > theLists.size( ) )
            rehash( );

        return true;
    }

    bool insert(const HashedObj && x )
    {
        auto & whichList = theLists[ myhash( x ) ];      
        if( find( begin( whichList ), end( whichList ), x ) != end( whichList ) )
            return false;
        whichList.push_back( std::move( x ) );

            // Rehash; see Section 5.5
        if( ++currentSize > theLists.size( ) )
            rehash( );

        return true;
    }

    bool remove( const HashedObj & x )
    {
        //represents the correct list in the hash table vector to start looking through
        auto & whichList = theLists[ myhash( x ) ];

        //trying to find x within the list
        //the iterator points to the slot in the list that contains x
        auto itr = find( begin( whichList ), end( whichList ), x );

        //if it gets to the end of the list without finding what you want to remove, then it returns false
        if( itr == end( whichList ) )
        {
            return false;
        }


        //if it finds x, it removes it from the list
        whichList.erase( itr );
        --currentSize;
        return true;
    }

    /*
    void printTable()
    {
        for(int i=0; i < symbols.size(); i++)
        {
            cout << "The hash table contains: " << symbols[i] << endl;
        }
    }
    */

  private: 
     vector<list<HashedObj>> theLists;   // The array of Lists
     int  currentSize;

     void rehash( )
     {
         vector<list<HashedObj>> oldLists = theLists;

         // Creates new double-sized, empty table
         theLists.resize( nextPrime( 2 * theLists.size( ) ) );
         for( auto & thisList : theLists )
             thisList.clear( );

         // Copies the old table into the new table
         currentSize = 0;
         for( auto & thisList : oldLists )
             for( auto & x : thisList )
                 insert( std::move( x ) );
     }

     size_t myhash( const HashedObj & x ) const
     {
         static hash<HashedObj> hf;
         return hf( x ) % theLists.size( );
        }
  };

  int nextPrime( int n )
{
    if( n % 2 == 0 )
    {
        ++n;
    }


    for( ; !isPrime( n ); n += 2 )
    {

    }


    return n;
}

bool isPrime( int n )
{
    if( n == 2 || n == 3 )
        return true;

    if( n == 1 || n % 2 == 0 )
        return false;

    for( int i = 3; i * i <= n; i += 2 )
        if( n % i == 0 )
            return false;

    return true;
}

#endif

非常感谢你们帮助我!

Answer 1

你正在这样做:

static hash<HashedObj> hf;

但是您还没有提供 hash 模板，或者没有为 HashedObj 特化 std::hash。

您应该避免using namespace std;。除其他事项外，很难弄清楚您想要获得哪个 hash。