c++ - 根据条件 C++ 从 vector 中复制元素

Question

我正在使用 C++ 创建 Hopcroft 的 DFA 最小化算法。

Hopcroft 算法的一部分是 - 最初 - 划分两个集合(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;

node 是我创建的一个结构，用于表示我的自动机的一个节点。保证已正确设置 bool 属性“final”(非最终状态为 false，最终状态为 true)。

最后，我的问题是:通过执行我所做的将一个元素从 vector 复制到另一个元素是否正确？如果我修改从 groupP 复制的元素的内容，是否也会在 groupQ 中修改这个相同的元素？

Answer 1

现在，您有指针 vector 。当您从一个 vector 复制到另一个 vector 时，您复制的是指针，而不是元素本身。

因为你有两个指向同一个节点的指针，对一个节点所做的任何修改都将在另一个组中可见——也就是说，如果你对 groupP[i]->foo，那么相同的变化将在 groupQ[j]->foo 中可见(前提是 groupP[i] 是您从 groupP 复制的元素之一 到 groupQ。

如果您不想这样，您有几个选择。一种方法是将 groupP 和 groupQ 留在同一个 vector 中，但根据元素的 final 成员的状态对 vector 进行分区:

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 :

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

这样，当您从一组复制到另一组时，您复制的是节点本身，而不是指向节点的指针，因此每次复制都会创建一个新的、独立的节点，其值与现有节点相同。