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.

Patmos

You should attempt it first and then when you run into problems, come and ask your specific question with the basis of your code as a jumping point for StackOverflow to assist in answering your question. – Bosk

Fortunately, the C++ standard library have many algorithmic functions that can be used, for example to check equality between two ranges (though it requires both ranges to be in the same order). You could also use std::all_of with a custom predicate to find all value from one container in the other. – Persecution

std::equal works when the elements in vector are unsorted: {5,7,3,1,2,7}? – Patmos

@DekodererDekoderer It works if both containers are in the same order, and also size. If yours aren't then please read my (edited) comment again, and follow the links. – Persecution

By the way, you are aware that you declare larray as an array of five elements, but try to initialize it with six? – Persecution

Thanks. Of course it should be 6 - my mistake. – Patmos

You could just remove the size from brackets - it will be calculated automatically. – Cain

Is there any reason not to sort both and then compare? – Goniometer

@Boris - from the post I can't modify the vector and the array – Demimondaine

@MichaelAnderson From the post: but I can create a new container and copy the element from vector and array to this new container and then copare them – Goniometer

You can reduce unequal cases by sum each elements of vector (or calculate length of vector) . Sum(lv) = {1,1,1,1,2,2} = 1 + 1 + 1 + 1 + 2 + 2 = 8 > Sum(array) – Omland

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

Cain

If you care about speed there's a couple of improvements that nicely sit above this. 1. If they have different lengths then they can't be equal. 2. If they have different sums (or bitwise xors, or products, etc) they cant be equal. These can be big gains since these tests are O(n) while the construction of the multiset is O(n log(n)) – Demimondaine

i.e. you should use the cheep O(n) and O(1) tests to rule out cases where they can never be equal before you bother constructing the multisets. – Demimondaine

@Michael: This is O(n) too. You're thinking multiset, not unordered_multiset. – Countermarch

@Hurkyl - you may be right (can't find the reference for that) - but either way scanning and operating on the lists is likely to be significantly faster than constructing another data structure. – Demimondaine

@MichaelAnderson, Yes, you are right, thank you. I'm just looking at the standard for the complexity of constructing std::unorederd_multiset, which should be O(n). As soon as I find, I will update the answer with reference to your suggestions. – Cain

Using vector means better use of cache. – Patmos

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

Intercurrent

It's good solution, but it will take time complexity O(nlogn) - because of sorting. Maybe there is faster solution like unordered_multiset, or map. – Patmos

Are the other soution faster? For map you have an O(nlogn) build time, while unordered_multiset is faster to build but slower to compare (at least according to cppreference.com) – Intercurrent

@DekodererDekoderer You need to profile different solutions with realistic array sizes. multiset and unordered_multiset will result in more dynamic allocations so are not necessarily "faster" (beware of confusing complexity with speed.) – Maureenmaureene

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

Swec

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;

Condign

No need to convert. You can call std::begin on an array. – Sturdivant