0
我創建了一個哈希映射類，除了使用迭代器外，它模仿stl映射。所以，現在我的問題是通過哈希映射循環，而不使用迭代器，並打印出與某個Key相關聯的Value。類本身是模板化的，但main.cpp中使用的值是一個字符串向量。我將如何製作打印功能來打印與鑰匙相關的項目（值）？我試着寫一個printElements（）函數，但它只打印Key。先謝謝你。通過無迭代器的哈希映射循環
這裏是我的散列映射類：
//
// 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;
}