How do you write a c plus plus program to remove duplicate elements in an array using function templates?

Answer 1

The most efficient method is to sort the array and then remove duplicate neighbours. If you want to maintain the original order, you must do it the long way, comparing every element with every other element, removing duplicates as you go.

Both methods are shown below.

#include // std::cout and std::endl

#include // std::vector

#include // std::sort and std::unique

#include // pseudo-random numbers

#include // required to seed random numbers

template

unsigned remove_unsorted_duplicates (std::vector& arr)

{

// Maintain count of deletions.

unsigned deletions(0);

// Need at least 2 elements...

if (arr.size() < 2)

return deletions;

// Loop through all but the penultimate element (left elements).

unsigned left(0);

unsigned penultimate = arr.size() - 1;

while (left < penultimate)

{

// Loop through all elements to the right of left element (right elements).

unsigned right = left + 1;

while (right < arr.size())

{

// Duplicate?

if (arr[left] == arr[right])

{

// Left-shift all the elements from end of the array to fill the gap.

unsigned i = right;

while (i < penultimate)

{

arr[i] = arr[i+1];

++i;

}

// Remove the redundant element from the end of the array.

arr.pop_back ();

// Increment the deletion total.

++deletions;

// Decrement the penultimate count.

--penultimate;

}

else

{

// Not a duplicate -- move to next element.

++right;

}

}

// Move to next element from left.

++left;

}

// Return the number of deletions.

return deletions;

}

template

unsigned remove_sorted_duplicates (std::vector& arr)

{

unsigned size = arr.size();

std::sort (arr.begin(), arr.end());

std::vector::iterator it = std::unique (arr.begin(), arr.end());

arr.resize (std::distance (arr.begin(), it));

return size - arr.size();

}

template

void print_array (std::vector& arr)

{

for (unsigned i(0); i < arr.size(); ++i)

{

std::cout << arr[i] << ' ';

}

std::cout << std::endl;

}

int main()

{

// Pseudo-random number generator.

std::default_random_engine generator;

generator.seed ((unsigned) time (NULL));

std::uniform_int_distribution distribution (1, 5);

// Create an array with 10 random elements in the range 1 to 5.

// Guaranteed to create at least 5 duplicates.

std::vector arr (10);

for (unsigned i(0); i < arr.size(); ++i)

{

arr[i] = distribution (generator);

}

// Copy the array.

std::vector arr2 (arr);

std::cout << "Unsorted duplicate removal\n" << std::endl;

std::cout << "Before:\t";

print_array (arr);

unsigned deletions = remove_unsorted_duplicates (arr);

std::cout << "After:\t";

print_array (arr);

std::cout << "There were " << deletions << " deletions.\n" << std::endl;

std::cout << "Sorted duplicate removal\n" << std::endl;

std::cout << "Before:\t";

print_array (arr2);

deletions = remove_sorted_duplicates (arr2);

std::cout << "After:\t";

print_array (arr2);

std::cout << "There were " << deletions << " deletions.\n" << std::endl;

}

Example Output

Unsorted duplicate removal

Before: 2 2 1 3 1 3 1 4 3 2

After: 2 1 3 4

There were 6 deletions.

Sorted duplicate removal

Before: 2 2 1 3 1 3 1 4 3 2

After: 1 2 3 4

There were 6 deletions.