1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
|
#include <iostream>
// return true if value is present in any of the positions [0 ... n-1]
bool is_present( const int array[], std::size_t n, int value )
{
for( std::size_t i = 0 ; i < n ; ++i ) if( array[i] == value ) return true ;
return false ;
}
// return true if the value of array[pos] is present in any of the positions [0 ... pos-1]
bool seen_earlier( const int array[], std::size_t pos )
{
if( pos == 0 ) return false ; // there is nothing before the first element
else return is_present( array, pos, array[pos] ) ;
}
// bring unique elements to the front of the array; return number of unique elements
std::size_t unique( int array[], std::size_t sz )
{
if( sz == 0 ) return 0 ; // sanity check
std::size_t next_pos = 1 ; // position to place the next unique element
// (array[0] is always unique)
// note that logically, there is a nested loop here:
// seen_earlier() calls is_present() which implements a loop
// however, the code is easier to read and reason about when
// we do not have directly nested control structures within the same function
// (caveat: a "career teacher" may see red because he/she/it can't
// immediately see any directly nested loops in the program)
for( std::size_t i = 1 ; i < sz ; ++i )
if( !seen_earlier( array, i ) ) array[ next_pos++ ] = array[i] ;
return next_pos ; // number of unique elements
}
// print the first n elements of the array
void print( const int array[], std::size_t n, std::ostream& stm = std::cout )
{
for( std::size_t i = 0 ; i < n ; ++i ) stm << array[i] << ' ' ;
stm << '\n' ;
}
int main()
{
int test[] { 2, 2, 1, 1, 2, 5, 4, 4, 3, 4, 3, 3, 5, 5, 4, 4, 1, 6, 3, 2, 1, 1 } ;
const std::size_t n = sizeof(test) / sizeof(*test) ;
print( test, n ) ;
const std::size_t n_unique = unique( test, n ) ;
print( test, n_unique ) ;
}
|