c++ - 为什么 stable_sort 会影响我的哈希表值？

Question

我已经定义了一个结构 ABC 来包含一个 int ID、字符串 NAME、字符串 LAST_NAME；
我的程序是这样的:从输入文件中读取一行。将每一行解析为名字和姓氏，并插入到 ABC 结构中。此外，结构的 ID 由输入行的编号给出。

然后，将结构 push_back 到 vector 主列表中。我还将这些散列到定义为 vector< vector > 的哈希表中，使用名字和姓氏作为关键字。也就是说，

如果我的数据是:
加菲猫
史努比狗
猫人

然后将关键字 cash 哈希到包含加菲猫和猫人的 vector 。我再次使用 push_back 将结构插入哈希表。

问题是，当我在我的 masterlist 上调用 stable_sort 时，我的哈希表由于某种原因受到了影响。我认为这可能会发生，因为歌曲的排序方式不同，所以我尝试复制主列表并对其进行排序，但它仍然影响哈希表，尽管原始主列表不受影响。

知道为什么会发生这种情况吗？

编辑——发布源代码:

这是主要内容

  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);
      }
    }
  }

这是哈希表插入实现的片段:

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

让我们看看。它可以是以下之一:

1. 您的哈希表实现已损坏。
2. 你的哈希函数坏了。
3. 排序会以某种方式改变您所存储内容的语义值。已排序的 vector 肯定与未排序的 vector 具有不同的值。

实际上，其中哪一个是问题的原因并不重要。为此，您应该是 std::map 容器。如果出于某种原因您绝对必须使用哈希表实现，那么至少使用一个相对标准的哈希容器，例如:

• std::unordered_map 在支持 C++11 的编译器上提供
• boost 的 boost::unordered_map
• std::tr1::unordered_map
• 许多编译器都提供了hash_map
• 等等

请注意，以上内容是按照您可能应该尝试的顺序排列的。