Предыдущее содержимое вектора std заменяется во время итерации - PullRequest
0 голосов
/ 01 декабря 2018

Я пишу программу, которая должна найти корневое связующее дерево в графе и все уникальные пути, соединяющие корень с другими вершинами в связующем дереве.Я пытаюсь выполнить обе операции только с одной функцией:

void Spanning_tree_finder(){

    int * v=Add_edges(s1); int control=0; int size;

    for(int i=0; i<_g.GetE(); i++){

        if(control==0 && v[i]==1) {

        s1[i]=1; control=1; 
        size=_v.size(); 
            for(int j=0; j<size; j++){

                if(_v[j].Getv2()==_g.GetEdge1(i)){
                Path pnew=_v[j];

                pnew.Setv2(_g.GetEdge2(i));
                pnew.Setp(i); 
                _v.push_back(pnew); 
                };

                if(_v[j].Getv2()==_g.GetEdge2(i)){
                Path pnew=_v[j];
                pnew.Setv2(_g.GetEdge1(i));
                pnew.Setp(i);
                _v.push_back(pnew); 
                };
            };

        Spanning_tree_finder();

        };
    };

    return;
};

Ради контекста, функция строит связующее дерево итеративно, которое в конце процесса содержится в s1, путемвзять дерево, также содержащееся в s1, выполнить поиск всех соседних ребер с помощью функции Add_edges и, таким образом, добавить к предыдущему дереву один из соседних ребер.Затем функция вызывается снова (обратите внимание, что Add_Edges и Spanning_tree_finder являются частью класса, а s1 является закрытым членом такого класса).Во время этого процесса функция также создает путь, соединяющий корень со свободной вершиной, связанной с недавно введенным смежным ребром, путем поиска предыдущего пути, соединяющего корень с непустой вершиной недавно введенного ребра и добавляя к этому путинедавно введенный край.Все пути хранятся в векторе путей, _v.Я знаю, что это объяснение немного запутанное, но я надеюсь, что оно понятно.

Однако, есть проблема с этой функцией, так как кажется, что на каждой итерации все пути, содержащиеся в _v, заменяются напуть, который был получен в текущей итерации.Вместо получения _v.size() различных путей, _v содержит _v.size() копий одного и того же пути, и это выполняется на каждой итерации.Я не понимаю, почему это произошло, так как мне кажется, что функция никогда не обращается к ранее добавленным элементам.Я надеюсь, что проблема, как я объяснил, ясна, и я с удовольствием предоставлю дальнейшие разъяснения.

РЕДАКТИРОВАТЬ: Более конкретно, строки кода, которые я считаю проблемными, являются

for(int j=0; j<size; j++){

            if(_v[j].Getv2()==_g.GetEdge1(i)){
            Path pnew=_v[j];

            pnew.Setv2(_g.GetEdge2(i));
            pnew.Setp(i); 
            _v.push_back(pnew); 
            };

            if(_v[j].Getv2()==_g.GetEdge2(i)){
            Path pnew=_v[j];
            pnew.Setv2(_g.GetEdge1(i));
            pnew.Setp(i);
            _v.push_back(pnew); 
            };
};

Суть проблемы в том, как pnew вставляется в _v.Вместо элемента pnew, добавляемого в конце вектора, все элементы в _v заменяются на pnew

1 Ответ

0 голосов
/ 01 декабря 2018

Конечно, звучит так, как будто объекты в _v имеют некоторые данные, к которым обращается указатель, и что вы изменяете объекты уже в _v, изменяя объект, который вы считаете новым.

Хрустальный шар говорит, что Path pnew = _v[j] копирует существующий объект Path, который содержит некоторые указатели на данные.Указатели будут скопированы на новый объект, но будут указывать на то же местоположение, поэтому такие модификаторы, как Setv2 и Setp, изменят данные для всех них.

Попробуйте исправить путь, либо заменив явныйуказатели на что-то другое, например векторы, или написание правильного конструктора копирования и оператора присваивания, которые правильно обрабатывают эти поля указателя (выделяя новую память и копируя содержимое).

...