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

问题描述 投票：3回答：5

假设我有一个vector a = {"the", "of"}和一个vector 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中的最后一个元素。奇怪的！

c++ vector erase
5个回答
7
投票

问题是当你删除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”，留下“橘子”和“苹果”。

5
投票

请尝试以下方法

#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() );
}

当然，如果要对矢量进行排序会更好。

1
投票

一般情况下，我建议使用STL已经构建的算法，并将它们正确组合，而不是“手动”遍历矢量内容并选择性地删除它的项目。

使用擦除删除成语

特别是，要从std::vector中删除满足某些属性的项目，您可以考虑使用erase-remove惯用法。 This Q&A on Stackoverflow讨论了从STL容器中删除项目的一些选项，包括std::vector案例。

你可以在下面找到评论的可编辑代码，live here：

#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 = {}

PS 另请注意this very similar question on Stackoverflow。

使用std::set_difference()

另一种方法可以是使用std::set_difference()，例如像下面的代码，live here。 （请注意，在这种情况下，根据set_difference()先决条件，输入向量必须已经排序。）

#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;
}
1
投票

你遇到的问题是因为当你在迭代它时从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元素，在这种情况下将为空。

如果订单很重要，或者必须在适当的位置完成，您可以使用擦除删除习惯用法。值得一提的是，对于较大的向量，这可能会更慢，因为它不可避免地是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来说应该是一个相当不错的替身。否则，这个lambda将完成这项工作：

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

这是从矢量中删除东西的正确语法：

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

其次，在删除它之后，此向量的索引将无效。

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

BTW你的算法是O（n ^ 2）时间复杂度。如果可以，我建议您先对矢量进行排序。然后你可以使用更快的算法来处理它。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.