CodeCogs

Copies elements while removing adjacent duplicates

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

Definition

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

Interface

#include <algorithm>
template < class InputIterator, class OutputIterator >
   OutputIterator unique_copy(
      InputIterator first, 
      InputIterator last, 
      OutputIterator result
   );
template < class InputIterator, class OutputIterator, class BinaryPredicate >
   OutputIterator unique_copy(
      InputIterator first, 
      InputIterator last, 
      OutputIterator result,
      BinaryPredicate comp,
   );

Parameters:

Parameter	Description
first	A forward iterator addressing the position of the first element in the source range to be copied
last	A forward iterator addressing the position one past the final element in the source range to be copied
result	An output iterator addressing the position of the first element in the destination range that is receiving the copy with consecutive duplicates removed
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_copy algorithm copies a sequence such as each duplicate consecutive elements become an unique element.

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

Return Value

Returns an iterator pointing to the end of the output range.

Complexity

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

References

http://www.tenouk.com/

Example 1

Problem

The following program demonstrates how to use unique_copy():

Workings

#include <iostream>
#include <list>
#include <algorithm>
#include <iterator>

using namespace std;

bool differenceOne (int elem1, int elem2)
{

  return elem1 + 1 == elem2 || elem1 - 1 == elem2;

}

int main()
{

  // source data
  int source[] = { 1, 4, 4, 6, 1, 2, 2, 3, 1, 6, 6, 6, 5, 7,5, 4, 4 };
  int sourceNum = sizeof(source)/sizeof(source[0]);

  // initialize coll with elements from source
  list<int> coll;
  copy(source, source+sourceNum,   // source
            back_inserter(coll));  // destination
  PRINT_ELEMENTS(coll);

  // print element with consecutive duplicates removed
  unique_copy(coll.begin(), coll.end(),    // source
              ostream_iterator<int>(cout," "));  // destination
  cout <<endl;


  // print element without consecutive duplicates that differ by one
  unique_copy(coll.begin(), coll.end(),   // source
              ostream_iterator<int>(cout," "),  // destination
              differenceOne);                   // duplicate criterion
  cout <<endl;

  return 0;
}

Solution

Output:

1 4 4 6 1 2 2 3 1 6 6 6 5 7 5 4 4
1 4 6 1 2 3 1 6 5 7 5 4
1 4 4 6 1 3 1 6 6 6 4 4

References

Nicolai M. Josuttis: "The C++ Standard Library"

Example 2

Problem

This program illustrates the use of the STL unique_copy() algorithm (default version) to remove adjacent duplicate copies of integer values from a vector of integers, and simultaneously copy the remaining values to another vector.

Workings

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

using namespace std;

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

  int a12[] = {21, 22, 23, 24, 25, 26, 27, 28, 29, 
               30, 31, 32, 33, 34, 35, 36, 37, 38};
  vector<int> v12(a12, a12+18);
  cout <<"\nHere are the values in the destination vector:\n";
  for (vector<int>::size_type i=0; i<v12.size(); i++)
    cout <<v12.at(i)<<" ";

  cout <<"\nNow we remove all adjacent duplicate copies of the "
         " values 2 and 3 from\nthe source vector and copy the remaining "
         "values to the destination vector,\nstarting at the third value "
         "in that destination vector.";
  vector<int>::iterator output_end = unique_copy(v11.begin(), v11.end(),
                                                 v12.begin()+2);

  cout <<"\nHere are the (unchanged) source vector values:\n";
  vector<int>::iterator p = v11.begin();
  while (p != v11.end())
    cout <<*p++<<" ";
  
  cout <<"\nAnd here are the destination vector values:\n";
  p = v12.begin();
  while (p != v12.end()) 
    cout <<*p++<<" ";

  cout <<"\nThe iterator returned by the call to unique_copy() is "
          "pointing to the value " << *output_end << ".";

  return 0;
}

Solution

Output:

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

Here are the values in the destination vector:
21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

Now we remove all adjacent duplicate copies of the values 2 and 3 from
the source vector and copy the remaining values to the destination vector,
starting at the third value in that destination vector.

Here are the (unchanged) source vector values:
1 2 2 3 3 6 5 2 6 9 12 2 2 2 9 10 11 12

And here are the destination vector values:
21 22 1 2 3 6 5 2 6 9 12 2 9 10 11 12 37 38

The iterator returned by the call to unique_copy() is pointing to the value 37.

References

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

unique_copy

Definition

Interface

Description

Return Value

Complexity

References

Example 1

Example 2

See Also