CodeCogs

Removes adjacent duplicates (elements that are equal to their predecessor)

You're viewing an older version of this page (#4148). View the current version.

Definition

The unique() algorithm is defined in the standard header <algorithm> and in the nonstandard backward-compatibility header <algo.h>.

Interface

#include <algorithm>
template < class ForwardIterator >
   ForwardIterator unique(
      ForwardIterator first, 
      ForwardIterator last
   );
template < class ForwardIterator, class Predicate >
   ForwardIterator unique(
      ForwardIterator first, 
      ForwardIterator last,
      Predicate comp
   );

Parameters:

Parameter	Description
first	A forward iterator addressing the position of the first element in the range to be scanned for duplicate removal
last	A forward iterator addressing the position one past the final element in the range to be scanned for duplicate removal
comp	User-defined predicate function object that defines the condition to be satisfied if two elements are to be taken as equivalent. A binary predicate takes two arguments and returns `true` when satisfied and `false` when not satisfied

Description

Unique algorithm transforms a sequence such as each duplicate consecutive elements become a unique element.

The first version uses operator== to compare the elements, the second version uses the given binary predicate comp.

Return Value

The return value is an iterator pointing to the end of the collapsed range.

Complexity

The complexity is linear; performs (last - first) - 1 applications of operator== (for the first version) or of comp (for the second version).

References

http://www.tenouk.com/

Example 1

Problem

This program illustrates the use of the STL unique() algorithm (default version) to remove adjacent duplicate copies of integer values from a vector of integers.

Workings

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
  int a1[] = {1, 2, 2, 3, 3, 6, 5, 2, 6, 9, 12, 2, 2, 2, 9, 10, 11, 12};
  vector<int> v1(a1, a1+18);
  cout <<"\nHere are the values in the first vector:\n";
  for (vector<int>::size_type i=0; i<v1.size(); i++)
    cout <<v1.at(i)<<" ";

  cout <<"\nNow we remove all adjacent duplicate copies of the "
          "\nvalues 2 and 3 and redisplay the values to confirm:\n";
  vector<int>::iterator new_end = unique(v1.begin(), v1.end());
  vector<int>::iterator p = v1.begin();
  while (p != new_end) cout << *p++ << " ";
    
  int a2[] = {1, 1, 2, 2, 2, 3, 4, 5, 5, 5, 6, 7, 7, 8, 9, 10, 10, 10};
  vector<int> v2(a2, a2+18);
  cout <<"\nHere are the values in the second vector:\n";
  for (vector<int>::size_type i=0; i<v2.size(); i++)
    cout <<v2.at(i)<<" ";

  cout <<"\nNow we remove all adjacent duplicate copies of any "
          "\nof the values and redisplay the values to confirm:\n";
  new_end = unique(v2.begin(), v2.end());
  p = v2.begin();
  while (p != new_end)
    cout <<*p++<<" ";

  return 0;
}

Solution

Output:

Here are the values in the first vector: 1 2 2 3 3 6 5 2 6 9 12 2 2 2 9 10 11 12

Now we remove all adjacent duplicate copies of the
values 2 and 3 and redisplay the values to confirm: 1 2 3 6 5 2 6 9 12 2 9 10 11 12

Here are the values in the second vector: 1 1 2 2 2 3 4 5 5 5 6 7 7 8 9 10 10 10

Now we remove all adjacent duplicate copies of any
of the values and redisplay the values to confirm: 1 2 3 4 5 6 7 8 9 10

References

http://www.smu.ca/academic/science/compsci/

Example 2

Problem

This program illustrates the use of the STL unique() algorithm (extended version) to remove adjacent duplicate copies of integer values divisible by 3 from a vector of integers.

Workings

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/* Determines if two integers are both divisible by 3.
   m and n both contain an integer
   Returns true if m and n are both divisible by 3 and otherwise false. */

bool bothDivisibleByThree
(
  int m, //in
  int n //in
)
{
  return (m%3 == 0) && (n%3 == 0);
}

int main()
{
  int a1[] = {1, 2, 2, 3, 3, 6, 5, 2, 6, 9, 12, 2, 2, 2, 9, 10, 11, 12};
  vector<int> v1(a1, a1+18);
  cout <<"\nHere are the values in the first vector:\n";
  for (vector<int>::size_type i=0; i<v1.size(); i++)
    cout <<v1.at(i)<<" ";

  cout <<"\nNow we remove all adjacent duplicate copies of the "
         "\nvalues 2 and 3 and redisplay the values to confirm:\n";
  vector<int>::iterator new_end = unique(v1.begin(), v1.end(),
                                         bothDivisibleByThree);
  vector<int>::iterator p = v1.begin();
  while (p != new_end)
    cout <<*p++<<" ";

  int a2[] = {1, 1, 2, 3, 3, 3, 4, 5, 5, 6, 6, 7, 8, 9, 9, 9, 9, 10};
  vector<int> v2(a2, a2+18);
  cout <<"\nHere are the values in the second vector:\n";
  for (vector<int>::size_type i=0; i<v2.size(); i++)
    cout <<v2.at(i)<<" ";

  cout <<"\nNow we remove all adjacent duplicate copies of any "
         "\nof the values and redisplay the values to confirm:\n";
  new_end = unique(v2.begin(), v2.end(), bothDivisibleByThree);
  p = v2.begin();
  while (p != new_end) 
    cout <<*p++<<" ";

  return 0;
}

Solution

Output:

Here are the values in the first vector:
1 2 2 3 3 6 5 2 6 9 12 2 2 2 9 10 11 12

Now we remove all adjacent duplicate copies of the
values 2 and 3 and redisplay the values to confirm:
1 2 2 3 5 2 6 2 2 2 9 10 11 12

Here are the values in the second vector:
1 1 2 3 3 3 4 5 5 6 6 7 8 9 9 9 9 10

Now we remove all adjacent duplicate copies of any
of the values and redisplay the values to confirm:
1 1 2 3 4 5 5 6 7 8 9 10

References

http://cs.smu.ca/

unique

Definition

Interface

Description

Return Value

Complexity

References

Example 1

Example 2

See Also