ベクトルのベクトルを使用してハッシュテーブルを作成しますか？

Question

私は現在、衝突解消法のベクトルベクトルを使ってハッシュテーブルを作成するプログラムを書こうとしています。

私が直面している問題は、実行時にベクトルのベクトルが作成されますが、内部のすべてのエントリベクトルはサイズ0のままです。私のput関数は不完全であることがわかりますが、どこに/理由がわかりません。

これは初めてのハッシュテーブルの作成であり、問​​題の可能性がある場合はお気軽にお問い合わせください。私の目標は、エントリーベクトルのベクトルを作成することです。各エントリーには、関連するキーと値があります。新しいEntryキーのハッシュ値を見つけたら、Entryベクトルのキー値をチェックして、キーがすでに存在するかどうかを調べる必要があります。そうであれば、そのキーの値を更新します。

これはtable.cppのセグメントである：

Table::Table(unsigned int maximumEntries) : maxEntries(100){ 
    this->maxEntries = maximumEntries; 
    this->Tsize = 2*maxEntries; 

} 

Table::Table(unsigned int entries, std::istream& input){ //do not input more than the specified number of entries. 

    this->maxEntries = entries; 
    this->Tsize = 2*maxEntries; 

    std::string line = ""; 

    int numEntries = 0; 


    getline(input, line); 
    while(numEntries<maxEntries || input.eof()){ // reads to entries or end of file 
     int key; 
     std::string strData = ""; 

     convertToValues(key, strData, line); 

     put(key, strData); // adds each of the values to the tab;e 

     numEntries++; 

     getline(input,line); 

    } 

} 



void Table::put(unsigned int key, std::string data){ 
    Entry newEntryObj(key,data); //create a new Entry obj 
    put(newEntryObj); 
} 


void Table::put(Entry e){ // creating the hash table 

    assert(currNumEntries < maxEntries); 

    int hash = (e.get_key() % Tsize); 

    Entry newEntry = Entry(e.get_key(), e.get_data()); 

    for(int i = 0; i < hashtable[hash].size(); i++){ 
     if (e.get_key() == hashtable[hash][i].get_key()){ 
      hashtable[hash][i].set_data(e.get_data()); 
     } 
     else{ 
      hashtable[hash].push_back(newEntry); // IF KEY DOESNT EXIST, ADD TO THE VECTOR 
     } 
    } 
} 

これはTable.h

#ifndef table_h 
#define table_h 

#include "entry.h" 
#include <string> 
#include <istream> 
#include <fstream> 
#include <iostream> 
#include <vector> 


class Table{ 

    public: 

    Table(unsigned int max_entries = 100); //Builds empty table with maxEntry value 
    Table(unsigned int entries, std::istream& input); //Builds table designed to hold number of entires 


    void put(unsigned int key, std::string data); //creates a new Entry to put in 
    void put(Entry e); //puts COPY of entry into the table 
    std::string get(unsigned int key) const; //returns string associated w/ param, "" if no entry exists 
    bool remove(unsigned int key); //removes Entry containing the given key 

    friend std::ostream& operator<< (std::ostream& out, const Table& t); //overloads << operator to PRINT the table. 

    int getSize(); 

    std::vector<std::vector<Entry>> getHashtable(); 


    private: 
    std::vector<std::vector<Entry>> hashtable; //vector of vectors 
    int Tsize; //size of table equal to twice the max number of entries 
    int maxEntries; 
    int currNumEntries; 

#endif /* table_h */ 
}; 

とEntry.hです：

#include <string> 
#include <iosfwd> 

class Entry { 

public: 
    // constructor 
    Entry(unsigned int key = 0, std::string data = ""); 

    // access and mutator functions 
    unsigned int get_key() const; 
    std::string get_data() const; 
    static unsigned int access_count(); 
    void set_key(unsigned int k); 
    void set_data(std::string d); 

    // operator conversion function simplifies comparisons 
    operator unsigned int() const; 

    // input and output friends 
    friend std::istream& operator>> 
    (std::istream& inp, Entry &e); 
    friend std::ostream& operator<< 
    (std::ostream& out, Entry &e); 

private: 
    unsigned int key; 
    std::string data; 
    static unsigned int accesses; 

}; 

Answer 1

あなたの持つ様々な問題があります。コードですが、あなたの質問に対する答えは次のようになります。

void Table::put(Entry e){ // creating the hash table 

ループを見てください。

for(int i = 0; i < hashtable[hash].size(); i++){ 

ここで、hashtable[hash]はベクターである。しかし、当初、それはどんな要素も持っていません。したがってhashtable[hash].size()は0です。したがって、ループを入力しないでください。

最初にhashtable[hash]にアクセスしようとすると、hashtableがTsizeに正しくサイズ変更されていないため、未定義の動作が発生します。あなたのコンストラクタ（S）でこれを試してみてください：

this->maxEntries = maximumEntries; 
this->Tsize = 2*maxEntries; 
this->hashtable.resize(this->Tsize); 

EDIT：

あなたの代わりにstd::vector::operator[]のstd::vector::at機能を使用する場合は理解することが容易になるだろう。たとえば：あなたはhashtable.at(hash)を初めてやるしようとすると、

void Table::put(Entry e){ // creating the hash table 

    assert(currNumEntries < maxEntries); 

    int hash = (e.get_key() % Tsize); 

    Entry newEntry = Entry(e.get_key(), e.get_data()); 

    for(int i = 0; i < hashtabl.at(hash).size(); i++){ 
     if (e.get_key() == hashtable.at(hash).at(i).get_key()){ 
      hashtable.at(hash).at(i).set_data(e.get_data()); 
     } 
     else{ 
      hashtable.at(hash).push_back(newEntry); // IF KEY DOESNT EXIST, ADD TO THE VECTOR 
     } 
    } 
} 

hashtableのサイズを変更せずに、このコードはout_of_range例外をスローしていました。

P.S.これはどれもテストされていません。