How to Compare Two Vectors for Equality Element by Element in C++

How to compare two vectors for equality element by element in C++?

Check std::mismatch method of C++.

comparing vectors has been discussed on DaniWeb forum and also answered.

C++: Comparing two vectors

Check the below SO post. will helpful for you. they have achieved the same with different-2 method.

Compare two vectors C++

How to compare two vectors for equality?

You can construct a std::unordered_set from each vector, then compare those, as shown in the code snippet below:

#include <iostream>  
#include <vector>  
#include <unordered_set> 

using namespace std;

int main()
{
    std::vector<int> nums = { 1, 2, 3, 4, 5 };
    std::vector<int> nums2 = { 5, 4, 3, 2, 1 };
    std::vector<int> nums3 = { 5, 4, 9, 2, 1 };

    std::unordered_set<int> s1(nums.begin(), nums.end());
    std::unordered_set<int> s2(nums2.begin(), nums2.end());
    std::unordered_set<int> s3(nums3.begin(), nums3.end());

    if (s1 == s2) {
        std::cout << "1 and 2 are equal";
    }
    else {
        std::cout << "1 and 2 are different";
    }
    std::cout << std::endl;

    if (s1 == s3) {
        std::cout << "1 and 3 are equal";
    }
    else {
        std::cout << "1 and 3 are different";
    }
    std::cout << std::endl;

    return 0;
}

However, there are some points to bear in mind:

1. For vectors of custom type objects, you would need to provide an operator== for that type (but that would have to be done anyway, or how can you say if the two vectors have the same contents).
2. Vectors that containing duplicate entries will create sets that have those duplicates removed: Thus, {1, 2, 2, 3} will show equal to {1, 2, 3}.
3. You will also need to provide a std:hash for your custom type. For a trivial class, bob, which just wraps an integer, that hash, and the required operator==, could be defined as shown below; you can then replace the <int> specializations in the above example with <bob> and it will work. (This cppreference article explains more about the hash.)

class bob {
public:
    int data;
    bob(int arg) : data{ arg } { }
};
bool operator==(const bob& lhs, const bob& rhs)
{
    return lhs.data == rhs.data;
}
template<> struct std::hash<bob> {
    std::size_t operator()(bob const& b) const noexcept {
        return static_cast<size_t>(b.data);
    }
};

Comparing unsorted elements in two vectors

As duplicates shall not matter, you could simply insert the elements of the vectors in a separate std::set, respectively, and then compare the sets using operator ==. I think the use of sets expresses the intent of your program best:

int main() {

    vector<int> v1 =  { 1, 4, 9, 16, 9, 7, 4, 9, 11 };
    vector<int> v2 =  { 11, 11, 7, 9, 16, 4, 1 };

    set<int> s1;
    s1.insert(v1.begin(), v1.end());

    set<int> s2;
    s2.insert(v2.begin(), v2.end());

    bool isEqual = (s1 == s2);
    cout << "v1 and v2 are " << (isEqual ? "" : "not ") << "equal." << endl;

    return 0;

}

How to efficiently compare vectors with C++?

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

template <class T>
static bool compareVectors(vector<T> a, vector<T> b)
{
    std::sort(a.begin(), a.end());
    std::sort(b.begin(), b.end());
    return (a == b);
}

You'll need to include the header algorithm.

If your vectors are always of same size, you may want to add an assertion at the beginning of the method:

assert(a.size() == b.size());

This will be handy in debugging your program if you once perform this operation for unequal lengths by mistake.

Otherwise, the vectors can't be the same if they have unequal length, so just add

if ( a.size() != b.size() )
{
   return false;
}

before the sort instructions. This will save you lots of time.

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).

Can I use ' == ' to compare two vectors. I tried it and seems to be working fine. But I don't know whether it will work in more complex situations

The overload of operator == that works on two std::vectors will compare the vector sizes and return false if those are different; if not, it will compare the contents of the vector element-by-element.

If operator == is defined for the vector's element type, then the comparison of vectors through operator == is valid and meaningful.

In formal terms, the C++11 standard specifies the operational semantics of a == b for sequence containers as (Table 96, § 23.2.1):

== is an equivalence
relation.

distance(a.begin(), a.end()) == distance(b.begin(), b.end()) && equal(a.begin(), a.end(), b.begin())

As you can see, equality between sequence containers is defined in terms of the std::equal algorithm between ranges defined by pairs of iterators, which in turn uses operator == for comparison of individual elements.

What's the FASTEST way to compare vectors in C++?

Simply use operator == of vector:

std::vector<int> v1{1, 2, 3, 4}, v2{1, 2, 3, 4};
bool are_equal = (v1 == v2);

How to efficiently compare two vectors in C++, whose content can't be meaningfully sorted?

If the elements can be hashed in some meaningful way, you can get expected O(n) performance by using a hashmap: Insert all elements from list A into the hashmap, and for each element in list B, check if it exists in the hashmap.

In C++, I believe that unordered_map is the standard hashmap implementation (though I haven't used it myself).

Comparing two arrays in C, element by element

Your best bet is to rewrite it as a function that returns true or false (1 or 0):

int compareArrays(double a[], double b[], int n) {
  int ii;
  for(ii = 1; ii <= n; ii++) {
    if (a[ii] != b[ii]) return 0;
    // better:
    // if(fabs(a[ii]-b[ii]) < 1e-10 * (fabs(a[ii]) + fabs(b[ii]))) {
    // with the appropriate tolerance
  }
  return 1;
}

Note that it is usually bad practice to compare doubles for equality - you are better off comparing their difference, and making sure the absolute value is less than some tolerance.

Also note you are comparing elements 1 through n - C arrays start at 0 though.

You would use the above with

if (compareArrays(a, a_tmp, N)) {

where the value N is #define'd per your question.

If you want to be "clever" and avoid a loop, you can write the following - it will stop ("short-circuiting") as soon as you reach the right number of comparisons. It is still a Bad Idea to compare doubles for equality but I will leave that for another time (see comment in code above for a solution).

if(a[1]==a_temp[1] && (2 > N || (a[2]==a_temp[2] && (3 > N || (a[3]==a_temp[3]))))) {

This makes the "and the rest" true as soon as you have compared the right number of terms - so it will stop evaluating terms (as you need). I am not convinced this is either faster, or better code - but it is "dynamic"... You can obviously make this expression as long as you would like; I just wrote the first three terms so you get the idea. I DO NOT RECOMMEND IT.

As for the comparison of doubles, you might consider replacing

if(a == b)

with

if(closeEnough(a, b))

where you define the macro

#define closeEnough(a, b) (fabs((a)-(b)) < 1e-10 * (fabs(a) + fabs(b)))? 1 : 0

This will make sure that your doubles don't have to be "exactly equal" - depending on how you arrived at them, they will almost never be, and the relative tolerance of 1 part in 10^10 is usually plenty for most practical comparisons.

---

Related Topics