Removing duplicate elements from std::vector (using std::unique and std::set)
Description:
In this article we shall understand various methods of removing duplicate values from a std::vector.
Example:
Input: 10 9 8 10 8 11 6 9 4 11 6
The first line of input is number of array elements n, and the next line consist of n array elements ai.
Output:
4 6 8 9 10 11
The output consist of all the unique elements of the vector in sorted order.
Method 1: (using std: :unique())
In this method we shall use the unique() method of standard library of C++. The unique(iterator 1, iterator 2) function takes two iterators as parameter and shifts the duplicate element present adjacently to each other at the end of the vector. Please note that unique() will only work on a sorted vector (because sorted list will have same elements adjacent to each other). The unique() returns the last position of the vector till where it has no duplicate elements. We can then resize the vector to the returned iterator of unique().
intmain() { int n; cin >> n; vector<int> A(n); for(int i = 0; i < n; i++) cin >> A[i];
sort(A.begin(), A.end()); // Sorting the entire array auto iter = unique(A.begin(), A.end()); // returns an iterator to the element that follows the last element not removed A.resize(distance(A.begin(), iter)); // distance returns number of elements between two iterator
for(int i = 0; i < A.size(); i++) cout << A[i] << " ";
}
Complexity: Time Complexity: The above program will take O(n logn) time complexity for sorting because sort() function in C++ is implemented using quick-sort which has average time complexity of O(n logn).
Space Complexity: The space complexity for the above program is O(n) for storing array elements.
Method 2: (using std: :set)
In this method is pretty straight-forward. We shall iterate over all the elements of the vector and store them in std::set data-structure. As we know set data-structure is implemented using red-black tree so it prevents storing of duplicate values. Program: #include<iostream> #include<vector> #include<set> usingnamespacestd;
intmain() { int n; cin >> n; vector<int> A(n); for(int i = 0; i < n; i++) cin >> A[i];
set<int> S; for(int i = 0; i < n; i++) S.insert(A[i]);
for(auto it = S.begin(); it != S.end(); it++) cout << *it << " "; }
Complexity: Time Complexity: The above program will take O(n logn) time complexity because insert operation in set takes O(log n) time and hence n elements take O(nlog n) time.
Space Complexity: The above program takes O(n) extra space for storing elements in set as well as vector when all elements of the vector are already unique.
Please write on comment section if you find any mistake or for any suggestions.
Comments