1

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

然后，将结构 push_back 放入向量主列表中。我还将这些散列到定义为 vector<vector> 的散列表中，使用名字和姓氏作为关键字。那是，

如果我的数据是：
Garfield Cat
Snoopy Dog
Cat Man

然后将关键字 cash 哈希到包含 Garfield Cat 和 Cat Man 的向量。我再次使用 push_back 将结构插入哈希表。

问题是，当我在我的主列表上调用 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;
  }
}
4

1 回答 1

2

让我们来看看。它可以是以下情况之一：

  1. 您的哈希表实现已损坏。
  2. 您的哈希函数已损坏。
  3. 不知何故，排序改变了你所存储内容的语义价值。排序后的向量肯定与未排序的向量具有不同的值。

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

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

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

于 2010-04-02T02:54:27.807 回答