Remove duplicates from a vector in C++
This post will discuss how to remove duplicates from a vector in C++.
1. Using std::remove function
A simple solution is to iterate the vector, and for each element, we delete all its duplicates from the vector if present. We can either write our own routine for this or use the std::remove algorithm that makes our code elegant. This approach takes constant space but runs in O(n2) time.
|
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> void remove(std::vector<int> &v) { auto end = v.end(); for (auto it = v.begin(); it != end; ++it) { end = std::remove(it + 1, end, *it); } v.erase(end, v.end()); } int main() { std::vector<int> v = { 5, 2, 1, 3, 4, 2, 2, 4, 5, 5, 6 }; remove(v); for (auto it = v.cbegin(); it != v.cend(); ++it) { std::cout << *it << ' '; } return 0; } |
Output:
5 2 1 3 4
2. Using std::unordered_set function
Here, the idea is to iterate over the vector and keep track of visited elements in a set. If an element is not seen before, we insert it again into the vector at the next available position from the beginning.
This approach needs additional storage for set data structure and runs in O(n) time if std::unordered_set is used over std::set.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
void remove(std::vector<int> &v) { std::vector<int>::iterator itr = v.begin(); std::unordered_set<int> s; for (auto curr = v.begin(); curr != v.end(); ++curr) { if (s.insert(*curr).second) { *itr++ = *curr; } } v.erase(itr, v.end()); } |
Here’s another solution that uses a set. The idea is to insert all vector elements in a set and copy the set’s contents back again into the vector. This works as inserting elements into the set removes all duplicates as all set elements must be distinct. Please note that this might change the original ordering of elements in the vector.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
#include <iostream> #include <vector> #include <unordered_set> int main() { std::vector<int> v = { 5, 2, 1, 3, 4, 2, 2, 4, 5, 5 }; std::unordered_set<int> s(v.begin(), v.end()); v.assign(s.begin(), s.end()); for (auto it = v.cbegin(); it != v.cend(); ++it) { std::cout << *it << ' '; } return 0; } |
Output:
4 3 1 2 5
3. Using std::remove_if with std::unordered_set function
Another efficient solution is to use std::remove_if with std::unordered_set.
The end logic remains similar to the previous solution, where we iterate over the vector and keep track of visited elements in a set. And if the element is not seen before, we insert it again into the vector at the next available position from the beginning.
Notice that the std::remove_if algorithm has no knowledge of the underlying container. It does not actually remove elements from the container but move all safe elements to the front and returns an iterator pointing to where the end should be, so they can be deleted using a single call to std::erase. This technique is commonly known as the Erase-remove idiom.
|
1 2 3 4 5 6 7 8 9 10 |
void remove(std::vector<int> &v) { std::unordered_set<int> s; auto end = std::remove_if(v.begin(), v.end(), [&s](int const &i) { return !s.insert(i).second; }); v.erase(end, v.end()); } |
4. Using std::copy_if with std::unordered_set function
Here’s how we can achieve the same by using the std::copy_if algorithm. This will work with C++11 and above.
|
1 2 3 4 5 6 7 8 9 10 |
void remove(std::vector<int> &v) { std::unordered_set<int> s; auto end = std::copy_if(v.begin(), v.end(), v.begin(), [&s](int const &i) { return s.insert(i).second; }); v.erase(end, v.end()); } |
Output:
5 2 1 3 4
5. Using std::remove_copy_if with std::unordered_set function
The std::remove_copy_if algorithm will also work, as shown below:
|
1 2 3 4 5 6 7 8 9 |
void remove(std::vector<int> &v) { std::unordered_set<int> s; auto end = std::remove_copy_if(v.begin(), v.end(), v.begin(), [&s](int const &i) { return !s.insert(i).second; }); v.erase(end, v.end()); } |
6. Using std::sort with std::unique function
Finally, we can also sort the vector and call std::unique, which removes the duplicate consecutive elements. This works but doesn’t preserve the original ordering of elements. This approach takes constant space but runs in O(n.log(n)) time.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
#include <iostream> #include <vector> #include <algorithm> #include <unordered_set> int main() { std::vector<int> v = { 5, 2, 1, 3, 4, 2, 2, 4, 5, 5 }; std::sort(v.begin(), v.end()); v.erase(std::unique(v.begin(), v.end()), v.end()); for (auto it = v.cbegin(); it != v.cend(); ++it) { std::cout << *it << ' '; } return 0; } |
Output:
1 2 3 4 5
That’s all about removing duplicates from 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 :)