How to Remove Duplicates from an Unsorted Vector while Maintaining Order?

Removing Duplicates from an Unsorted Vector

Maintaining the order of first occurrences while eliminating duplicates from an unsorted vector is crucial in various situations. While a straightforward approach utilizing a set and manual iteration is effective, it can be improved upon by leveraging STL algorithms.

To achieve this, the std::copy_if algorithm provides a convenient solution. By defining a predicate that keeps track of elements already processed and returns false for duplicates, we can filter out the desired elements.

If C 11 support is unavailable, the clumsily named std::remove_copy_if can be employed, with its logic inverted. Here's an untested example to illustrate:

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

Next, the following code can be used:

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

In this solution, the std::ref ensures that the stateful functor is not copied internally within the algorithm. However, std::copy_if does not impose any requirements on side-effects of the applied functor.

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