stl :: sort（）正在改變它正在排序的對象的屬性

我一直在使用布朗算法編碼Graph Coloring問題的解決方案。該算法工作得很好，但爲了增加一點效率，我試圖按節點排序節點。爲此，我使用stl::sort()。儘管如此，排序已經排序元素後，每個元素的adyacency列表已被修改。我有4個文件：stl :: sort（）正在改變它正在排序的對象的屬性

nodo.h：

class Nodo{ 
private: 
    int id; 
    int color; 
    vector<Nodo*> adyacentes; 
public: 
    int grado; 
    vector<Nodo*> getAdyacentes(); 
    int getId(); 
    int getColor(); 
}

nodo.cpp - >包括干將的基本實現。

grafo.h：

class Grafo{ 
private: 
    Nodo *nodos; 
    int tam; 
public: 
    void colorearBrown(); 
    void imprimir(); 
}

grafo.cpp：

void Grafo::imprimir(){ 
    cout << setw(6) << "Numero" << setw(5) << " Color" << " Nodos adyacentes" << endl; 
    for(int i = 0; i < tam; ++ i){ 
     cout << setw(6) << nodos[i].getId() << setw(5) << nodos[i].getColor() << " "; 
     vector<Nodo*> ady = nodos[i].getAdyacentes(); 
     for(vector<Nodo*>::iterator it = ady.begin(); it != ady.end(); ++ it){ 
      if (it != ady.begin()){ 
       cout << ","; 
      } 
      cout << (*it)->getId(); 
     } 
     cout << endl; 
    } 
} 

bool operator<(const Nodo& a, const Nodo& b){ 
    return (a.grado >= b.grado); 
} 

void Grafo::colorearBrown(){ 
    imprimir(); 
    sort(&nodos[0], &nodos[tam]); 
    cout << endl << endl; 
    imprimir(); 
}

就是這樣。假設我已用「Grafo」對象中的正確裝載圖形，我運行的方法和colorearBrown()得到以下輸出（部分）：

. 
. 
. 
    16 -1 1,22,36,43,47,48 
    17 -1 10,13,20,22,44,47 
    18 -1 27,32,48 
    19 -1 4,32,36 
    20 -1 6,8,10,12,17,33,36,38,43,45,48 
    21 -1 4,6,45 
    22 -1 6,16,17,26,30,31 
    23 -1 3,8,10,14,24,26,32,36 
. 
. 
. 

Numero Color Nodos adyacentes 
    20 -1 4,42,22,32,10,3,34,50,18,19,25 
    7 -1 20,32,6,13,3,50,2,18,31,19 
    36 -1 7,14,16,44,12,38,30,1,50,37 
    14 -1 22,30,49,24,2,11,40,5 
. 
. 
.

瞭解如何對節點20 adyacent節點改變列表（這裏），但是這對於所有節點都是重複的。

該程序完美編譯，如果沒有排序，節點在整個執行過程中保持相同的方式。

任何關於排序算法爲什麼會混淆我的結構的想法會很有幫助。

來源

2012-02-16 cgledezma

而不是使用html標記，您可以簡單地添加4個空格在您的代碼前面，以更好的格式。 – Lucas 2012-02-16 21:33:38

您也可以突出顯示代碼行並使用'{}'按鈕來格式化代碼。 – 2012-02-16 21:36:48

'矢量 getAdyacentes'？選擇一種語言並堅持下去;這不完全可讀。 – MSalters 2012-02-17 09:11:51

std::sort複製（或在C++ 11中移動）對象。但是，您的對象中有指針，指向對象所在的位置。排序之後，那個地方還有另一個物體。

把它想象成坐在椅子上的人。你給每個人一個椅子名單，其中「相鄰」的人坐。然後你問人們換地方。改變地點的人不會改變寫在紙上的內容。

人是節點對象，位置是數組中的位置，帶有列表的紙張是指向相鄰節點的指針向量。

對這個問題的一個簡單的解決方案將使用std::list和排序sort成員函數。該成員函數不會移動對象，而只是重新鏈接內部節點，因此指針將繼續指向正確的對象。該解決方案的一個缺點（在你的情況下可能並不重要）是該列表不提供隨機訪問。

來源

2012-02-16 22:03:16 celtschk

stl :: sort（）正在改變它正在排序的對象的屬性

回答

相關問題