How to delete an element from an array?

[saeed.albahri1]

Hello C++ Nerds!

I am creating a list using Arrays. And I want to have AddItem, DeleteItem functions in those lists.

But as you know, you can't delete an element from an Array because it's a fixed size. But we can shift all the left elements by one place and therefore we delete that Item.

I did the same thing, but I got a problem.

and I am trying to implement a function that deletes an element from my array and the function does remove the element, but it duplicates the next element in array two times.

void SortedList::DeleteItem(ItemType x)
{
    for (int i = 0; i < MAX_ITEMS; i++)
    {
        if (values[i] == x)
        {
            values[i] = values[i - 1];
        }
    }
}

List is like this:

1
2
3.3
4.4
5.5
6.2
7.1
8
9
10

after deleting 5.5, the output will be like:

1
2
3.3
4.4
4.4
6.2
7.1
8
9
10
Length is: 10

see that 4.4? I don't want two of them! I just want one.

How?

Full code is here:

#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <fstream>
#include <string>


#define MAX_ITEMS 10
typedef float ItemType;
using namespace std;

int compareItems(const void * x, const void * y)
{
    if (*(float *)x > *(float *)y)
    {
        return 1;
    }
    else if (*(float *)x < *(float *)y)
    {
        return -1;
    }

    return 0;
}

class SortedList
{
private:
    int length;
    ItemType values[MAX_ITEMS];
    int currentPos;
public:
    SortedList();
    void MakeEmpty();
    void InsertItem(ItemType x);
    void DeleteItem(ItemType x);
    bool IsFull();
    int Lengthls();
    void RetrieveItem(ItemType &x, bool &found);
    void ResetList();
    void GetNextItem(ItemType &x);
    float getItem(int index);
};

SortedList::SortedList()
{
    length = 0;
}

void SortedList::MakeEmpty()
{
    length = 0;
}

void SortedList::InsertItem(ItemType x)
{

    if (length == (MAX_ITEMS))
    {
        cout << "we reached the max number of elements allowed" << endl;
        return;
    }
    values[length++] = x;

    //sort the array
    qsort(values, length, sizeof(float), compareItems);
}

void SortedList::DeleteItem(ItemType x)
{
    for (int i = 0; i < MAX_ITEMS; i++)
    {
        if (values[i] == x)
        {
            values[i] = values[i - 1];
        }
    }
}

int SortedList::Lengthls()
{
    return length;
}

float SortedList::getItem(int index)
{
    return values[index];
}

void SortedList::GetNextItem(ItemType &x)
{

}


int main()
{
    SortedList Instance1;

    //insert txt file into array
    string line;
    ifstream myfile("float.txt");
    if (myfile.is_open())
    {
        while (getline(myfile, line))
        {
            Instance1.InsertItem(atof(line.c_str()));
        }
        myfile.close();
    }
    else cout << "Unable to open file";

    //delete item from array
    //Instance1.DeleteItem(5.5);

    //add item into array
    //Instance1.InsertItem(10);

    //print out the array to screen

    for (int i = 0; i < Instance1.Lengthls(); i++)
    {
        cout << Instance1.getItem(i) << endl;
    }

    //print the length to screen
    cout << "Length is: " << Instance1.Lengthls() << endl;


    system("Pause");
    return 0;

}

[Excizted]

It makes perfectly sense. Your delete function loops through your array, when it finds the element you want to delete it REPLACES this element with the previous element.

If you want your strategy to work, I suggest creating a temporary array by looping through all the elements, like you do now, but for the condition do:

if(i != x) addElementToNewArray

[mike_2000_17]

You don't need to create another temporary array, this can be done "in-place" (within the same array). The key is that you cannot just overwrite the element that is equal to x, you need to also shift all the other values.

Basically, what you need to do is replicate the behaviour of the standard std::remove function (see docs). This algorithm basically works by keeping track of two elements: the one you write to (write-marker) and the one you read from (read-marker). At each iteration, you increment the read-marker (index or pointer). But for the write-marker, you only increment it when the value is not x. This will make the write-marker lag behind the read-marker (or be equal to it) and skip overwrite any value that is equal to x. In the docs for the remove function, there is already some code there to demonstrate that logic, you could just use that code if you want, or you can just call the std::remove() function to do all the work for you.

[saeed.albahri1]

I just wanted to let you know that I figured it out. After hours of searching and trying.

This is the code I used:

void SortedList::DeleteItem(ItemType x)
{
    for (int i = 0; i < MAX_ITEMS; i++) // loop to find the item to delete
    {
        if (values[i] == x)   // if we find the item to delete
        {
            for (int j = i; j < MAX_ITEMS - 1; j++)
            {
                values[j] = values[j + 1];
            }

            values[MAX_ITEMS - 1] = NULL;
            length--;
            break;
        }
    }
}

[nullptr]

You should use length rather than MAX_ITEMS in DeleteItem(ItemType x).

[Maritimo]

This easy code delete multiple occurences of ItemType x from a
and works even for an array plenty of only x:

void SortedList::DeleteItem(ItemType x)
{
    int i=-1, j=0;
    while(j<MAX_ITEMS)
    {
        while(j<MAX_ITEMS && a[j]==x) ++j;
        if(j<MAX_ITEMS) a[++i]=a[j++];
    }
    MAX_ITEMS=i+1;
}

Enjoy :)