Check if two vectors contains the same elements in C++
This post will discuss how to check if two vectors contain the same elements in C++. The solution should compare two vectors for equality, ignoring the order.
1. Using std::sort
The idea is to sort both vectors and compare them using the == operator (or std::equal). The == operator checks whether the contents of both vectors are the same or not. The time complexity of this solution is O(n*log(n)), where n is the size of the vector.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
#include <iostream> #include <vector> #include <algorithm> template<typename T> bool isEqual(std::vector<T> &first, std::vector<T> &second) { if (first.size() != second.size()) { return false; } std::sort(first.begin(), first.end()); std::sort(second.begin(), second.end()); return first == second; } int main() { std::vector<int> first = {1, 2, 3}; std::vector<int> second = {3, 1, 2}; std::cout << std::boolalpha << isEqual(first, second) << std::endl; return 0; } |
2. Using std::is_permutation
Another viable alternative is to use the std::is_permutation function, which checks whether the specified range is a permutation of another range. This function is introduced with C++11 and performs at most O(n2) comparisons.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
#include <iostream> #include <vector> #include <algorithm> template<typename T> bool isEqual(std::vector<T> &first, std::vector<T> &second) { if (first.size() != second.size()) { return false; } return std::is_permutation(first.begin(), first.end(), second.begin()); } int main() { std::vector<int> first = {1, 2, 3}; std::vector<int> second = {3, 1, 2}; std::cout << std::boolalpha << isEqual(first, second) << std::endl; return 0; } |
Alternatively, we can use the boost::algorithm::is_permutation function from the boost library. It checks if a sequence is a permutation of another one, i.e., it contains all the same elements in the same or different order.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
#include <iostream> #include <vector> #include <boost/algorithm/cxx11/is_permutation.hpp> template<typename T> bool isEqual(std::vector<T> &first, std::vector<T> &second) { if (first.size() != second.size()) { return false; } return boost::algorithm::is_permutation(first.begin(), first.end(), second.begin()); } int main() { std::vector<int> first = {1, 2, 3}; std::vector<int> second = {3, 1, 2}; std::cout << std::boolalpha << isEqual(first, second) << std::endl; return 0; } |
3. Using std::unordered_multiset
Finally, we can construct a multiset from each vector, and compare them for equality using the == operator. Since a set eliminates duplicates, a multiset should be used.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
#include <iostream> #include <vector> #include <unordered_set> template<typename T> bool isEqual(std::vector<T> &first, std::vector<T> &second) { if (first.size() != second.size()) { return false; } std::unordered_multiset<int> s1(first.begin(), first.end()); std::unordered_multiset<int> s2(second.begin(), second.end()); return s1 == s2; } int main() { std::vector<int> first = {1, 1, 2, 3}; std::vector<int> second = {3, 1, 2, 1}; std::cout << std::boolalpha << isEqual(first, second) << std::endl; return 0; } |
That’s all about checking if two vectors contain the same elements in C++.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)