爲什麼stable_sort會影響我的散列表值？

我已經定義了一個結構ABC來包含一個int ID，字符串名稱，字符串LAST_NAME;
我的程序是這樣的：從輸入文件中讀入一行。將每行解析爲名字和姓氏，並插入到ABC結構中。而且，結構的ID由輸入行的編號給出。爲什麼stable_sort會影響我的散列表值？

然後，將結構push_back到一個向量masterlist中。我也將這些散列表定義爲矢量< vector>，使用名和姓作爲關鍵字。也就是說，

如果我的數據是：
加菲貓
史努比狗
貓眼看人

然後爲關鍵字現金哈希含加菲貓和貓眼看人的向量。我再次使用push_back將結構插入散列表。

問題是，當我在我的masterlist上調用stable_sort時，我的散列表受到某種原因的影響。我認爲這可能會發生，因爲歌曲的排序方式不同，所以我嘗試製作masterlist的副本並對其進行排序，但仍然影響哈希表，儘管原始主列表不受影響。

任何想法，爲什麼會發生這種情況？

編輯 - 源代碼發佈：

這裏是主

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

來源

2010-04-01 zebraman

你可以請你發佈你的代碼？描述你認爲你所做的事通常比發佈實際代碼更有幫助，特別是當涉及算法問題時。 – 2010-04-01 23:17:13

對不起，它有點糾結。我不想在這裏發佈整個事情。有多個文件。但這是重要的東西。 – zebraman 2010-04-01 23:27:51

爲什麼你這樣做，而不是使用'std :: map'或類似非標準的'hash_map'或'boost :: unordered_map'？ – 2010-04-02 00:09:40

讓我們來看看。它可能是以下其中一種情況：

您的散列表實施已中斷。
你的散列函數被破壞。
不知何故排序會改變您存儲的語義值。排序的向量與未排序的向量的值必定不同。

實際上，這些問題中的哪一個並不重要。你應該是std::map容器，而不是這個。如果由於某種原因，你絕對必須使用哈希表實現那麼至少使用相對標準的哈希容器中，如：

提供與編譯器std::unordered_map C++ 11的支持
升壓轉換器的boost::unordered_map
std::tr1::unordered_map
hash_map設置有許多編譯器
等

請注意，上面的順序是您應該嘗試的順序。

來源

2010-04-02 02:54:27

爲什麼stable_sort會影響我的散列表值？

回答

相關問題