从一个向量中删除元素，如果它们也在另一个向量中。

Question

假设我有一个向量a={"the", "of"}和一个向量b={"oranges", "the", "of", "apples"}。

我想比较这两个向量，并从a中删除也在b中的元素。以下是我想出来的解决方法：

for (int i = 0; i < a.size(); i++) {
    for (int j =0; j < b.size(); j++) {
       if (a[i] == b[j]) {
          a.erase(a.begin() + i);
       }
    }
}

但是，这个循环没有移除a中的最后一个元素。奇怪！

- muqsitnawaz

---

a[i] 的含义在内部循环的中间发生了改变。 - Kerrek SB

你能对向量进行排序吗？那么你可以直接使用 std::set_difference。 - Kerrek SB

是的。这可能就是为什么它不起作用的原因。但是你怎么能对字符串进行排序呢？我必须处理字符串。 - muqsitnawaz

这些不应该是集合吗？浏览一下标准库提供的算法，并将它们组合起来形成您的解决方案。如果您遇到具体问题，请告诉我们。 - Lightness Races in Orbit

Answer 1

问题在于当你移除 a 的第一个元素时，索引从 0 增加到 1。在循环的下一次迭代中，向量的大小为 1，符合外部循环的条件导致其终止。您可以通过简单地使用 std::remove_if、std::find 和 lambda 来避免可能需要的任何诡计来解决这个问题。

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

int main()
{
    std::vector<std::string> a{ "the", "of" };
    std::vector<std::string> b{ "oranges", "the", "of", "apples" };

    auto pred = [&b](const std::string& key) ->bool
    {
        return std::find(b.begin(), b.end(), key) != b.end();
    };

    a.erase(std::remove_if(a.begin(), a.end(), pred), a.end());

    std::cout << a.size() << "\n";
}

更好的测试方法是交换 a 和 b 的内容。这将去掉 "the" 和 "of"，留下 "oranges" 和 "apples"。

- Captain Obvlious

---

情况比这还要糟糕一些；除非内部循环已经处于最后一次迭代，否则外部循环肯定不会立即“终止”，突然间你正在访问可能已经不存在的元素。 - Lightness Races in Orbit

是的，我错过了那个。甚至没有想到在容器中删除元素后，内部循环可能会有未定义行为，如果该元素是最后一个。我会再试几次后添加它 :) - Captain Obvlious

Answer 2

尝试以下方法。

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cassert>

int main()
{
    std::vector<std::string> a = { "the", "of" };
    std::vector<std::string> b = { "oranges", "the", "of", "apples" };

    for ( auto it = a.begin(); it != a.end(); )
    {
        if ( std::find( b.begin(), b.end(), *it ) != b.end() )
        {
            it = a.erase( it ); 
        }
        else
        {
            ++it;
        }
    }

    assert( a.empty() );
}

当然，如果向量有序会更好。

- Vlad from Moscow

---

然后如果它们是集合会更好，这样你就可以使用内置算法轻松找到差异。只需一行代码。 - Lightness Races in Orbit

Answer 3

总的来说，建议使用STL已经构建好的算法，而不是手动遍历向量内容并选择性地删除其项目。 使用Erase-Remove惯用语 特别地，要从std::vector中删除满足某些属性的项目，可以考虑使用erase-remove惯用语。 这个Stackoverflow上的问答讨论了一些从STL容器（包括std::vector）中删除项目的选项。

您可以在下面找到有注释的可编译代码，在线查看：

#include <algorithm>    // for std::remove_if()
#include <iostream>     // for std::cout, std::endl
#include <string>       // for std::string
#include <vector>       // for std::vector
using namespace std;

void print(const char* name, const vector<string>& v);

int main() 
{
    // Input vectors
    vector<string> a = {"the", "of"};
    vector<string> b = {"oranges", "the", "of", "apples"};

    print("a", a);
    print("b", b);

    // Use the erase-remove idiom
    a.erase(
        remove_if(
            a.begin(), 
            a.end(), 

            // This lambda returns true if current string 's'
            // (from vector 'a') is in vector 'b'. 
            [&b](const string& s) 
            {
                auto it = find(b.begin(), b.end(), s);
                return (it != b.end());
            }
        ), 

        a.end()
    );

    cout << "\nAfter removing:\n";
    print("a", a);
}


