How to Remove Duplicates from an Unsorted Array While Maintaining Insertion Order Using STL Algorithms?

STL Algorithms for Duplicate Removal with Order Preservation

Given an array of unsorted integers, the task is to remove duplicate elements while preserving the insertion order of the first occurrence of each integer. While a straightforward approach using a set can achieve this, an optimized solution leveraging STL algorithms offers a more efficient and elegant solution.

STL Algorithm-Based Approach

STL provides several algorithms that facilitate efficient manipulation of containers. One such algorithm is std::copy_if. This algorithm can be utilized to create a new vector containing unique elements while maintaining their original order.

To implement this solution, define a predicate function that keeps track of previously encountered elements and returns false if an element has already been processed. This ensures that only unique elements are copied into the new vector.

Implementation

In C 11 and later, define a function object with an overloaded operator() that implements the predicate:

template <typename T>
struct NotDuplicate {
  bool operator()(const T& element) {
    return s_.insert(element).second;  // true if element is unique
  }

private:
  std::set<T> s_;
};

Pass this predicate to std::copy_if along with the original and target vectors:

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

If C 11 support is not available, use std::remove_copy_if and invert the predicate logic to achieve the same result.

Conclusion

This approach demonstrates the effectiveness of STL algorithms for manipulating containers efficiently while ensuring adherence to the desired ordering requirements. By leveraging the std::copy_if algorithm, you can remove duplicates from an unsorted vector while preserving the insertion order of the unique elements.

The above is the detailed content of How to Remove Duplicates from an Unsorted Array While Maintaining Insertion Order Using STL Algorithms?. For more information, please follow other related articles on the PHP Chinese website!