Removal Algorithms

Efficiently Remove Duplicates

How do I efficiently remove duplicate elements from a container using std::ranges::remove()?

Abstract art representing computer programming

To efficiently remove duplicate elements from a container using std::ranges::remove(), you need to first ensure the container is sorted.

This is because std::ranges::remove() works on contiguous elements and duplicates must be adjacent for this to work effectively.

Here's a step-by-step guide:

  1. Sort the container to bring duplicate elements next to each other.
  2. Use std::ranges::remove() to shift the duplicates to the end.
  3. Use the erase() method to remove the surplus elements.

Here's an example using a std::vector:

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

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

  // Step 1: Sort the container
  std::sort(Source.begin(), Source.end());

  // Step 2: Apply std::ranges::remove to shift duplicates
  auto NewEnd = std::ranges::unique(Source);

  // Step 3: Erase surplus elements
  Source.erase(NewEnd.begin(), NewEnd.end());

  // Display the result
  std::cout << "Unique elements in Source: ";
  for (auto Num : Source) {
    std::cout << Num << ", ";
  }
}
Unique elements in Source: 1, 2, 3, 4, 5,

In this example:

  • We first sort the Source vector to arrange the elements in ascending order.
  • We then use std::ranges::unique() to move the duplicate elements to the end. Note that std::ranges::unique() is more suitable for this task than std::ranges::remove(), as it directly deals with adjacent duplicates.
  • Finally, we erase the surplus elements to resize the container.

Using std::ranges::remove_if() for Complex Conditions

If you need to remove duplicates based on a more complex condition (e.g., user-defined types), you can use std::ranges::remove_if() in combination with sorting:

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

struct Player {
  std::string Name;
  int Score;

  bool operator<(const Player& other) const {
    return Score < other.Score;  // Sort by Score
  }
};

int main() {
  std::vector<Player> Players{
    {"Alice", 10}, {"Bob", 20},
    {"Charlie", 10}, {"Diana", 20},
    {"Eve", 30}
  };

  // Step 1: Sort the container
  std::sort(Players.begin(), Players.end());

  // Step 2: Apply std::ranges::unique to shift duplicates
  auto NewEnd = std::ranges::unique(
    Players,
    [](const Player& a, const Player& b) {
      return a.Score == b.Score;
    }
  );

  // Step 3: Erase surplus elements
  Players.erase(NewEnd.begin(), NewEnd.end());

  // Display the result
  std::cout << "Unique players by score:\n";
  for (const auto& player : Players) {
    std::cout << player.Name << " (Score "
      << player.Score << ")\n";
  }
}
Unique players by score:
Alice (Score 10)
Bob (Score 20)
Eve (Score 30)

In this example:

  • We define a custom comparison operator for sorting Player objects by their Score.
  • We use std::ranges::unique() with a custom predicate to handle duplicates based on the Score.
  • The erase() method removes the surplus elements, resulting in a container with unique scores.

By sorting the container and using std::ranges::unique(), you can efficiently remove duplicates and maintain a clean, unique set of elements.

This Question is from the Lesson:

Removal Algorithms

An overview of the key C++ standard library algorithms for removing objects from containers. We cover remove(), remove_if(), remove_copy(), and remove_copy_if().

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

This Question is from the Lesson:

Removal Algorithms

An overview of the key C++ standard library algorithms for removing objects from containers. We cover remove(), remove_if(), remove_copy(), and remove_copy_if().

A computer programmer
Part of the course:

Professional C++

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

Free, unlimited access

This course includes:

  • 124 Lessons
  • 550+ Code Samples
  • 96% Positive Reviews
  • Regularly Updated
  • Help and FAQ
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