如何从 C++ 中的向量中链接删除对？

Question

我有这个文本文件，我正在将每一行读入 std::vector<std::pair>,

handgun bullets
bullets ore
bombs ore
turret bullets

第一项取决于第二项。我正在编写一个删除函数，当用户输入一个项目名称时，它会删除包含该项目的对作为第二个项目。既然存在依赖关系，依赖于被删除项的项也应该被删除，因为它不再可用。例如，如果我删除 ore，bullets 和 bombs 将无法再使用，因为 ore 不可用。因此，handgun 和 turret 也应该被删除，因为这些对依赖于 bullets，而 bullets 又依赖于 ore，即间接依赖于 ore。此链应继续，直到删除所有依赖对。

我尝试为当前示例执行此操作并附带以下伪代码，

for vector_iterator_1 = vector.begin to vector.end
{
    if user_input == vector_iterator_1->second
    {
        for vector_iterator_2 = vector.begin to vector.end
        {
            if vector_iterator_1->first == vector_iterator_2->second
            {
                delete pair_of_vector_iterator_2
            }
        }

        delete pair_of_vector_iterator_1
    }
}

不是一个很好的算法，但它解释了我打算做什么。在示例中，如果我删除 ore，则 bullets 和 bombs 也会被删除。随后，依赖于 ore 和 bullets 的对也将被删除（bombs 没有依赖性）。因为只有一个长度链 (ore-->bullets)，所以只有一个嵌套的 for 循环来检查它。但是，单个链中可能存在零个或大量依赖项，从而导致许多或没有嵌套 for 循环。所以，这不是一个非常实用的解决方案。我将如何使用可变长度的依赖链来做到这一点？请告诉我。感谢您的耐心等待。

P。 S.：如果你不明白我的问题，请告诉我。

Answer 1

一个（天真的）解决方案：

创建待删除项目队列
添加您的第一项（用户输入）
While(!empty(items-to-delete)) 遍历你的向量
每次您发现当前项目是列表中的第二项时，将第一项添加到您的队列中，然后删除该对

轻松优化：

确保您永远不会将一个项目添加到队列中两次（哈希 table/etc）

Answer 2

就个人而言，我只会使用标准库进行删除：

vector.erase(remove_if(vector.begin(), vector.end(), [](pair<string,string> pair){ return pair.second == "ore"; }));

remove_if() 为您提供了一个指向符合条件的元素的迭代器，因此您可以拥有一个函数，该函数接受要擦除的 .second 值，并在保存 .first 被擦除的值。从那里开始，您可以循环直到没有任何内容被删除。

对于您的解决方案，在循环内使用 find_if 可能更简单，但无论哪种方式，标准库都有一些您可以在这里使用的有用的东西。

Answer 3

我忍不住不使用 C++ 标准库中的标准算法和数据结构编写解决方案。我正在使用 std::set 来记住我们删除了哪些对象（我更喜欢它，因为它具有日志访问权限并且不包含重复项）。该算法与@Beth Crane 提出的算法基本相同。

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <string>
#include <set>

int main()
{
    std::vector<std::pair<std::string, std::string>> v
    {   {"handgun", "bullets"},
        {"bullets", "ore"},
        {"bombs", "ore"},
        {"turret", "bullets"}};

    std::cout << "Initially: " << std::endl << std::endl;
    for (auto && elem : v)
        std::cout << elem.first << " " << elem.second << std::endl;

    // let's remove "ore", this is our "queue"
    std::set<std::string> to_remove{"bullets"}; // unique elements

    while (!to_remove.empty()) // loop as long we still have elements to remove
    {
        // "pop" an element, then remove it via erase-remove idiom
        //  and a bit of lambdas
        std::string obj = *to_remove.begin();
        v.erase(
            std::remove_if(v.begin(), v.end(),
                           [&to_remove](const std::pair<const std::string,
                                        const std::string>& elem)->bool
            {
                // is it on the first position?
                if (to_remove.find(elem.first) != to_remove.end())
                {
                    return true;
                }
                // is it in the queue?
                if (to_remove.find(elem.second) != to_remove.end())
                {
                    // add the first element in the queue
                    to_remove.insert(elem.first);
                    return true;
                }
                return false;
            }
                          ),
            v.end()
        );
        to_remove.erase(obj); // delete it from the queue once we're done with it
    }

    std::cout << std::endl << "Finally: " << std::endl << std::endl;
    for (auto && elem : v)
        std::cout << elem.first << " " << elem.second << std::endl;
}

Answer 4

@vsoftco 我查看了 Beth 的回答并开始尝试解决方案。直到我回来才看到你的代码。在仔细检查您的代码后，我发现我们做了几乎相同的事情。这是我所做的，

std::string Node;

std::cout << "Enter Node to delete: ";

std::cin >> Node;

std::queue<std::string> Deleted_Nodes;

Deleted_Nodes.push(Node);

while(!Deleted_Nodes.empty())
{
    std::vector<std::pair<std::string, std::string>>::iterator Current_Iterator = Pair_Vector.begin(), Temporary_Iterator;

    while(Current_Iterator != Pair_Vector.end())
    {
        Temporary_Iterator = Current_Iterator;

        Temporary_Iterator++;

        if(Deleted_Nodes.front() == Current_Iterator->second)
        {
            Deleted_Nodes.push(Current_Iterator->first);

            Pair_Vector.erase(Current_Iterator);
        }

        else if(Deleted_Nodes.front() == Current_Iterator->first)
        {
            Pair_Vector.erase(Current_Iterator);
        }

        Current_Iterator = Temporary_Iterator;
    }

    Deleted_Nodes.pop();
}

为了在我的问题的评论中回答你的问题，这就是 else if 声明的目的。它应该是一个有向图，因此它只删除链中的下一级元素。更高级别的元素未被触及。

1 --> 2 --> 3 --> 4 --> 5

删除 5：1 --> 2 --> 3 --> 4

删除 3：1 --> 2 4 5

删除 1：2 3 4 5

尽管我的代码与您的相似，但我（目前）还不是 C++ 专家。如果我犯了任何错误或忽略了什么，请告诉我。谢谢。 :-)

如何从 C++ 中的向量中链接删除对？

How to chain delete pairs from a vector in C++?

c++

vector

chain

std-pair