CODEWITHSUNDEEP
c++algorithmstl
Oleg
Oleg

Reputation: 1097

How to compare two vectors for equality?

I have the following program:

std::vector<int> nums = {1, 2, 3, 4, 5};
std::vector<int> nums2 = {5, 4, 3, 2, 1};

bool equal = std::equal(nums.begin(), nums.end(), nums2.begin());
if (equal)
{
    cout << "Both vectors are equal" << endl;
}

There are two vectors that have equal elements. std::equal function does not work here because it goes sequentially and compares corresponding elements. Is there a way to check that both these vectors are equal and get true in my case without sorting? In real example I do not have integers but custom objects which comparing as equality of pointers.

Upvotes: 6

Views: 4029

Answers (5)

Arty
Arty

Reputation: 16747

Throwing-in one more way to solve your task, using std::sort. It also works correctly if vectors have duplicate elements (as seen from example below). It is also quite fast, O(N*Log(N)) time on average, in real life will be close in time to solutions with std::unordered_set or std::unordered_multiset.

Yes, I see that OP asked to achieve without sorting, but actually std::is_permutation is also doing sorting underneath almost for sure. And std::set does indirectly sorting too using trees. Even std::unordered_set does a kind of sorting by hash value (hash bucketing is a kind of radix sorting). So probably this task can't be solved without a kind of indirect sorting or other kind of ordering whole vector.

Try it online!

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> nums1 = {1, 2, 3, 4, 1, 5}, nums2 = {5, 4, 3, 1, 2, 1};
    std::sort(nums1.begin(), nums1.end());
    std::sort(nums2.begin(), nums2.end());
    std::cout << std::boolalpha << (nums1 == nums2) << std::endl;
}

Output:

true

Upvotes: 0

Blastfurnace
Blastfurnace

Reputation: 18652

The std::is_permutation standard library algorithm does exactly what you want. It returns true if both ranges contain the same elements in any order.

It might be slow for some applications but it only requires equality comparison and it doesn't require a temporary container or additional memory allocation.

#include <algorithm>
#include <iostream>
#include <vector>

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

    bool equal = std::is_permutation(nums.begin(), nums.end(), nums2.begin(), nums2.end());

    if (equal) {
        std::cout << "Both vectors are equal" << std::endl;
    }
}

Upvotes: 3

Adrian Mole
Adrian Mole

Reputation: 51825

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);
    }
};

Upvotes: 3

Andy Newman
Andy Newman

Reputation: 1208

If I had to invent an algorithm to do this from scratch, because for whatever reason using sets or sorts doesn't work, I would consider removing matches. This will be inefficient - it's O(n^2) - but it will work, and inefficiency is unlikely to be an issue in many cases:

bool compare(A, B)
  copy B to BB
  for each a in A
    if BB contains a
      remove a from BB
    else
      return false

  if BB is empty
    return true

  return false

Upvotes: 0

Aykhan Hagverdili
Aykhan Hagverdili

Reputation: 29975

You're looking for a set or a multiset. C++ standard library does have implementations of these data structures:

Upvotes: 0

Related Questions