unique

Category: algorithms	Component type: function

Prototype

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

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

Description

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

Requirements on types

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

• 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

Example

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.

See also