不带迭代程序的哈希映射循环

Question

我创建了一个散列映射类，除了使用迭代器之外，它模仿了stl映射。因此，现在我的问题是在不使用迭代器的情况下循环遍历哈希映射，并打印出与某个Key相关联的Value。类本身是模板化的，但main.cpp中使用的Value是字符串的向量。我该如何制作一个打印功能来打印与密钥关联的项目（值）？我尝试编写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;

}

Answer 1

如果你真的想避免迭代器，我建议你维护键值对的向量，它可以为你提供迭代器的up和atom接口。除非即使在这个级别也需要避免迭代器（？）。在这种情况下，您可以提供返回const std::pair<Key,Value>*的方法，当用户需要访问集合中的值时，可以在飞行中填充该数组。