Loop through Hash Map without Iterators

Question

I have created a hash map class that mimics the stl map except for the use of iterators. So, now my problem is looping through the hash map, without using iterators, and printing out the Value that is associated with a certain Key. The class itself is templated, but the Value used in the main.cpp is a vector of strings. How would I make a print function that will print the items (Value) associated with a Key? I tried writing a printElements() function, but it only prints the Key. Thank you in advance.

Here is my hash map class:

//
//  HashMap.h
//  HashWordPuzzle
//
//  Created by Elizabeth Kelly on 3/27/15.
//  Copyright (c) 2015 Elizabeth Kelly. All rights reserved.
//

#ifndef __HashWordPuzzle__HashMap__
#define __HashWordPuzzle__HashMap__

#include <vector>
#include <algorithm>
#include <functional>
#include <string>
#include <iostream>

using namespace std;

int nextPrime( int n );

// QuadraticProbing HashMap 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 hashCode( string str ) --> Global method to hash strings

template <typename Key, typename Value>
class HashMap
{
public:
explicit HashMap (int size ) : array_( nextPrime( size ) )
{ makeEmpty( ); }

bool contains( const Key & key ) const
{
    return isActive( findPos( key ) );
}

int getSize() {
    return array_.size();
    //return count;
}

const Value & getValue(const Key & key) const {
    int index = findPos(key);
    return array_[index].value_;
}

Key getKey(const int index) const {
    return array_[index].key_;
}

void makeEmpty( )
{
    currentSize = 0;
    for( auto & entry : array_ )
        entry.info = EMPTY;
}

bool insert( const Key & key, const Value & value )
{
    // Insert x as active
    int currentPos = findPos( key );
    if( isActive( currentPos ) )
        return false;

    array_[ currentPos ].key_ = key;
    array_[ currentPos ].info = ACTIVE;
    array_[currentPos].value_ = Value{};
    count++;

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

    return true;
}

bool insert( Key && key, Value && value )
{
    // Insert x as active
    int currentPos = findPos( key );
    if( isActive( currentPos ) )
        return false;

    array_[ currentPos ] = std::move( key );
    array_[ currentPos ].info = ACTIVE;
    array_[currentPos].value_ = Value{};

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

    return true;
}

bool remove( const Key & key )
{
    int currentPos = findPos( key );
    if( !isActive( currentPos ) )
        return false;

    array_[ currentPos ].info = DELETED;
    return true;
}

Value & operator[](const Key & key) {

    int index = findPos(key);
    if (!contains(key)) {
        insert(key, Value{});
    }

    return array_[index].value_;
    //check if index is valid (if -1) then insert an empty key and an empty vector
}

const Value & operator[](const Key & key) const {
    int index = findPos(key);
    //return find(key);

    return array_[index].value_;//???????
}

int getNext(int pos) {
    while (!isActive(pos) && pos != array_.size()) {
        pos++;
    }
    return pos;
}

void printElements() {
    for (int i = 0; i < array_.size(); i++) {
        if (isActive(i)) {
            cout << array_[i].key_ << " " << endl;
            cout << endl;
            for (int i = 0; i < getValue(array_[i].key_).size(); i++) {
                cout << getValue(array_[i].key_)[i] << endl;
            }

        }
    }

}


enum EntryType { ACTIVE, EMPTY, DELETED };

private:
struct HashEntry
{
    Key key_;
    Value value_;
    EntryType info;

    HashEntry( const Key & e = Key{ }, const Value & v = Value{}, EntryType i = EMPTY )
    : key_{ e }, info{ i } { }

    HashEntry( Key && e, const Value & v = Value{}, EntryType i = EMPTY )
    : key_{ std::move( e ) }, info{ i } { }
};

vector<HashEntry> array_;
int currentSize;
int count = 0;

bool isActive( int currentPos ) const
{ return array_[ currentPos ].info == ACTIVE; }

int findPos( const Key & key ) const
{
    int offset = 1;
    int currentPos = myhash( key );

    while(array_[currentPos].info != EMPTY && array_[currentPos].key_ != key){
        currentPos += offset;  // Compute ith probe
        offset += 2;

        if(currentPos >= array_.size()) {
            currentPos -= array_.size();
        }
    }//close while
    return currentPos;
}

void rehash( )
{
    vector<HashEntry> oldArray = array_;

    // Create new double-sized, empty table
    array_.resize( nextPrime( 2 * oldArray.size( ) ) );
    for( auto & entry : array_ )
        entry.info = EMPTY;

    // Copy table over
    currentSize = 0;
    for( auto & entry : oldArray )
        if( entry.info == ACTIVE )
            insert( std::move( entry.key_ ), entry.value_ );
}

size_t myhash( const Key & key ) const
{
    static hash<Key> hf;
    return hf( key ) % array_.size( );
}

};

This is the code used in the main:

//Computes a map in which the keys are words and values are vectors of    words
//that differ in only one character from the corresponding key.
//Uses a quadratic algorithm, but speeds things up a little by
//maintaining an additional map that groups words by their length
HashMap<string, vector<string>> computeAdjacentWords(const vector<string> & words, int table_size) {

HashMap<string, vector<string>> adj_words(table_size); //key is type string
HashMap<int, vector<string>> words_by_length(table_size); //key is type int

//Group words by their length
for (int i = 0; i < words.size(); i++) {
    words_by_length[words[i].length()].push_back(words[i]);
    words_by_length.getNext(i); //I need to loop through the map here WITHOUT using iterators
}

//Work on each group separately
for (int i = 0; i < words_by_length.getSize(); i++) {
    const vector<string> & groups_words = words_by_length.getValue(i);
    //const vector<string> & groups_words = words_by_length.getValue(words_by_length[i]);
    //implement getNext(), current_counter to replace the lack of iterator

    for (int i = 0; i < groups_words.size(); ++i) {
        for (int j = i + 1; j < groups_words.size(); ++j) {
            if (oneCharOff(groups_words[i], groups_words[j])) {
                adj_words[groups_words[i]].push_back(groups_words[j]);
                adj_words[groups_words[j]].push_back(groups_words[i]);

            }//close if
        }//close for loop
    }//close for loop
}//close for loop

return adj_words;

}

Answer 1

If you really want to avoid the iterator, I would recommend to maintain the vector of keyvalue pairs that can provide you the up-and-atom interface of iterator. Unless you need to avoid iterator even at this level(?). In this case you could provide the method returning const std::pair<Key,Value>* the array that could be filled in flight when user would need an access to values in your collection.