8 Key Standard Library Algorithms

Removing Duplicates from a Range

What is the most efficient way to remove duplicates from a range using standard algorithms?

Abstract art representing computer programming

To remove duplicates from a range using standard algorithms, you can use a combination of std::ranges::sort() and std::ranges::unique().

This approach ensures that the range is first sorted, which is a prerequisite for std::ranges::unique() to work correctly.

Here is an example demonstrating this process:

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

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

  // Sort the range first
  std::ranges::sort(numbers);

  // Remove duplicates
  auto last = std::ranges::unique(numbers);
  numbers.erase(last.begin(), numbers.end());  

  for (int n : numbers) {
    std::cout << n << ", ";
  }
}
1, 2, 3, 5, 8,

In this example:

  1. std::ranges::sort(numbers) sorts the elements in the numbers vector.
  2. std::ranges::unique(numbers) rearranges the elements such that each unique element appears only once, and returns a subrange of the unique elements.
  3. numbers.erase(last.begin(), numbers.end()) removes the duplicate elements from the vector.

This approach is efficient and leverages the power of the C++ standard library's range algorithms.

Alternatively, you can use a std::set to remove duplicates, which automatically handles uniqueness but does not preserve the original order:

#include <iostream>
#include <set>
#include <vector>

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

  // Use a set to remove duplicates
  std::set<int> unique_numbers(
    numbers.begin(), numbers.end());

  for (int n : unique_numbers) {
    std::cout << n << ", ";
  }
}
1, 2, 3, 5, 8,

Using a std::set is straightforward but does not maintain the original order of elements. If preserving order is important, you should use the std::ranges::sort() and std::ranges::unique() approach.

For better performance, especially with large datasets, the sorting and unique algorithms are generally preferred as they are optimized for such operations in the standard library.

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