c++11 - How to efficiently compare vectors with C++?

Question

I need advice for micro optimization in C++ for a vector comparison function, it compares two vectors for equality and order of elements does not matter.

template <class T>
static bool compareVectors(const vector<T> &a, const vector<T> &b)
{
  int n = a.size();
  std::vector<bool> free(n, true);
  for (int i = 0; i < n; i++) {
    bool matchFound = false;
    for (int j = 0; j < n; j++) {
      if (free[j] && a[i] == b[j]) {
        matchFound = true;
        free[j] = false;
        break;
      }
    }
    if (!matchFound) return false;
  }
  return true;
}

This function is used heavily and I am thinking of possible way to optimize it. Can you please give me some suggestions? By the way I use C++11.

Thanks

Answer 1

Your can probabilistically compare two unsorted vectors (u,v) in O(n):

Calculate:

U= xor(h(u[0]), h(u[1]), ..., h(u[n-1]))
V= xor(h(v[0]), h(v[1]), ..., h(v[n-1]))

If U==V then the vectors are probably equal.

h(x) is any non-cryptographic hash function - such as MurmurHash. (Cryptographic functions would work as well but would usually be slower).

(This would work even without hashing, but it would be much less robust when the values have a relatively small range).

A 128-bit hash function would be good enough for many practical applications.