我基本上必须编辑一个二次探测文件以用作 hash_map 库,但我在重载下标运算符时遇到问题,因此我可以修改该特定索引。
我目前的代码是:
template <typename HashedObj, typename storedObj >
class HashTable
{
public:
int& operator [] (const int nIndex)
{
return array[nIndex];//THIS IS WHATS WRONG
}
//create hashtable with siz of 101
explicit HashTable(int size = 101) : array( nextPrime( size ) )
{ makeEmpty( ); }
//return true if current index is active
bool contains( const HashedObj & x ) const
{
return isActive( findPos( x ) );
}
//initiallize index as empty
void makeEmpty( )
{
currentSize = 0;
for( int i = 0; i < array.size( ); i++ )
array[ i ].info = EMPTY;
}
//insert object into hash index and mark index as active
bool insert( const HashedObj & x )
{
// Insert x as active
int currentPos = findPos( x );
if( isActive( currentPos ) )
return false;
array[ currentPos ] = HashEntry( x, ACTIVE );
if( ++currentSize > array.size( ) / 2 )
rehash( );
return true;
}
//search for obj and mark index as deleted
bool remove( const HashedObj & x )
{
int currentPos = findPos( x );
if( !isActive( currentPos ) )
return false;
array[ currentPos ].info = DELETED;
return true;
}
//declare three different entry types
enum EntryType { ACTIVE, EMPTY, DELETED };
private:
//each hash index stores the following
struct HashEntry
{
//THIS WILL BE STRINGS OR INTS
HashedObj element;
//THIS WILL BE VECTOR STRINGS
storedObj ilement;
//index status is stored
EntryType info;
//each entry is made of hashed obj and stored obj and the status is empty
HashEntry( const HashedObj & e = HashedObj( ), const storedObj & f = storedObj( ),EntryType i = EMPTY )
: element( e ), ilement( f ),info( i ) { }
};
//create an array of hashentries
vector<HashEntry> array;
//currentsize of the hash table is stored here
int currentSize;
bool isActive( int currentPos ) const
{ return array[ currentPos ].info == ACTIVE; }
int findPos( const HashedObj & x ) const
{
int offset = 1;
int currentPos = myhash( x );
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( int j = 0; j < array.size( ); j++ )
array[ j ].info = EMPTY;
// Copy table over
currentSize = 0;
for( int i = 0; i < oldArray.size( ); i++ )
if( oldArray[ i ].info == ACTIVE )
insert( oldArray[ i ].element );
}
int myhash( const HashedObj & x ) const
{
int hashVal = hashing( x );
hashVal %= array.size( );
if( hashVal < 0 )
hashVal += array.size( );
return hashVal;
}
};
int hashing( const string & key );
int hashing( int key );
重点是主要代码能够做类似的事情:
wordsByLength[words[i].length()] = words[i];
其中 words[i] 将是一个 vector 。我还假设我稍后需要修改 = 运算符,但我不太确定
最佳答案
想想你的下标运算符应该返回什么。是 int&
吗?最简单的选择是 HashEntry:
template <typename HashedObj, typename storedObj >
class HashTable
{
public:
HashEntry& operator [] (int nIndex) // read/write version
{
return array[nIndex];
}
const HashEntry& operator [] (int nIndex) const // read only version
{
return array[nIndex];//THIS IS WHATS WRONG
}
...
};
但它是私有(private)的。因此,要么将其公开 - 但这会以某种方式破坏您的封装。
因为您正在插入 HashedObj - 那么这可能是您想要的返回类型:
template <typename HashedObj, typename storedObj >
class HashTable
{
public:
HashedObj& operator [] (int nIndex) // read/write version
{
return array[nIndex].element;
}
const HashedObj& operator [] (int nIndex) const // read only version
{
return array[nIndex].element;
}
...
};
关于c++ - 我如何重载模板类的下标运算符,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13113599/