Почему stable_sort может влиять на мои значения хеш-таблиц? - PullRequest
Новая
       45

Почему stable_sort может влиять на мои значения хеш-таблиц?

1 голос
/ 02 апреля 2010

Я определил struct ABC, которая будет содержать int ID, строку NAME, строку LAST_NAME;
Моя процедура такова: чтение строки из входного файла. Разобрать каждую строку в имя и фамилию и вставить в структуру ABC. Также идентификатор структуры задается номером строки ввода.

Затем вставьте структуру обратно в векторный список. Я также хэширую их в хеш-таблицу, определенную как vector , используя имя и фамилию в качестве ключевых слов. То есть

Если мои данные:
Кот Гарфилд
Снупи Дог
Человек-кошка

Затем для ключевого слова наличными хэширует вектор, содержащий 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;
  }
}

1 Ответ

2 голосов
/ 02 апреля 2010

Посмотрим. Это может быть одна из следующих вещей:

  1. Ваша реализация хеш-таблицы не работает.
  2. Ваша хеш-функция нарушена.
  3. Каким-то образом сортировка меняет семантическое значение того, что вы сохранили. Сортированный вектор, безусловно, имеет значения, отличные от несортированного вектора.

В действительности не имеет значения, кто из них является причиной проблемы. Вместо этого вы должны быть контейнером std::map. Если по какой-то причине вы обязательно должны использовать реализацию хеш-таблицы , то по крайней мере используйте относительно стандартный хеш-контейнер, такой как:

  • std::unordered_map предоставляется на компиляторах с поддержкой C ++ 11
  • буст boost::unordered_map
  • std::tr1::unordered_map
  • hash_map предоставляется со многими компиляторами
  • и т.д.

Обратите внимание, что вышеперечисленное упорядочено в том порядке, в котором вы, вероятно, должны их попробовать.

...