c++ - 从 C++ 动态数组中添加/删除元素

Question

所以我试图从一个动态分配的数组中一个一个地添加和删除一个元素。我低于 100% 的代码适用于 add_entry，但不适用于 remove_entry。我所做的是从一个列表中，我将该列表中的元素复制到 new_list。有些步骤似乎不是必需的，但我不得不放在那儿，因为我们正在学习指针。

add_entry 代码有效。 remove_entry 适用于“删除 Erika”，但不适用于“删除 Bo”。我很乐意就此获得您的反馈。非常感谢!

#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;
}

Answer 1

remove_entry 中的逻辑是错误的。您可以使用调试器自己解决这个问题，甚至可以用笔和纸试运行一个小示例。

您的 remove_entry 函数也未指定(至少在这篇文章中)。它应该删除等于 delete_me 的所有条目还是只删除第一个条目？您的实现对此不清楚。

你在整个地方都犯了一个一致的错误

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

应该是

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

int i; 不 将 i 设置为零。它留下一个未指定的值。显然在你的编译器上它被设置为 0，否则你会注意到这个问题。但是 C++ 不保证这一点，所以如果你想要零，请用 int i = 0; 来表示。

想想你在做什么。要删除那些等于 delete_me 的条目，您必须复制除了那些等于 delete_me 的元素之外的所有元素。这需要一个 for 循环，不需要多个循环，不需要搜索要删除的元素，不需要调用辅助函数，它比你想象的要容易得多。这是一个实现

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;
}

此实现删除所有等于 delete_me 的元素。如果您只想删除第一个，则必须添加一些逻辑。我已经删除了有关更改容量的内容，因为我并不真正了解它。如果您确定没问题，请将其放回去。

这是未经测试的代码，我很容易犯错。

正如其他人所说，这里不需要分配新数组，您可以就地执行此操作，但我将把它留作练习。