unique


Category: algorithms	Component type: function

Prototype

Unique is an overloaded name; there are actually two unique functions.

template <class ForwardIterator>
ForwardIterator unique(ForwardIterator first, ForwardIterator last);

template <class ForwardIterator, class BinaryPredicate>
ForwardIterator unique(ForwardIterator first, ForwardIterator last,
                       BinaryPredicate binary_pred);

Description

Every time a consecutive group of duplicate elements appears in the range [first, last), the algorithm unique removes all but the first element. That is, unique returns an iterator new_last such that the range [first, new_last) contains no two consecutive elements that are duplicates. [1] The iterators in the range [new_last, last) are all still dereferenceable, but the elements that they point to are unspecified. Unique is stable, meaning that the relative order of elements that are not removed is unchanged.

The reason there are two different versions of unique is that there are two different definitions of what it means for a consecutive group of elements to be duplicates. In the first version, the test is simple equality: the elements in a range [f, l) are duplicates if, for every iterator i in the range, either i == f or else *i == *(i-1). In the second, the test is an arbitrary Binary Predicate binary_pred: the elements in [f, l) are duplicates if, for every iterator i in the range, either i == f or else binary_pred(*i, *(i-1)) is true. [2]

Definition

Defined in algo.h.

Requirements on types

For the first version:

ForwardIterator is a model of Forward Iterator.
ForwardIterator is mutable.
ForwardIterator's value type is Equality Comparable.

For the second version:

ForwardIterator is a model of Forward Iterator.
ForwardIterator is mutable.
BinaryPredicate is a model of Binary Predicate. [3]
ForwardIterator's value type is convertible to BinaryPredicate's first argument type and to BinaryPredicate's second argument type.

Preconditions

[first, last) is a valid range.

Complexity

Linear. Exactly (last - first) - 1 applications of operator== (in the case of the first version of unique) or of binary_pred (in the case of the second version).

Example

Remove duplicates from consecutive groups of equal ints.

vector<int> V;
V.push_back(1);
V.push_back(3);
V.push_back(3);
V.push_back(3);
V.push_back(2);
V.push_back(2);
V.push_back(1);

vector<int>::iterator new_end = unique(V.begin(), V.end());
copy(V.begin(), new_end, ostream_iterator<int>(cout, " "));
    // The output it "1 3 2 1".

Remove all duplicates from a vector of chars, ignoring case. First sort the vector, then remove duplicates from consecutive groups.

inline bool eq_nocase(char c1, char c2) { return tolower(c1) == tolower(c2); }
inline bool lt_nocase(char c1, char c2) { return tolower(c1) < tolower(c2); }

int main()
{
  const char init[] = "The Standard Template Library";
  vector<char> V(init, init + sizeof(init));
  sort(V.begin(), V.end(), lt_nocase);
  copy(V.begin(), V.end(), ostream_iterator<char>(cout));
  cout << endl;
  vector<char>::iterator new_end = unique(V.begin(), V.end(), eq_nocase);
  copy(V.begin(), new_end, ostream_iterator<char>(cout));
  cout << endl;
}
// The output is:
//    aaaabddeeehiLlmnprrrStTtTy
//  abdehiLmnprSty

Notes

[1] Note that the meaning of "removal" is somewhat subtle. Unique, like remove, does not destroy any iterators and does not change the distance between first and last. (There's no way that it could do anything of the sort.) So, for example, if V is a vector, remove(V.begin(), V.end(), 0) does not change V.size(): V will contain just as many elements as it did before. Unique returns an iterator that points to the end of the resulting range after elements have been removed from it; it follows that the elements after that iterator are of no interest. If you are operating on a Sequence, you may wish to use the Sequence's erase member function to discard those elements entirely.

[2] Strictly speaking, the first version of unique is redundant: you can achieve the same functionality by using an object of class equal_to as the Binary Predicate argument. The first version is provided strictly for the sake of convenience: testing for equality is an important special case.

[3] BinaryPredicate is not required to be an equivalence relation. You should be cautious, though, about using unique with a Binary Predicate that is not an equivalence relation: you could easily get unexpected results.