Removing duplicate elements from std::vector (using std::unique and std::set)














































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().
Program:

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main()
{
    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>
using namespace std;

int main()
{
    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.

More Articles of Abhishek Kumar Singh:

Name Views Likes
C++ boost::range::replace_if 956 0
C++ boost::range::copy_backward 724 1
C++ boost::range::max_element 1177 0
C++ boost::range::inplace_merge 647 0
C++ boost::range::copy 1250 1
C++ boost::algorithm::is_partitioned() 819 1
C++ boost::algorithm::copy_if() 968 0
C++ boost::range::for_each (version 2) 727 0
C++ boost::range::set_symmetric_difference 636 0
C++ boost::remove_copy_if 723 0
C++ boost::range::set_intersection 940 0
C++ boost::range::find_end 673 0
C++ boost::range::remove_erase_if 1480 0
C++ boost::range::push_back 1086 0
C++ boost::range::generate 624 0
C++ boost::algorithm::any_of() 625 0
C++ boost::range::insert 696 0
C++ boost::range::remove_erase 896 0
C++ boost::range::reverse 1165 0
C++ boost::algorithm::equal() 724 1
C++ boost::range::copy_n 804 0
C++ boost::range::random_shuffle 1218 1
C++ boost::algorithm::partition_point() 586 0
C++ boost::algorithm::one_of_equal() 508 0
C++ boost::algorithm::all_of() 857 1
C++ boost::range::merge 962 0
C++ boost::range::reverse_copy 733 0
C++ boost::range::find 716 0
C++ boost::range::fill_n 586 0
Removing duplicate elements from std::vector (using std::unique and std::set) 2126 1
C++ boost::range::equal 671 0
C++ boost::algorithm::iota() 904 0
C++ boost::range::is_sorted 819 0
test article 760 2
C++ boost::algorithm::is_permutation() 808 1
C++ boost::partial_sum 831 0
C++ boost::range::partial_sort 893 1
C++ boost::range::min_element 989 0
C++ boost::range::iota 990 0
C++ boost::range::set_union 687 0
C++ boost::algorithm::partition_copy() 1047 3
C++ boost::range::swap_ranges 592 0
C++ boost::range::for_each 857 0
C++ boost::range::upper_bound 1021 0
C++ boost::range::binary_search 1187 0
C++ boost::algorithm::all_of_equal() 528 0
C++ boost::algorithm::copy_n() 647 1
C++ boost::range::lower_bound 985 0
C++ boost::algorithm::gather() 1388 0
C++ boost::algorithm::none_of_equal() 570 0
C++ boost::algorithm::one_of() 688 2
C++ boost::range::rotate 817 0
C++ boost::algorithm::any_of_equal() 818 0
Use of Comparator in C++ 2045 0
C++ boost::range::count 785 0
C++ boost::range::replace_copy_if 610 0
C++ boost::range::remove 790 2
C++ boost::remove_if 1360 1
C++ boost::range::nth_element 1095 1
C++ boost::range::partition 715 1
C++ boost::range::erase 607 0
C++ boost::range::fill 873 1
C++ boost::range::find_if 1214 0
C++ boost::range::lexicographical_compare 781 0
C++ boost::algorithm::none_of() 559 0
C++ boost::algorithm::hex() 3331 0
C++ boost::range::replace 702 0
C++ boost::range::replace_copy 794 1
C++ boost::range::set_difference 903 0
C++ boost::range::overwrite 680 0
C++ boost::range::count_if 908 0
C++ boost::range::push_front 641 0
C++ boost::range::includes 638 0
C++ boost::algorithm::is_sorted() 667 0
C++ boost::range::remove_copy 595 1
C++ boost::algorithm::minmax_element 596 1
Deletion of leaf node of a Binary Search Tree 1653 1
Nth Fibonacci Number (Recursive Solution, Dynamic Programming, Iterative Solution 3768 1
C++ boost::range::rotate_copy 621 0

Comments