1

我必须基本上编辑一个二次探测文件才能作为 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] 将是一个向量。我还假设我稍后需要修改 = 运算符，但我不太确定

4

1 回答 1

1

想想你的下标运算符应该返回什么。是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
    }
...
};

但它是私人的。因此，要么将其公开-但这会以某种方式破坏您的封装。

因为您正在插入 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;
    }
...
};
于 2012-10-28T22:28:22.347 回答