Why might stable_sort be affecting my hashtable values?

Question

I have defined a struct ABC to contain an int ID, string NAME, string LAST_NAME;
My procedure is this: Read in a line from an input file. Parse each line into first name and last name and insert into the ABC struct. Also, the struct's ID is given by the number of the input line.

Then, push_back the struct into a vector masterlist. I am also hashing these to a hashtable defined as vector< vector >, using first name and last name as keywords. That is,

If my data is:
Garfield Cat
Snoopy Dog
Cat Man

Then for the keyword cash hashes to a vector containing Garfield Cat and Cat Man. I insert the structs into the hashtable using push_back again.

The problem is, when I call stable_sort on my masterlist, my hashtable is affected for some reason. I thought it might be happening since the songs are being ordered differently, so I tried making a copy of the masterlist and sorting it and it still affects the hashtable though the original masterlist is unaffected.

Any ideas why this might be happening?

EDIT--source code posted:

Here is the main

  ifstream infile;
  infile.open(argv[1]);
  string line;
  vector<file> masterlist;
  vector< vector<node> > keywords(512);
  hashtable uniquekeywords(keywords,512);


  int id=0;
  while (getline(infile,line)){
    file entry;
    if (!line.empty() && line.find_first_not_of(" \t\r\n")!=line.npos){
      id++;
      string first=beforebar(line,0);
      string last=afterbar(line);
      entry.first=first;
      entry.last=last;
      entry.id=id;
      masterlist.push_back(entry);

      int pos=line.find_first_of("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890");

      while (pos!=(int)line.npos){
    string keyword=getword(line,pos);
    node bucket(keyword,id);
    bucket.addentry(entry);
    uniquekeywords.insert(bucket);
      }
    }
  }

Here is the snippet of hashtable insert implementation:

struct node{
  string keyword;
  vector<file> entries;
  int origin;

  void addentry(file entry);
  node(string keyword, int origin);
};


void hashtable::insert(node bucket){
  int key=hashfunction(bucket.keyword);
  if (table[key].empty()){
    table[key].push_back(bucket);
    numelt++;
  }
  else{
    vector<node>::iterator it;
    it=table[key].begin();
    while(it!=table[key].end()){
      if (compare((*it).keyword,bucket.keyword)==0 && (*it).origin!=bucket.origin){
    (*it).entries.insert((*it).entries.end(),bucket.entries.begin(),bucket.entries.end());
    (*it).origin=bucket.origin;
    return;
      }
      it++;
    }
    node bucketcopy(bucket.keyword,bucket.origin);
    table[key].push_back(bucket);
    numelt++;
    return;
  }
}

Answer 1

Let's see. It can be one of these things:

1. Your hashtable implementation is broken.
2. Your hash function is broken.
3. Somehow sorting changes the semantic value of what you've stored. A sorted vector certainly has different values than an unsorted vector.

In reality, it doesn't matter which one of these are the cause of the problem. You should be the std::map container instead for this. If for some reason you absolutely must use a hash table implementation then at least use a relatively standard hashed container such as:

• boost's boost::unordered_map
• std::unordered_map provided on compilers with C++0x support
• std::tr1::unordered_map
• hash_map provided with many compilers
• etc.

Note that the above are ordered in the order that you should probably try them.