Find all duplicates present in a vector in C++
This post will discuss how to find all duplicates present in a vector in C++.
1. Using std::set_difference
To find duplicates present in a vector, we can find the set difference between the original elements and the distinct elements. The following code example demonstrates this using the standard algorithm std::set_difference. It constructs a sorted range with the set difference of the specified sorted ranges.
|
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 27 |
#include <iostream> #include <vector> #include <algorithm> #include <set> template<typename T> std::set<T> findDuplicates(std::vector<T> vec) // no-ref, no-const { std::set<int> duplicates; std::sort(vec.begin(), vec.end()); std::set<int> distinct(vec.begin(), vec.end()); std::set_difference(vec.begin(), vec.end(), distinct.begin(), distinct.end(), std::inserter(duplicates, duplicates.end())); return duplicates; } int main() { std::vector<int> vec = {2, 2, 4, 1, 3, 6, 6, 7, 6, 8}; std::set<int> duplicates = findDuplicates(vec); for (auto &i: duplicates) { std::cout << i << ' '; } return 0; } |
Output:
2 6
2. Using Set
Another option is to traverse the vector and keep a record of all the seen elements in a Set. If any element is already present in the Set, then it must be a duplicate. This logic would translate to the following C++ code:
|
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 27 28 29 30 |
#include <iostream> #include <vector> #include <algorithm> #include <unordered_set> template<typename T> std::unordered_set<T> findDuplicates(std::vector<T> const &vec) { std::unordered_set<int> seen; std::unordered_set<int> duplicates; for (int i: vec) { if (seen.find(i) != seen.end()) { duplicates.insert(i); } seen.insert(i); } return duplicates; } int main() { std::vector<int> vec = {2, 2, 4, 1, 3, 6, 6, 7, 6, 8}; std::unordered_set<int> duplicates = findDuplicates(vec); for (auto &i: duplicates) { std::cout << i << ' '; } return 0; } |
Output:
6 2
3. Using frequency map
Alternatively, we can create a frequency map and filter all keys having their value greater than 1. This can be implemented as follows in C++.
|
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 27 28 29 30 31 32 33 34 35 |
#include <iostream> #include <vector> #include <algorithm> #include <unordered_set> #include <unordered_map> template<typename T> std::unordered_set<T> findDuplicates(std::vector<T> const &vec) { std::unordered_map<int, int> freq; for (T const &i: vec) { freq[i]++; } std::unordered_set<int> duplicates; for (auto const &pair: freq) { if (pair.second > 1) { duplicates.insert(pair.first); } } return duplicates; } int main() { std::vector<int> vec = {2, 2, 4, 1, 3, 6, 6, 7, 6, 8}; std::unordered_set<int> duplicates = findDuplicates(vec); for (auto &i: duplicates) { std::cout << i << ' '; } return 0; } |
Output:
2 6
That’s all about finding all duplicates present in a vector 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 :)