How to compare vector with array?

Question

I would like to compare vector with an array. Elements in vector and in array are in different order, unsorted and can duplicated. E.g.

Below are the same:

vector<int> lvector = {5,7,3,1,2,7};
int larray[6] = {3,5,1,7,2,7}

Below, not the same:

vector<int> lvector = {5,7,3,1,2,7,5};
int larray[7] = {3,5,1,7,2,7,3}

And something like this is also not the same:

vector<int> lvector = {1,1,1,1,2,2};
int larray[6] = {1,1,1,1,1,2}

Now I need to check if vector and array have got the same elements. I can't modify the vector and the array, but I can create a new container and copy the element from vector and array to this new container and then copare them. I am asking about this, because I would like to do this in en efficient way. Thanks.

Answer 1

There are a lot of different ways of solving this problem, each has proc and cons.

Some pre-tests

1. Obviously, two ranges cannot be equal, if they have different size.
2. You could calculate an order independent hash function for elements in the ranges (thanks, @Michael Anderson). It could be a sum of elements, or you just could xor them all. Arrays with different hash value cannot be equal.

std::unordered_multiset

You could create an unordered_multiset, which holds frequency of elements in the range. While it has linear complexity in average, it may be O(n^2) because of hash collisions. Quote from the Standard (N3337, § 23.5.7.2):

Complexity: Average case linear, worst case quadratic.

However, you should also remember the complexity of std::unordered_set::operator==:

For unordered_set and unordered_map, the complexity of operator== (i.e., the number of calls to the == operator of the value_type, to the predicate returned by key_equal(), and to the hasher returned by hash_function()) is proportional to N in the average case and to N^2 in the worst case, where N is a.size().

For unordered_multiset and unordered_multimap, the complexity of operator== is proportional to sum of Ei^2 in the average case and to N^2 in the worst case, where N is a.size(), and Ei is the size of the ith equivalent-key group in a.

However, if the respective elements of each corresponding pair of equivalent-key groups Eai and Ebi are arranged in the same order (as is commonly the case, e.g., if a and b are unmodified copies of the same container), then the average-case complexity for unordered_multiset and unordered_multimap becomes proportional to N (but worst-case complexity remains O(N2), e.g., for a pathologically bad hash function).

Example:

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


int main()
{
    std::vector<int> v{5, 7, 3, 1, 2, 7};
    int arr[] = {3, 5, 1, 7, 2, 7};

    std::unordered_multiset<int> mv(std::begin(v), std::end(v));
    std::unordered_multiset<int> ma(std::begin(arr), std::end(arr));

    std::cout << "Are equal? " << (mv == ma) << std::endl;
    return 0;
}

std::sort

You could compare sorted copies of your range. According to the Standard (N3337, § 25.4.1.1) , it has O(n * log(n)) complexity:

Complexity: O(N log(N)) (where N == last - first) comparisons.

Example:

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


int main()
{
    std::vector<int> v{5, 7, 3, 1, 2, 7};
    int arr[] = {3, 5, 1, 7, 2, 7};

    std::vector<int> sv(v);
    std::vector<int> sa(std::begin(arr), std::end(arr));

    std::sort(std::begin(sv), std::end(sv));
    std::sort(std::begin(sa), std::end(sa));

    std::cout << "Are equal? " << (sv == sa) << std::endl;
    return 0;
}

Answer 2

That's a variant of what proposed by soon:

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


int main()
{
    std::vector<int> v{5, 7, 3, 1, 2, 7};
    int arr[] = {3, 5, 1, 7, 2, 7};

    std::vector<int> mv(std::begin(v), std::end(v));
    std::vector<int> ma(std::begin(arr), std::end(arr));
    std::sort(mv.begin(), mv.end()) ;
    std::sort(ma.begin(), ma.end()) ;

    std::cout << "Are equal? " << (mv == ma) << std::endl;
    return 0;
}

Answer 3

Here is template function to compare vector with array:

#include <array>
#include <algorithm>
#include <vector>

template <class T, std::size_t N>
bool equal(const std::vector<T>& v, const std::array<T, N>& a)
{
    if (v.size() != N)
        return false;
        
    return std::equal(v.begin(), v.end(), a.begin());
}

Usage example:

std::vector<int> v = {1, 2, 3};
std::array<int, 4> a = {1, 2, 3, 4};
    
bool eq = equal(v, a);

Answer 4

At first convert the array into v1 vector.

v={1,1,2,3,4}; vector and

v1={1,1,2,3,4}; converted from array

bool f=0;
if(equal(v.begin(),v.end(),v1.begin()))  //compare two vector, if equal return true
{
    f=1;
}

}
if(f==1)
    cout<<"Yes"<<endl;
else cout<<"No"<<endl;