c++ - STL::sort() 正在改变它正在排序的对象的属性

Question

我一直在使用布朗算法编写图形着色问题的解决方案。该算法运行良好，但为了提高效率，我尝试按节点的程度对节点进行排序。为此，我使用了 STL::sort()。尽管如此，在 sort 对元素进行排序后，每个元素的邻接表都被修改了。我有 4 个文件:

nodo.h:

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

nodo.cpp -> 包括 getter 的基本实现。

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(此处)上发生变化，但这对所有节点都重复进行。

程序完美编译，如果没有排序，节点在整个孔执行过程中保持不变。

关于为什么排序算法会扰乱我的结构的任何想法都会有所帮助。

Answer 1

std::sort 复制(或移动，在 C++11 中)对象。但是，您的对象中有指针，指向对象所在的地方。排序后，那个地方还有另一个对象。

把它想象成人们坐在椅子上。您给每个人一张“相邻”人坐的椅子 list 。然后你要求人们改变位置。人们换地方并不会改变纸上写的内容。

人是节点对象，地点是数组中的位置，带有列表的纸片是指向相邻节点的指针 vector 。

该问题的一个简单解决方案是使用 std::list 并使用其 sort 成员函数进行排序。该成员函数不会四处移动对象，而只是重新链接内部节点，因此您的指针将继续指向正确的对象。该解决方案的一个缺点(在您的情况下可能重要也可能不重要)是该列表不提供随机访问。