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