# STLAlgorithmExtensions/NonUniqueCopy

BOOST WIKI | STLAlgorithmExtensions | RecentChanges | Preferences | Page List | Links List

The C++ standard defines unique_copy as a mechanism to copy all unique elements within a sequence. However, no mechanism is defined to copy a single instance of each item that has at least one duplicate, following it. That is:

```Given: 1,2,2,3,4,4,4,4,4,5
Result: 2,4 (These items were duplicated)
```

Presented below is a fairly efficient algorithm, given the iterator types supplied, solving this somewhat tricky problem. As with unique_copy, the initial iterator range is assumed to represent a sequence in either non-ascending or non-descending order, otherwise the behavior is undefined. As with unique_copy, an iterator one past the end of the output range is returned:

```template<typename InputIterator, typename OutputIterator>
OutputIterator nonunique_copy(InputIterator first1, InputIterator last1, OutputIterator first2)
{
if (first1!=last1) // Test for empty range
for (InputIterator prev(first1++);first1!=last1;++prev,++first1)
if (*first1==*prev) // Test if current pair is not unique
{
*first2++=*first1; // Store in output sequence
for (;;) // Find next set of distinct elements
{
prev=first1++;
if (first1==last1) // End of input range hit, done
return first2;
if (!(*first1==*prev)) // Next non-unique pair found, skip and look for next dupe
break;
}
}

return first2;
}

template<typename InputIterator, typename OutputIterator, typename BinaryPredicate>
OutputIterator nonunique_copy(InputIterator first1, InputIterator last1, OutputIterator first2, BinaryPredicate pred)
{
if (first1!=last1) // Test for empty range
for (InputIterator prev(first1++);first1!=last1;++prev,++first1)
if (pred(*first1,*prev)) // Test if current pair is not unique
{
*first2++=*first1; // Store in output sequence
for (;;) // Find next set of distinct elements
{
prev=first1++;
if (first1==last1) // End of input range hit, done
return first2;
if (!pred(*first1,*prev)) // Next non-unique pair found, skip and look for next dupe
break;
}
}

return first2;
}
```

#### Sample code usage, with std:: omitted for brevity:

```int main()
{
int nums[]={1,2,2,3,4,4,4,4,4,5};
vector<int> nonUniqueNums; // set<int> could have been used instead, since the resulting elements are unique

nonunique_copy(nums,nums+sizeof(nums)/sizeof(int),back_inserter(nonUniqueNums));

std::copy(nonUniqueNums.begin(),nonUniqueNums.end(),ostream_iterator<int>(cout,","));
std::cout << '\n';
}
```

Output:

2,4,

Enjoy,

BOOST WIKI | STLAlgorithmExtensions | RecentChanges | Preferences | Page List | Links List
Edit text of this page | View other revisions
Last edited March 21, 2005 2:37 pm (diff)
Search:
Disclaimer: This site not officially maintained by Boost Developers