根据条件 C++ 从向量中复制元素

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]);

其中P组和Q组是：

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

node 是我创建的一个结构，用于表示我的自动机的一个节点。保证布尔属性 "final" 已经正确设置（非最终状态为 false，最终状态为 true）。

最后，我的问题是：按照我所做的，将一个元素从一个向量复制到另一个向量是否正确？如果我修改从 groupP 复制的元素的内容，是否也会在 groupQ 中修改同一个元素？

Answer 1

您可以使用 std::copy_if 做同样的事情：

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

由于你是在操作指针，元素本身是共享的，所以修改一个容器中的节点可以从另一个容器中看到。

请注意，像您这样操作原始指针很容易出错，例如您可能想使用 shared pointers。

编辑： 添加缺失的 std::back_inserter。

Answer 2

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

因为你有两个指向同一个节点的指针，对一个节点所做的任何修改都将在另一个组中可见——也就是说，如果你对 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;

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

根据条件 C++ 从向量中复制元素

Copy elements from vector based on condition C++

c++

automata