I noticed that I had to pass by reference in order to change the actual vector object I used. But curious as to why for the print_table, I don't have to pass by reference, BUT for the trivial clear_table function I need to (otherwise Frank doesn't get removed from the list).
I'm just building trivial open addressing hash table using double hashing.
Code:
//FNV string hash fcn (src:http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx)
//Helper fcn used in open_address_insert/remove/search operations
unsigned int fnv_hash(const void* key, int len)
{
const unsigned char* p = static_cast<const unsigned char*>(key);
unsigned int h = 2166136261;
for (int i = 0; i < len; i++)
h = (h * 16777619) ^ p[i];
return h;
}
//note: no duplicates, no values (very simplified double hashing method of open addressing)
void insert_via_double_hashing(vector<string>& list, const string& key)
{
size_t size = list.size();
size_t cur_bucket = fnv_hash(key.c_str(), key.size() ) % size;
size_t second_hash_fcn = (fnv_hash(key.c_str(), key.size() ) % (size - 1) ) + 1;//NB: 2nd hash fcn is a step size
for ( size_t i = 0; i < list.size(); ++cur_bucket )
{
if ( list[cur_bucket] == "deleted" || list[cur_bucket] == "" )
{
list[cur_bucket] = key;
// cout << list[cur_bucket] << endl;
cout << "SUCCESS. Key:[" << key << "] inserted @:[" << cur_bucket << "]." << endl;
return;
}
cur_bucket = (cur_bucket + second_hash_fcn) % size;
}
}
void print_table(vector<string> v)
{
cout << "PRINTING TABLE..." << endl;
for ( size_t i = 0; i < v.size(); ++i )
cout << v.at(i) << ", ";
cout << endl;
}
//NB:redundant, but to hide details
void clear_table(vector<string>& v)
{
v.assign(10,"");
}
int main()
{
vector<string> namebook;
namebook.assign(10,"");
namebook[2] = "Frank";
for ( size_t i = 0; i < namebook.size(); ++i )
cout << namebook.at(i) << ", ";
cout << endl;
clear_table(namebook);
insert_via_double_hashing(namebook, "joe");
return 0;
}
EDIT: or I shouldn't worry since I didn't build the vector class and so the details of how it knows is part of compiler and library writer's job?