Error in Removal of Duplicates from a Sorted Array in C++ using Pointers

Question

I have a task to remove the duplicates from a sorted array.

However, when I try this it doesn't remove anything and still gives me the same values in the output as the original.

I think I'm missing something in the removeDuplicates() function.

Also pointer notation would be recommended. Thank you!

void removeDuplicates(int *arr, int *size)
{
    int s,*p,i,k=0;
    p=arr;
    s=*size;
    int arr1[s];
    for(i=0;i<s-1;i++)
    {
        if (*(p+i)!=*(p+i+1))
        {
            arr1[k++]=*(p+i);
        }
    }
    arr1[k++]=*(p+s-1);

    for(i=0; i<k; i++)
    {
        *(p+i) = arr1[i];
    }
    for(i=0; i<k; i++)
    {
        cout<<*(p+i)<<endl;
    }
}

Are the duplicates always adjacent to each other? Also any reason for writing *(p + i) rather than just p[i] itself? — Zoso
– Zoso, Commented May 4, 2021 at 15:47
Do you have a reason not to use: en.cppreference.com/w/cpp/algorithm/unique ? — al3c
– al3c, Commented May 4, 2021 at 15:48
@Zoso the title says "sorted array", so the duplicates should be adjacent if it's sorted properly. — Mark Ransom
– Mark Ransom, Commented May 4, 2021 at 15:50
@MarkRansom Oh right. I missed the title. The question body had no mention of the array being sorted. Thanks. — Zoso
– Zoso, Commented May 4, 2021 at 15:51
int arr1[s] is not valid C++, although some compilers may support it as a non-standard extension (keyword: VLA). If you want a dynamically allocated array, consider using a vector. (Note: this is not the problem, if it compiles, it works, it's just not something you should be relying on) — user14215102
– user14215102, Commented May 4, 2021 at 15:52

Vlad from Moscow · Accepted Answer · 2021-05-04 16:15:31Z

2

For starters variable length arrays as the array declared in your function

int arr1[s] = {};

is not a standard C++ feature. And moreover in C where variable length arrays exist you may not initialize them in their declarations.

Moreover if the source array contains only one or two different elements then the value of the variable k will be incorrect and equal to either 0 (instead of 1) or 1 (instead of 2).

Apart from this the function shall not output anything. It is the caller of the function decides whether to output the sub-array of unique elements. And as the second parameter is passed by reference in C meaning then it shall be changed within the function.

There is standard algorithm std::unique that can be used to do the task. Here is a demonstrative program.

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

int main() 
{
    int a[] = { 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5 };
    
    auto last = std::unique( std::begin( a ), std::end( a ) );
    
    for ( auto first = std::begin( a ); first != last; ++ first )
    {
        std::cout << *first << ' ';
    }
    
    std::cout << '\n';
    
    return 0;
}

The program output is

1 2 3 4 5

If you want to write a similar function for arrays yourself using pointers within the function then it can look for example the following way

#include <iostream>

template <typename T>
size_t removeDuplicates( T *a, size_t n )
{
    T *dest = a;
    
    if ( n != 0 )
    {
        ++dest;
        for ( T *current = a; ++current != a + n;  )
        {
            if ( *current != *( dest - 1 ) )
            {
                if ( dest != current )
                {
                    *dest = *current;
                }
                
                ++dest;
            }
        }           
    }
    
    return dest - a;
}

int main() 
{
    int a[] = { 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5 };
    const size_t N = sizeof( a ) / sizeof( *a );
    
    size_t last = removeDuplicates( a, N );
    
    for ( size_t first = 0; first != last; ++first )
    {
        std::cout << a[first] << ' ';
    }
    
    std::cout << '\n';
    
    return 0;
}

Again the program output is

1 2 3 4 5

answered May 4, 2021 at 16:15

Vlad from Moscow

313k27 gold badges204 silver badges358 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

greybeard Over a year ago

Why control *dest = *current?

Vlad from Moscow Over a year ago

@greybeard What is unclear with this assignment statement?

greybeard Over a year ago

I see good reason to have it executed only when dest != current (which I asked about). Does Gkp? Why do you not assign unconditionally?

Vlad from Moscow Over a year ago

@greybeard If there are no duplicate elements then the assignments will be redundant and in general inefficient.

Collectives™ on Stack Overflow

Error in Removal of Duplicates from a Sorted Array in C++ using Pointers

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related