In C++, vector is a sequential template class, part of STL(Standard Template Library). A vector in C++ is a resizable array because it can change its size either by growing or shrinking when an element is added or removed from the vector, respectively. Hence, it is also called a dynamic array because of its property of growing and shrinking in size as the element is added or removed from it.

In this article, we will learn how to erase duplicates and sort a vector in C++.

Example:

Input:
my_vector = {1, 3, 1, 4, 4, 6, 5, 6, 6}

Output:
my_vector = {1, 3, 4, 5, 6}

In the example given above, the input my_vector contains 1, 4, and 6 as duplicate elements. So, our main aim would be to remove them from my_vector and modify my_vector such that it contains the unique elements. It means that every element given in the input vector must appear only once in the output of my_vector vector.

Ways to Erase Duplicate Elements and Sort a Vector

There are two efficient approaches to erase duplicates and sort the vector in C++:

1. Erase Duplicate Elements and Sort Vector Using std::unique

In C++, the std::unique() function is declared in the <algorithm> header.  This function transfers all the consecutive duplicate elements in a vector to the end of the vector. We can then use the std::erase() function to remove the duplicate part.

In sorted vector, all the duplicate elements are consecutive to each other. Therefore, sorting the vector before using the std::unique will work as we want. We can sort the vector using std::sort().

Syntax of std::unique()

unique(first, last);

Syntax of std::sort()

sort(first, last);

Syntax of std::erase()

erase(first, last);

Example

// C++ Program to illustrate how to erase all the duplicates
// and sort the vector using unique, erase and sort functions
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    vector<int> my_vector = { 1, 3, 1, 4, 4, 6, 5, 6, 6 };

    // sort the input vector
    sort(my_vector.begin(), my_vector.end());

    // using unique funtion
    auto it = unique(my_vector.begin(), my_vector.end());

    // Remove duplicates elements beyond it iterator
    my_vector.erase(it, my_vector.end());

    std::cout << "Vector after removing duplicates: ";
    for (int item : my_vector) {
        cout << item << " ";
    }

    return 0;
}

Vector after removing duplicates: 1 3 4 5 6 

Time Complexity: O(n logn), where n is the number of elements
Space Complexity: O(1)

2. Erase Duplicate Elements and Sort Vector Using a Set

In C++, sets contain unique elements in some defined order. So, we can place all the elements of the input vector in a set. This will ensure that all the elements in the set have unique occurrences(without duplicate occurrences) and will be in the given order. Then, we can replace all the input vector values with the values inside the set.

Example

// C++ Program to illustrate how to erase all the duplicates
// and sort the vector using set container
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    vector<int> my_vector = { 1, 3, 1, 4, 4, 6, 5, 6, 6 };

    // sort the input vector
    sort(my_vector.begin(), my_vector.end());

    for (int i = 1; i < my_vector.size(); ++i) {
        if (my_vector[i] == my_vector[i - 1]) {
            my_vector.erase(my_vector.begin() + i);
            --i;
        }
    }

    std::cout << "Vector after removing duplicates: ";
    for (int item : my_vector) {
        cout << item << " ";
    }

    return 0;
}

Vector after removing duplicates: 1 3 4 5 6 

Time Complexity: O(n logn), where n is the number of elements
Space Complexity: O(n)