1

基本的に、hash_map ライブラリとして機能するように 2 次プロービング ファイルを編集する必要がありますが、特定のインデックスを変更できるように、添字演算子をオーバーロードするのに問題があります。

私がこれまでに持っているコードは次のとおりです。

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 に答える