Цикл по Hash Map без итераторов

Я создал класс хеш-карты, который имитирует карту STL, за исключением использования итераторов. Итак, теперь моя проблема заключается в циклическом просмотре хеш-карты без использования итераторов и распечатке значения, связанного с определенным ключом. Сам класс является шаблонным, но значение, используемое в main.cpp, является вектором строк. Как сделать функцию печати, которая будет печатать элементы (значения), связанные с ключом? Я попытался написать функцию printElements (), но она печатает только ключ. Заранее спасибо.

Вот мой класс хеш-карты:

//
//  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( );
}

};

Этот код используется в основном:

//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;

}

0

Решение

Если вы действительно хотите избежать итератора, я бы порекомендовал сохранить вектор пар значений ключей, который может предоставить вам интерфейс итератора. Если вам не нужно избегать итераторов даже на этом уровне (?). В этом случае вы можете предоставить метод, возвращающий const std::pair<Key,Value>* массив, который можно заполнить в полете, когда пользователю потребуется доступ к значениям в вашей коллекции.

0

Другие решения


По вопросам рекламы [email protected]