How can you efficiently compare two std::vectors for equality, ignoring the order of elements?

c++, c++11, stdvector

Solution

It just realized that this code only does kind of a "set equivalency" check (and now I see that you actually did say that, what a lousy reader I am!). This can be achieved much simpler

#include <algorithm> // for std::sort

template <class T>
bool compareVectors(vector<T> a, vector<T> b)
{
    // alternatively, assert(a.size() == b.size());
    // (if you expect the vectors to be the same length)
    if (a.size() != b.size())
    {   // this test saves a lot of time and means we don't need to sort
        return false; 
    }
    // or, in C++20, std::ranges::sort(a);
    std::sort(a.begin(), a.end());
    std::sort(b.begin(), b.end());
    return (a == b);
}

The complexity of this technically is `O(n*log(n))` because it's mainly dependent on the sorting which (usually) is of that complexity. This is better than your `O(n^2)` approach, but might be worse due to the needed copies. This is irrelevant if your original vectors may be sorted.

If you want to stick with your approach, but tweak it, here are my thoughts on this:

You can use `std::find` for this:

template <class T>
static bool compareVectors(const vector<T> &a, const vector<T> &b)
{
  const size_t n = a.size(); // make it const and unsigned!
  std::vector<bool> free(n, true);
  for ( size_t i = 0; i < n; ++i )
  {
      bool matchFound = false;
      auto start = b.cbegin();
      while ( true )
      {
          const auto position = std::find(start, b.cend(), a[i]);
          if ( position == b.cend() )
          {
              break; // nothing found
          }
          const auto index = position - b.cbegin();
          if ( free[index] )
          {
             // free pair found
             free[index] = false;
             matchFound = true;
             break;
          }
          else
          {
             start = position + 1; // search in the rest
          }
      }
      if ( !matchFound )
      {
         return false;
      }
   }
   return true;
}

Another possibility is replacing the structure to store free positions. You may try a `std::bitset` or just store the used indices in a vector and check if a match isn't in that index-vector. If the outcome of this function is very often the same (so either mostly true or mostly false) you can optimize your data structures to reflect that. E.g. I'd use the list of used indices if the outcome is usually false since only a handful of indices might needed to be stored.

This method has the same complexity as your approach. Using std::find to search for things is sometimes better than a manual search. (E.g. if the data is sorted and the compiler knows about it, this can be a binary search).

Problem

Original source