CODEWITHSUNDEEP
c++arrayscharduplicates
Massa
Massa

Reputation: 41

Method problems: Deleting duplicate chars in an array

So I am trying to delete duplicate chars in a partially filled array. The array is populated from a file located on my PC. My array population method is working fine; however, my duplicate deleting method is not. Here is my method: 

    void deleteRepeated(char array[], int* numberUsed)
{
    for (int x = 0; x < *numberUsed ; x++) 
    {
        cout << "Positions used: " << *numberUsed << endl;
        for (int y = x+1; y < *numberUsed; y++ )
        {
            cout << "Positions used: " << *numberUsed << endl;
            if (array[y] == array[x])
            {
                cout << "Positions used: " << *numberUsed << endl;
                for (int z = y; z < *numberUsed; z++)
                    array[z] = array[z+1];
                y--; 
                *numberUsed--;
                cout << "Positions used: " << *numberUsed << endl;
            }
        }
    }
}

I am passing the entire array, and the number of indices used in that array. The array length is 10, and my tests, I am using 6 out of those 10 with the chars: {'g', 'g', 'n', 'o', 'r', 'e'}. What am I doing wrong?

NOTE: "cout << "Positions used: " << *numberUsed << endl" is being used to check if the method is correctly deleting or not. In the most inner loop where index is z, is where the method starts to go bonkers.

Any help would be much appreciated.

Upvotes: 1

Views: 509

Answers (2)

Tim Child
Tim Child

Reputation: 3012

Every time you find a dup you reduce the number chars used

*numberUsed--;

but remember this controlling the first loop index

for (int x = 0; x < *numberUsed ; x++)

so try this

int count =*numberUsed;
for (int x = 0; x < count ; x++)

this way you visit all the original chars in the array.

Upvotes: 1

us2012
us2012

Reputation: 16253

(I wrote the first part of this answer before I read your comment about STL not being allowed, but I'll leave it anyways because I think it's rather neat code.)

You could use the functionality that the C++ standard library makes available to you. Use std::string instead of char arrays (that's nearly always a good idea), then you can do the following (note: C++11 only because of unordered_set and std::begin):

#include <string>
#include <unordered_set>
#include <iostream>
#include <iterator>

std::string uniquechars(const std::string& s) {
    std::unordered_set<char> uniquechars(std::begin(s), std::end(s));
    std::string newstring(std::begin(uniquechars), std::end(uniquechars));
    return newstring;
}

int main() {
    std::string teststr("thisisanexamplesentence");
    std::cout << "The unique characters of " << teststr << " are " << uniquechars(teststr) << std::endl;
}

Note that it doesn't keep the original order of the characters though, so if that's needed this does not work.

If you have to work without the standard library, you have to dig a bit deeper. @TimChild above already made a good start diagnosing what's wrong with your program, but there are more efficient solutions, for example keeping some kind of record of which characters you have already seen. As you're working with chars, I would consider a bit-field that can hold markers (extra overhead of 256/8=32 bytes) or if that's not too much, just a plain array of bools (extra overhead 256 bytes). As the latter is easier to implement and the code is more legible:

void deleteRepeated(char array[], int *numused) {
    bool seenthischar[256] = {false};
    char *readpointer = &array[0];
    char *writepointer = &array[0];
    int length = *numused;
    for ( ;readpointer <= &array[0] + length; readpointer++) {
      if (seenthischar[((unsigned char) *readpointer)]) {
        *numused--;
      } else {
        seenthischar[((unsigned char) *readpointer)] = true;
        *writepointer = *readpointer;
        writepointer++;
      }
    }
}

This only has one loop, so it only has to go through the array once, i.e. its time complexity is linear in the length of the input array.

Upvotes: 1

Related Questions