更有效的矢量比较

Question

我试图比较2个不同的向量来捕捉任何重复.一个向量是10个数字的5百万个元素,另一个是10个元素中的280万个.我的操作系统是ubuntu 18.04,我使用的是QtCreator.当我尝试比较这些大型载体时,我得到了一个挂机.这是我尝试过的:

vector<vector<int> >::iterator v1;
vector<vector<int> >::iterator v2;

for(v1 = vector1.begin(); v1 != vector1.end(); v1++)
    {
        for(v2 = vector2.begin(); v2 != vector2.end(); v2++)
        {
            if(*v1 == *v2)
            {
                vector1.erase(v1);
            }
        }
    }

当我尝试运行它并调试Qt挂起.我也想知道我是否需要更改擦除看起来像:

vector1.erase(v1.begin(), v1.end());

任何有关"更好"的方式的建议都会有所帮助.我知道这些是一些具有超过250万个10个数字元素的大向量.

Thx提前

Idzireit

仍在解决这个问题.现在我正在尝试Mark Ransom解决方案的衍生产品.这是我到目前为止所得到的:

#include "includes.h"

bool vec_less(vector<int> &v1, vector<int> &v2)
{

    for(int i = 0; i < 10; i++)
    {
        if(v1[i] == v2[i])
        {
            i++;
        }
        if(v1[i] < v2[i])
            return true;
        else
            return false;
    }
    return v1.size() <v2.size();
}

void dupfilter(vector<vector<int> > &aaperms, vector<vector<int> > &perms)
{
    vector<vector<int> >::iterator v1 = aaperms.begin();
    vector<vector<int> >::iterator v2 = perms.begin();

    while(v1 != aaperms.end() && v2 != perms.end())
    {

        if(*v1 == *v2)
        {
            aaperms.erase(v1);
            ++v1;
            ++v2;
        }

        if(vec_less(*v1, *v2) == true)
            ++v1;
        else
            ++v2;
    }

    return;
}

我只需要对1个向量进行排序.另一个按原样分类.我对附加代码的问题是现在它没有找到重复项.它确实经过了每个向量一次但由于某种原因它没有找到重复.我知道有一些因为先前的尝试并将它们排序后发现它们虽然我遇到了严重的sigseg故障.

我一直试图将我的头脑包裹在auto和unique之间,并且只是不能得到示例和我的(代码？方法？)重合.

Idzireit

Answer 1

有 二 您的解决方案有三个问题.

1. 您的代码具有未定义的行为.删除项目时,迭代器变为无效.

2. 您的代码很复杂 o(n^2) o(n^3).

3. 从矢量中间删除项具有线性复杂度,因此对于大矢量应该避免.这就是为什么我纠正了一点2.

下面的代码具有o(n)时间复杂性,使用STL算法通常是最佳选择:

using Vec = std::vector<std::vector<int>>;

void removeItems(Vec& from, const Vec& itemsToRemove)
{
    const std::unordered_set<Vec::value_type> items {
       itemsToRemove.begin(),
       itemsToRemove.end()
    };

    auto it = 
    std::remove_if(from.begin(), from.end(),
                   [&items](const auto &x){
                       return items.count(x) != 0;
                   });
    from.erase(it, from.end());
}

你可以考虑更换内部std::vector用std::array,因为你描述它有一定的大小,这将减少内存碎片(我应该提供额外的动力).

using Vec = std::vector<std::array<int, 5>>;