Iterator and Range-Based Algorithms

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

How do I remove duplicates from a sorted vector in C++?

Abstract art representing computer programming

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:

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
  std::vector<int> numbers{1, 2, 2, 3, 4, 4, 5};

  // Removing duplicates
  auto new_end = std::unique(numbers.begin(),
    numbers.end());  

  // Resizing the vector
  numbers.erase(new_end, numbers.end());

  // Printing the result
  for (const int& num : numbers) {
    std::cout << num << " ";
  }
}
1 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(nlogn)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:

std::sort(numbers.begin(), numbers.end());
auto new_end = std::unique(numbers.begin(),
  numbers.end());
numbers.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.

Answers to questions are automatically generated and may not have been reviewed.

Free, Unlimited Access

Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

Screenshot from Warhammer: Total War
Screenshot from Tomb Raider
Screenshot from Jedi: Fallen Order
Contact|Privacy Policy|Terms of Use
Copyright © 2024 - All Rights Reserved