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（）正在改变它正在排序的对象的属性

回答

相关问题