How to compare a vector with an array?

Question

I would like to compare a vector with an array. Elements in the vector and in the array are in a different order, unsorted and can be duplicated. For example.

The following are the same:

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

Below is 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 the vectors and arrays have the same elements. I cannot change the vector and the array, but I can create a new container and copy the element from the vector and the array to this new container, and then copy them. I ask about this because I would like to do it in an efficient way. Thanks.

Answer 1

There are many ways to solve this problem, each of which has its pros and cons.

Some preliminary tests

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

std::unordered_multiset

You can create an unordered_multiset that contains the frequency of the elements in a range. Although it has linear complexity on average, it can be O (n ^ 2) due to hash collisions. Quote from the standard (N3337, § 23.5.7.2):

Difficulty: average random linear, worst quadratic case.

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

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

For unordered_multiset and unordered_multimap complexity of operator== 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 group of equivalent keys in a .

However, if the corresponding elements of each corresponding pair of equivalent keys of the group Eai and Ebi are arranged in the same order (which is usually the case, for example, if a and b are unmodified copies of the same container), then the average size complexity for unordered_multiset and unordered_multimap becomes proportional to N ( but in the worst case, the complexity remains O(N2) , for example, for a pathologically poor 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 can compare sorted copies of your range. According to the Standard (N3337, § 25.4.1.1), it has complexity O(n * log(n)) :

Difficulty: 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

This is an option of what is proposed in the near future:

 #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

First convert the array to vector v1.

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;