How to Remove Duplicates from a Sorted Vector in C++

Removing duplicates from a sorted vector in C++ can be efficiently achieved using the std::unique() algorithm from the <algorithm> header.

The std::unique() function removes consecutive duplicate elements and returns an iterator to the new end of the range.

After using std::unique(), you need to resize the vector to remove the extra elements.

Here’s how you can do it:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector<int> numbers{1, 2, 2, 3, 4, 4, 5};
7
8  // Removing duplicates
9  auto new_end = std::unique(numbers.begin(),
10    numbers.end());  
11
12  // Resizing the vector
13  numbers.erase(new_end, numbers.end());
14
15  // Printing the result
16  for (const int& num : numbers) {
17    std::cout << num << " ";
18  }
19}

11 2 3 4 5

How It Works

• Including the Header: You need to include the <algorithm> header to access the std::unique() function.
• Using std::unique(): The std::unique() function modifies the vector in-place and removes consecutive duplicates. It returns an iterator pointing to the element that should be considered the new end of the vector.
• Resizing the Vector: After calling std::unique(), the vector still contains the old elements beyond the new logical end. You must call erase() to remove these elements physically.

Practical Considerations

• Sorted Vector Requirement: The vector must be sorted before calling std::unique() for this method to work correctly. If the vector is not sorted, you can sort it using std::sort().
• Efficiency: This method is efficient because it operates in linear time relative to the number of elements in the vector. Sorting the vector, if needed, takes $O(n log n)$ time.

Additional Tips

Combining Steps: If the vector is not already sorted, you can combine the steps of sorting and removing duplicates:

1std::sort(numbers.begin(), numbers.end());
2auto new_end = std::unique(numbers.begin(),
3  numbers.end());
4numbers.erase(new_end, numbers.end());

Using with Custom Types: If you are working with a vector of custom objects, ensure your type supports equality comparison or provide a custom comparator to std::unique().

Removing duplicates from a sorted vector is a common task in C++, and using std::unique() along with std::erase() provides a clean and efficient solution.