TITLE: STL example - an array with no duplicates

(Newsgroups: comp.lang.c++, 29 Apr 98)

DAVY: "Peter Davy" <peter.davy@stdc.govt.nz>

> Anybody know how to quickly go through a large array of integers and find
> duplicates? I realise I can get the value, store in a variable, and then go
> through the array for ever element until I find a match but it will be very
> time consuming for 1000 elements repeated 1000 times. Is there a faster
> way?
 

MCKEE: William A. McKee (5 May 98)

>> Here's how I'd do it:
>> 
>> int int_compare (const void * a, const void * b)
>> {
>>     return * (int *) a - * (int *) b;
>> }
>> 
>> int main ()
>> {
>>     int array [ARRAY_SIZE];
>>     int size = 0; // size of reduced array.
>>     if (ARRAY_SIZE > 0)
>>     {
>>         qsort (array, ARRAY_SIZE, sizeof (*array), int_compare);
>>         for (int i = 1; i < ARRAY_SIZE; i++)
>>             if (array [size] != array [i])
>>                 array[++size] = array [i];
>>         size++;
>>     }
>> }


BECKER: Pete Becker <petebecker@acm.org> (5 May 98)

Even better:

#include <algorithm>
#include <iterator>

int main()
{
int array[ARRAY_SIZE];
std::sort(array, array + ARRAY_SIZE);
std::copy(array, std::unique(array, array + ARRAY_SIZE),
	std::ostream_iterator<int>());
return 0;
}

<A HREF="TableOfContents.html">CppTips Table Of Contents</A><br>