How to Remove Duplicates from an Unsorted Vector while Preserving Order in C ?

Keeping the Ordering in Duplicates Removal: STL Algorithms to the Rescue

When dealing with unsorted vectors, the task of removing duplicates while preserving the original ordering can be daunting. While brute-force methods like using a set to track unique elements are viable, let's explore a more elegant solution utilizing STL algorithms.

One powerful algorithm in STL is std::copy_if. It takes a predicate to filter elements, copying those that match the criteria to a new container. To apply it here, we define a NotDuplicate predicate that maintains a set of processed elements and evaluates to false if an element has been previously encountered.

Here's a simplified implementation of the NotDuplicate predicate:

struct NotDuplicate {
  bool operator()(const int& element) {
    return s_.insert(element).second;
  }
 private:
  std::set<int> s_;
};

With this predicate in hand, we can employ std::copy_if to achieve our goal:

std::vector<int> uniqueNumbers;
NotDuplicate<int> pred;
std::copy_if(numbers.begin(), numbers.end(), 
             std::back_inserter(uniqueNumbers),
             std::ref(pred));

This code iterates over the original vector, filtering elements using the NotDuplicate predicate. Elements that have not been previously encountered are copied to the uniqueNumbers vector, preserving the original ordering.

For those without C 11 support, an alternative approach involves std::remove_copy_if, which does the reverse of std::copy_if. You would invert the logic of the predicate (e.g., return true if an element has been encountered) and use std::remove_copy_if to remove duplicates:

std::vector<int> uniqueNumbers;
NotDuplicate<int> pred;
std::remove_copy_if(numbers.begin(), numbers.end(), 
             std::back_inserter(uniqueNumbers),
             std::ref(pred));

This solution offers an efficient and elegant way to remove duplicates while maintaining the original ordering, taking advantage of the versatility of STL algorithms.

The above is the detailed content of How to Remove Duplicates from an Unsorted Vector while Preserving Order in C ?. For more information, please follow other related articles on the PHP Chinese website!