How to quickly check if two vectors have equal values

Question:

The number of elements reaches 100000 and I have to compare it with another vector of 100000, how can I do this with a very high performance gain

How I'm comparing the vectors

for(i = 0; i < teste; i++)
{
    for(j = 0; j < teste; j++)
    {
        if(indice[i] == aux[j])
        {
            cont++;
        }
    }
}

Answer:

You can try creating a hash array, for example

char hash[0x7FFFFFFF];

if any positive integers are possible.

Initialize the vector,

for (int i = 0; i < 0x7FFFFFFF; ++i)
{
    hash[i] = 0;
}

Iterate over one of your original vectors and use the hash to know that that number exists in this vector:

for (int i = 0; i < teste; ++i)
{
    hash[indice[i]] = 1;
}

Then iterate over the second vector, incrementing cont if the hash is already filled,

for (int i = 0; i < teste; ++i)
{
    if (hash[aux[i]])
    {
        ++cont;
    }
}

That way the complexity becomes O(n), instead of O(n^2), which was your case.

The problem now is that too much RAM is used. 1GB RAM minimum, just for the hash vector…

So there is a tradeoff between algorithmic complexity and spatial complexity, which must always be taken into account.