我使用的是通用哈希表类,但是当我在 main 中声明字符串时,它会出现以下错误。我认为问题是在“typename”部分引起的,但是当我更改为“class”时,问题并没有解决。
我的主要:
HashTable<string> H;
我的标题:
#ifndef QUADRATIC_PROBING_H
#define QUADRATIC_PROBING_H
#include <vector>
#include <string>
using namespace std;
int nextPrime( int n );
// QuadraticProbing 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 hash( string str ) --> Global method to hash strings
template <typename HashedObj>
class HashTable
{
public:
explicit HashTable( int size = 101 ) : array( nextPrime( size ) )
{ makeEmpty( ); }
bool contains( const HashedObj & x ) const
{
return isActive( findPos( x ) );
}
void makeEmpty( )
{
currentSize = 0;
for( size_t i = 0; i < array.size( ); i++ )
array[ i ].info = EMPTY;
}
bool insert( const HashedObj & x )
{
// Insert x as active
size_t currentPos = findPos( x );
if( isActive( currentPos ) )
return false;
array[ currentPos ] = HashEntry( x, ACTIVE );
// Rehash; see Section 5.5
if( ++currentSize > array.size( ) / 2 )
rehash( );
return true;
}
bool remove( const HashedObj & x )
{
int currentPos = findPos( x );
if( !isActive( currentPos ) )
return false;
array[ currentPos ].info = DELETED;
return true;
}
enum EntryType { ACTIVE, EMPTY, DELETED };
private:
struct HashEntry
{
HashedObj element;
EntryType info;
HashEntry( const HashedObj & e = HashedObj( ), EntryType i = EMPTY )
: element( e ), info( i ) { }
};
vector<HashEntry> array;
int currentSize;
bool isActive( int currentPos ) const
{ return array[ currentPos ].info == ACTIVE; }
int findPos( const HashedObj & x ) const
{
int offset = 1;
size_t currentPos = myhash( x );
// Assuming table is half-empty, and table length is prime,
// this loop terminates
while( array[ currentPos ].info != EMPTY &&
array[ currentPos ].element != x )
{
currentPos += offset; // Compute ith probe
offset += 2;
if( currentPos >= array.size( ) )
currentPos -= array.size( );
}
return currentPos;
}
void rehash( )
{
vector<HashEntry> oldArray = array;
// Create new double-sized, empty table
array.resize( nextPrime( 2 * oldArray.size( ) ) );
for( size_t j = 0; j < array.size( ); j++ )
array[ j ].info = EMPTY;
// Copy table over
currentSize = 0;
for( size_t i = 0; i < oldArray.size( ); i++ )
if( oldArray[ i ].info == ACTIVE )
insert( oldArray[ i ].element );
}
int myhash( const HashedObj & x ) const
{
int hashVal = hash( x );
hashVal %= array.size( );
if( hashVal < 0 )
hashVal += array.size( );
return hashVal;
}
};
int hash( const string & key );
int hash( int key );
#endif
我收到以下错误:
d:\users\suuser\documents\visual studio 2010\projects\cs300-hw3\cs300-hw3\quadraticprobing.h(50): warning C4018: '>' : signed/unsigned mismatch
1> d:\users\suuser\documents\visual studio 2010\projects\cs300-hw3\cs300-hw3\quadraticprobing.h(41) : while compiling class template member function 'bool HashTable<HashedObj>::insert(const HashedObj &)'
1> with
1> [
1> HashedObj=std::string
1> ]
1> d:\users\suuser\documents\visual studio 2010\projects\cs300-hw3\cs300-hw3\compressor.cpp(130) : see reference to class template instantiation 'HashTable<HashedObj>' being compiled
1> with
1> [
1> HashedObj=std::string
1> ]
1>d:\users\suuser\documents\visual studio 2010\projects\cs300-hw3\cs300-hw3\quadraticprobing.h(120): error C2872: 'hash' : ambiguous symbol
1> could be 'hash'
1> or 'c:\program files\microsoft visual studio 10.0\vc\include\xfunctional(763) : std::hash'
1> d:\users\suuser\documents\visual studio 2010\projects\cs300-hw3\cs300-hw3\quadraticprobing.h(119) : while compiling class template member function 'int HashTable<HashedObj>::myhash(const HashedObj &) const'
1> with
1> [
1> HashedObj=std::string
1> ]