c++ - Data placed into array correctly but is not there when array is printed -
i'm implementing own hash table , running following problem: when insert node(s) table, not printed out when loop through array. using array of arrays underlying data structure , logic follows:
- i pass node insert function. function, based on type of data in node, calls appropriate hash function provided c++ stl.
- then, mod hash value returned size of hash table , use determine array place node.
- i have array of arrays of booleans (the same size hash table) use check whether specific spot in hash table has data in it.
- if does, keep looping till empty spot found.
like said before, problem data inputed correctly array (i've checked print statements), when print array, nothing outputted. have checked if object being constructed correctly (again, print statements), looking fine. i've included full code below. appreciated!
///////start of node.h/////////// #ifndef node_h #define node_h #include <iostream> template <typename t> class hashtable; template <typename t> class node { friend class hashtable<t>; private: t data; public: node(t data): data(data) { std::cout << "in node constructor" << std::endl; } node() { decltype(data) {}; } t getdata() const { return data; } }; #endif //////////////////////end of node.h//////////////////// /////start of hashtable.h/////// #ifndef hashtable_h #define hashtable_h #include "node.h" #include <iostream> #include <array> #include <functional> #include <typeinfo> #include <string> const int table_size=5; template <typename t> class hashtable { private: std::array<std::array<node<t>, table_size>, table_size> hashtable; std::array<std::array<bool, table_size>, table_size> spots; public: hashtable() { for(int index=0;index<spots.size();++index) { for(int position=0;position<spots.at(index).size();++position) { spots.at(index).at(position)=false; } } } int hashfunction(node<t> node) { auto key=node.getdata(); std::hash<decltype(node.getdata())> hash_function {}; int hash=hash_function(key); if(hash < 0) { hash*=-1; } //std::cout << "the hash value return stl hash function key " << key << " " << hash << std::endl; if(hash > table_size) { hash%=table_size; } std::cout << "the hash value key " << key << " " << hash << std::endl; return hash; } void insert(node<t> node) { int hashvalue=hashfunction(node); auto location=hashtable.at(hashvalue); std::cout << "going insert " << node.getdata() << std::endl; for(int index=0;index<location.size();++index) { if(spots.at(hashvalue).at(index)==false) { std::cout << "found spot not taken!" << std::endl; std::cout << "the size of data @ spot in array before insert is: " << location.at(index).getdata().size() << std::endl; location.at(index)=node; std::cout << "the size of data @ spot in array after insert is: " << location.at(index).getdata().size() << std::endl; std::cout << "the data in spot in array: " << location.at(index).getdata() << std::endl; std::cout << std::endl; spots.at(hashvalue).at(index)=true; break; } } } bool contains(node<t> node) { int hashvalue=hashfunction(node); auto location=hashtable.at(hashvalue); auto result=find_if(begin(location), end(location), [node] (const auto & element) {return element.getdata()==node.getdata();}); if(result!=end(location)) { return true; } return false; } int getsize() const { int size {}; for(int index=0;index<hashtable.size();++index) { size+=hashtable.at(index).size(); } return size; } void print() { std::cout << "in print function" << std::endl; for(int index=0;index<hashtable.size();++index) { //std::cout << hashtable.at(index).size() << std::endl; for(int position=0;position<hashtable.at(index).size();++position) { std::cout << hashtable.at(index).at(position).getdata().size() << std::endl; } } /* for(int index=0;index<spots.size();++index) { for(int position=0;position<spots.at(index).size();++position) { if(spots.at(index).at(position)==true) { std::cout << "there should data here" << std::endl; } } } */ } }; #endif ////////////end of hashtable.h////////// ////////////start of main.cpp/////////// #include "hashtable.h" #include <cstdlib> #include <random> #include <algorithm> using namespace std; int main() { hashtable<string> hash_table; hash_table.insert(node<string>("java")); hash_table.insert(node<string>("c++")); hash_table.insert(node<string>("c#")); hash_table.insert(node<string>("latex")); hash_table.insert(node<string>("python")); } /////////////end of main.cpp/////////////
one error in insert(node<t> node) function on these line:
auto location=hashtable.at(hashvalue); //... location.at(index) = node; the location should reference not copy. happening you're making changes local location, , not actual location hash table uses. none of changes "stick".
the line above should this:
auto& location=hashtable.at(hashvalue); // <-- note auto reference //... location.at(index) = node; now assigning returned reference reference.
also, highly recommend use debugger, error have been diagnosed if stepped through code see being done.
Comments
Post a Comment