void print(const char* name, const vector<string>& v) 
{
    cout << name << " = {";
    bool first = true;
    for (const auto& s : v) 
    {
        if (first) 
        {
            first = false;
            cout << s;
        } 
        else 
        {
            cout << ", " << s;
        }
    }
    cout << "}" << endl;
}

输出：

a = {the, of}
b = {oranges, the, of, apples}

After removing:
a = {}

使用std::set_difference()

另一种方法是使用std::set_difference()，例如以下代码：点击此处查看实时演示。
（请注意，在这种情况下，根据set_difference()的先决条件，输入向量必须已经排序。）

PS
还要注意这个在Stackoverflow上非常相似的问题。

---

#include <algorithm>    // for std::set_difference(), std::sort()
#include <iostream>     // for std::cout, std::endl
#include <iterator>     // for std::inserter
#include <string>       // for std::string
#include <vector>       // for std::vector
using namespace std;

void print(const char* name, const vector<string>& v);

int main() 
{
    // Input vectors
    vector<string> a = {"the", "of"};
    vector<string> b = {"oranges", "the", "of", "apples"};

    print("a", a);
    print("b", b);

    // Sort the vectors before calling std::set_difference().
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    // Resulting difference vector
    vector<string> c;
    set_difference(a.begin(), a.end(),
                   b.begin(), b.end(),
                   inserter(c, c.begin()));

    print("difference(a,b)", c);
}


void print(const char* name, const vector<string>& v) 
{
    cout << name << " = {";
    bool first = true;
    for (const auto& s : v) 
    {
        if (first) 
        {
            first = false;
            cout << s;
        } 
        else 
        {
            cout << ", " << s;
        }
    }
    cout << "}" << endl;
}

- Mr.C64

Answer 4

你遇到的问题是由于在迭代过程中从 a 中删除元素，但没有进行补偿。这是在编写带有删除操作的循环时常见的问题。

如果向量内容的顺序无关紧要，并且你可以将结果存储在另一个向量中，最好的方法之一是对两个向量进行排序并调用 std::set_difference。

#include <algorithm>
#include <iterator>
#include <string>
#include <vector>

int main()
{
    std::vector<std::string> a = { "the", "of" };
    std::vector<std::string> b = { "oranges", "the", "of", "apples" };
    std::vector<std::string> res;

    std::sort(a.begin(), a.end());
    std::sort(b.begin(), b.end());

    std::set_difference(a.begin(), a.end(), b.begin(), b.end(),
        std::back_inserter(res));
}

res将包含a中不在b中的所有元素，在这种情况下，b将为空。

如果顺序很重要，或者必须在原地完成，您可以使用擦除-删除惯用语。值得注意的是，对于较大的向量，这可能会更慢，因为它不可避免地是O（n ^ 2）算法。

#include <algorithm>
#include <iterator>
#include <string>
#include <vector>

struct Pred
{
    const std::vector<std::string>& filter;
    Pred(const std::vector<std::string>& x)
        :filter(x){}

    bool operator()(const std::string& str) const
    {
        return std::find(filter.begin(), filter.end(), str) != filter.end();
    }
};

int main()
{
    std::vector<std::string> a = { "the", "of" };
    std::vector<std::string> b = { "oranges", "the", "of", "apples" };

    Pred pred(b);

    a.erase(std::remove_if(a.begin(), a.end(), pred), a.end());
}

如果您没有C++11兼容的编译器，那么Pred结构体应该是一个相当不错的替代品。否则，可以使用以下lambda表达式：

auto pred = [&b](const std::string& str)
    {
        return std::find(b.begin(), b.end(), str) != b.end();
    };

- Jared Mulconry

Answer 5

这是从向量中删除元素的正确语法：

myvector.erase (myvector.begin()+5);

其次，如果你删除了它，这个向量的索引将无效。

因此，我建议你进行两轮扫描。 第一轮，标记要删除的元素。 第二轮，你可以删除它们。

顺便说一下，你的算法时间复杂度为O(n^2)。 如果可以的话，我建议你先对向量进行排序。然后你就可以使用更快的算法来处理它了。

- BufBills

---

嗯，是的。这就是我想在这里写的内容。我的错。但它只是不起作用。 - muqsitnawaz

虽然 erase 会使你的迭代器失效，但它也会返回一个新的、有效的迭代器，指向替换被删除元素的位置。来自莫斯科的 Vlad 的回答展示了这个过程是如何工作的。 - David K