автоматы — копировать элементы из вектора на основе условия переполнения стека

Question

автоматы — копировать элементы из вектора на основе условия переполнения стека

Я использую C ++ для создания алгоритма Хопкрофта для минимизации DFA.

Часть алгоритма Хопкрофта состоит в том, чтобы — изначально — разделить два набора (P с принимающим и неприемлемым состояниями и Q только с непринятыми состояниями). У меня уже есть группа P, и из P я пытаюсь извлечь Q. Я использую следующий код, чтобы сделать это:

for(int i=0; i<groupP.size(); i++)
if(groupP[i]->final)
groupQ.push_back(groupP[i]);

в которой groupP и groupQ находятся:

vector<node*> groupQ;
vector<node*> groupP;

а узел — это структура, которую я создал для представления узла моих автоматов. Гарантируется, что логический атрибут «final» уже установлен правильно (false для не конечных состояний, true для конечных состояний).

Наконец, мой вопрос: правильно ли копировать один элемент из вектора в другой, выполняя то, что я сделал? Если я изменю содержимое скопированного элемента из groupP, будет ли этот же элемент изменен и в groupQ?

0

automata c++

Решение

Другие решения

Вы могли бы использовать станд :: copy_if который делает то же самое:

std::copy_if(groupP.cbegin(), groupP.cend(),
std::back_inserter(groupQ),
[](node* n){ return n->final; });

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

Обратите внимание, что манипулирование необработанными указателями, как вы делаете, очень подвержено ошибкам, и вы можете использовать общие указатели например.

Редактировать: Добавление отсутствует std::back_inserter,

1

Источник

Accepted Answer

Прямо сейчас у вас есть векторы указателей. Когда вы копируете из одного вектора в другой, вы копируете указатели, а не сами элементы.

Поскольку у вас есть два указателя, относящихся к одному и тому же узлу, любая модификация узла будет видна в другой группе, т. Е. Если вы внесете изменение в groupP[i]->fooто же самое изменение будет видно в groupQ[j]->foo (при условии, что groupP[i] является одним из элементов, которые вы скопировали из groupP в groupQ,

Если вы не хотите этого, у вас есть несколько вариантов. Можно было бы уйти groupP а также groupQ в том же векторе, но разделить вектор на основе состояния элемента final член:

auto P_end = std::partition(groupP.begin(), groupQ.end(),
[](node *n) { return n->final;});

Тогда [groupP.begin (), P_begin) является groupP (т.е. final==true) и [P_begin, groupP.end ()) является groupQ (т.е. final==false).

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

В качестве последней возможности, вы можете скопировать элементы из groupP в groupQи в процессе создания нового элемента, поэтому после копирования элементов из groupP в groupQкаждый элемент, который вы скопировали, теперь существует в двух местах — то есть, есть один элемент в groupP и один элемент в groupQ, Любой из них может быть изменен, но они отделены друг от друга, поэтому любой из них может быть изменен, но изменение одного не влияет на другое.

Самый очевидный способ добиться этого — просто использовать векторы узлов:

vector<node> groupQ;
vector<node> groupP;

Таким образом, когда вы копируете из одной группы в другую, вы копируете сами узлы, а не указатели на узлы, поэтому каждая копия создает новый независимый узел с тем же значением, что и существующий узел.

3