Add/ remove elements from C++ dynamic array

Question

So I'm trying to add and remove one element one-by-one from a dynamically allocated array. My code below 100% works for add_entry, but not really works for remove_entry. What I did was from a list, I copied the elements from that list to new_list. Some of the steps seem not necessary but I had to put there because we're learning about pointers.

The add_entry code works. The remove_entry works for "deleting Erika" but not since "deleting Bo". I would love to get your feed back on this. Thank you very much!

#include <iostream>
#include <string>

using namespace std;

typedef string T;

T* add_entry(T* list, const T& new_entry, //
         int& size, int& capacity);
T* remove_entry(T* list, const T& delete_me,
            int& size, int& capacity);

T* allocate(int capacity);

void copy_list(T *dest, T* src, int many_to_copy);
T* search_entry(T* list, const T& find_me, int size);

void print_list(T* list, int size);

int main(){
    int capacity = 3;
    int size = 0;
    T* list = allocate(capacity);
    list = add_entry(list, "Erika", size, capacity);
    print_list(list, size);


    list = add_entry(list, "Red", size, capacity);
    print_list(list, size);


    list = add_entry(list, "Bo", size, capacity);
    print_list(list, size);


    list = add_entry(list, "Pierson", size, capacity);
    print_list(list, size);


    list = add_entry(list, "Maher", size, capacity);
    print_list(list, size);


    list = add_entry(list, "Mac", size, capacity);
    print_list(list, size);


    list = add_entry(list, "Paula", size, capacity);
    print_list(list, size);

    cout<<"Deleting Erika"<<endl;

    list = remove_entry(list, "Erika", size, capacity);
    print_list(list, size);


    cout<<"Deleting Bo"<<endl;

    list = remove_entry(list, "Bo", size, capacity);
    print_list(list, size);  

    cout<<"Deleting Maher"<<endl;

    list = remove_entry(list, "Maher", size, capacity);
    print_list(list, size);

    cout<<"Deleting Pierson"<<endl;

    list = remove_entry(list, "Pierson", size, capacity);
    print_list(list, size);

    cout<<"Deleting Red"<<endl;

    list = remove_entry(list, "Red", size, capacity);
    print_list(list, size);

}

T* add_entry(T* list, const T& new_entry,
             int& size, int& capacity) {
    if (size == capacity) capacity*=2;
    T* new_list = allocate(capacity);
    copy_list(new_list, list, size);
    new_list[size] = new_entry;
    delete[] list;
    size++;
    return new_list;
}

T* remove_entry(T* list, const T& delete_me,
                int& size, int& capacity) {
    if (size == (int)(capacity/4)) {
        capacity=(int)(capacity/2);
    }
    T* new_list = allocate(capacity);
    copy_list(new_list, list, size);
    for (int i, j; j < size; i++) {
        if (list[i] != *search_entry(list, delete_me, size)) {
            new_list[j] = list[i];
            j++;
        }
    }
    delete[] list;
    size--;
    return new_list;
}

T* allocate(int capacity) {
    const bool debug = false;
    if(debug) cout<<"Allocate: capacity: "<<capacity<<endl;
    return new T[capacity];
}

void copy_list(T *dest, T* src, int many_to_copy) {
    for (int i; i< many_to_copy; i++)
        dest[i] = src[i];
}

T* search_entry(T* list, const T& find_me, int size) {
    for (int i; i< size; i++) {
        if (list[i] == find_me)
            return list;
    }
    return nullptr;
}


void print_list(T* list, int size) {
    for (int i; i < size; i++)
        cout << list[i] << " ";
    cout << endl;
}

Allocating a new array every single time is not what you are supposed to do. You have capacity > size exactly because you don't want to reallocate every time. Just add a new element at a free place. — n. m. could be an AI
– n. m. could be an AI, Commented Sep 18, 2018 at 5:03
@n.m. It's not efficient but this is just a homework to follow a prototype code. I really need to know where I coded wrong at my remove_entry function — Manny Lim
– Manny Lim, Commented Sep 18, 2018 at 5:06
Tactical note: Until I saw the typedef string T;, I was looking for templates. T is a common generic template parameter. — user4581301
– user4581301, Commented Sep 18, 2018 at 5:09
Is there any way you can bundle your dynamic array inside a class? Seems kind of a waste to be coding in C++ and doing all of the work the C way. — user4581301
– user4581301, Commented Sep 18, 2018 at 5:10
Your remove_entry logic is totally wrong and makes no sense at all. You should not be calling search_entry in that function. Also ask yourself how many entries you have removed. And your search_entry lis broken. Test this function separately. — n. m. could be an AI
– n. m. could be an AI, Commented Sep 18, 2018 at 5:15

john · Accepted Answer · 2018-09-18 08:18:06Z

The logic in remove_entry is just wrong. You could work this out for yourself by using a debugger, or even dry running a small example with pen and paper.

Your remove_entry function is also underspecified (at least in this post). Should it remove all entries equal to delete_me or just the first? Your implementation is unclear on this.

You make a consistent error all over the place

void print_list(T* list, int size) {
    for (int i; i < size; i++)
        cout << list[i] << " ";
    cout << endl;
}

should be

void print_list(T* list, int size) {
    for (int i = 0; i < size; i++)
        cout << list[i] << " ";
    cout << endl;
}

int i; does not set i to zero. It leaves it with an unspecified value. Clearly on your compiler it is getting set to 0, otherwise you would have noticed the problem. But C++ does not guaranteee this, so if you want zero say it with int i = 0;.

Think about what you are doing. To delete those entries equal to delete_me you must copy all the elements except those that are equal to delete_me. This requires a single for loop, it doesn't require multiple loops, it doesn't require searching for the element to remove, it doesn't require calling ancilliary functions, it's much easier than you think. Here's an implementation

T* remove_entry(T* list, const T& delete_me, int& size, int capacity) {
    T* new_list = allocate(capacity);
    int j = 0;
    for (int i = 0; i < size; i++) {
        if (list[i] != delete_me) {
            new_list[j] = list[i];
            j++;
        }
    }
    size = j;
    delete[] list;
    return new_list;
}

This implementation removes all elements equal to delete_me. You'll have to add some logic if you want to just remove the first. I've removed the stuff about changing the capacity because I didn't really understand it. If you're sure it's OK put it back.

This is untested code, I could easily have made a mistake.

As others have said there is no need here to allocate a new array, you can do this operation in place but I'll leave that as an exercise.

Collectives™ on Stack Overflow

Add/ remove elements from C++ dynamic array

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related