C++：从动态结构数组中删除元素并移动其他元素

Question

我有一个结构数组。我正在尝试从该数组中删除一个元素列表，并将其他元素向左移动。移动元素后，我试图 delete/free 数组末尾的内存，我们不再需要了。我有以下代码：

#include <iostream>
#include<stdio.h>
#include<stdlib.h>
void removeelement(int*);
void displayelements();

typedef struct {
   int n;
}element;
element** array;

int numofelements=5;

int main() {
   array = (element**)malloc(5*sizeof(element*));
   for(int i=0;i<5;i++){
       array[i] = new element;
       array[i]->n=i;
   }
   int removelist[3] = {1,3,4};
   removeelement(removelist);
   displayelements();
   return 0;
}
void removeelement(int* removelist){
    for(int i=0;i<3;i++){
        int index = removelist[i];
        int j;
        for(j=index;j<numofelements-2;j++){
            array[j] = array[j+1];
        }
        delete [] array[j+1];
        numofelements--;
    }
}
void displayelements(){
    int i=0;
    while(i<numofelements){
        printf("%d\n",array[i]->n);
        i++;
    }
}

但是 delete [] array[j+1]; 导致异常：

*** Error in `main': double free or corruption (fasttop): 0x0000000001861cb0 ***

我不明白是什么原因造成的。正如许多人在其他论坛中所建议的那样，我正在使用 'new' 运算符来创建一个新的动态元素。

编辑：

我做了以下修改：

我把for(j=index;j<numofelements-2;j++){改成了for(j=index;j<numofelements-1;j++){

int index = removelist[i] 到 int index = removelist[i]-i

我删除了 delete [] array[j+1] 将 delete array[numofelements+1] 放在两个 for 循环之外。虽然我只对一个元素使用了 delete，但它也为其他冗余元素释放了内存，这很有趣。这是最终代码：

#include <iostream>
#include<stdio.h>
#include<stdlib.h>
void removeelement(int*);
void displayelements();

typedef struct {
   int n;
}element;
element** array;

int numofelements=5;

int main() {
   array = (element**)malloc(5*sizeof(element*));
   for(int i=0;i<5;i++){
       array[i] = new element;
       array[i]->n=i;
   }
   int removelist[3] = {1,3,4};
   removeelement(removelist);
   displayelements();
   return 0;
}
void removeelement(int* removelist){
    for(int i=0;i<3;i++){
        int index = removelist[i]-i;
        int j=index;
        for(;j<numofelements-1;j++){
            array[j] = array[j+1];
        }
        numofelements--;
    }
    delete array[numofelements+1];
}
void displayelements(){
    int i=0;
    while(i<5){
        printf("%d\n",array[i]->n);
        i++;
    }
}

我使用这段代码让它工作。但我将按照你们许多人的建议使用 std::vector。

Answer 1

您在 new[] 表达式未返回的指针上使用了 delete[] 表达式。因此程序的行为是未定义的。

任何用 new 分配的东西都必须用 delete 释放。 delete[] 不行。

即使您使用了正确的表达式，还有另一个错误：

int numofelements=5;

//...
for(int i=0;i<3;i++){
    int index = removelist[i];
    int j;
    for(j=index;j<numofelements-2;j++){
        array[j] = array[j+1];
    }
    delete [] array[j+1];
    numofelements--;
}

外循环第一次迭代后，array[4]已被删除。请注意，由于 removelist[i] == 1，我怀疑 array[4] 一开始就不应该被删除。

在第二次迭代中，array[4]将再次被删除。由于 this 指向已删除的对象，因此行为未定义。

此外，由于array[j] = array[j+1]在内循环中，删除指针的副本仍保留在数组中，而部分指针将被覆盖，因此它们的内存将被泄漏。简单修复你的算法：先删除索引处的指针，删除后移动元素。

甚至更多：如果您的循环按预期工作，前 2 次迭代将每次删除数组的一个元素，从而将 numofelements 减少到 3。然后，您将删除索引处的一个元素4 在索引 0..2 中具有有效指针的数组。大概必须对要删除的索引进行排序；在这种情况下，可以通过删除索引 removelist[i] - i 来解决偏移问题。另一个聪明的策略是按照 Paul 的建议从高到低删除指数。

其他需要考虑的事项：

程序泄漏了分配给 array 的内存。对于这个简单的程序来说，这可能不是问题，但最好养成取消分配所有已分配内存的习惯，以免在重要的时候忘记这样做。
使用 malloc 是个坏主意，除非有具体合理的理由这样做。人们通常没有合理的理由使用 malloc.
在不使用 RAII 容器的情况下分配动态内存是个坏主意。如果使用 std::vector，这个程序中的错误本来可以避免的。

Answer 2

这一行：

delete [] array[j+1];

删除'array[j+1]'指向的元素数组。但是 'array[j+1]' 是由这一行初始化的：

array[i] = new element;

它只分配一个元素，而不是一个元素数组，所以删除也应该只删除一个元素。例如：

delete array[j+1];

然而，主要问题是删除了错误的元素。为了了解原因，让我们假设初始化 'array' 的循环将指针分配给五个 'element' 结构，我们将它们称为 A、B、C、D 和 E。

在调用 removeelements() 之前，'array' 包含以下指针：

array[0] -> A
array[1] -> B
array[2] -> C
array[3] -> D
array[4] -> E

'numofelements' 是 5.

在 removeelements() 内部，第一个要删除的元素是 1，内部循环如下所示：

for(j=1;j<3;j++){
    array[j] = array[j+1];
}

这将导致 'array[2]' 的内容被复制到 'array[1]' 中，而 'array[3]' 的内容被复制到 'array[2] 中。之后 'array' 包含以下内容：

array[0] -> A
array[1] -> C
array[2] -> D
array[3] -> D
array[4] -> E

此时'j'包含3所以'delete array[j+1]'会删除'array[4]'指向的元素，即'E'.

'numofelements' 然后递减为 4.

要删除的第二个元素是 3。因为 'numofelements' 现在是 4，所以内部循环将如下所示：

for(j=3;j<2;j++){
    array[j] = array[j+1];
}

'j' 将被初始化为 3。它大于 2，因此循环体不会执行，'array' 将保持不变。

因为 'j' 是 3 'delete array[j+1]' 将再次删除 'array[4]'，它仍然指向 E。所以 E 被第二次删除，导致你得到的错误。

如果程序继续运行，'numofelements' 将递减为 3，然后我们将移至要删除的第三个元素，即 4。这将产生如下内部循环：

for(j=4;j<1;j++){
    array[j] = array[j+1];
}

'j' 将被初始化为 4 并且循环体将再次不被执行。 'delete array[j+1]' 将尝试删除 'array[5]' 指向的元素，该元素超出了 'array' 的范围并会导致异常。

正如其他人所建议的那样，处理此问题的最佳方法是使用 std::vector。但是，即使 std::vector 代码的结构方式也无法为您提供所需的结果，因为一旦从 'array' 中删除一个元素，其后所有元素的索引都会发生变化，这意味着'removelist' 中的其余索引将不再正确。

我建议无论您进行何种更改，您都手动逐步执行代码，就像我在上面所做的那样，跟踪数组的内容和相关变量，这样您就可以准确地理解您的代码在做什么。

Answer 3

除了内存管理中的明显错误之外，如果您首先对 removelist 数组进行排序，然后在该数组中从最后一个条目开始向后工作，则该方法通常可以变得更简单第一次进入。

这样做会改变 array 调整大小的方式，因为您将对不再受影响的条目进行调整大小（移动元素）。在您当前的代码中，您正在移动条目，并且在循环的后续迭代中，您需要使用现在要删除的 "invalid" removelist 一组索引重新访问那些移动的条目。

请参阅 mayaknife 和 user2079303 的回答以说明删除每个项目后无效条目的问题（从 removelist 数组中的最低条目到最高条目）。正如所指出的，即使使用 std::vector 也不会对您有所帮助，因为这个问题指出了用于删除元素的基本逻辑中的缺陷。

如果您要在 removelist 数组中倒退（我说 "might have addressed"，因为这还没有经过全面测试，所以您可以在当前代码中解决这个问题或多或少说明了要点）：

void removeelement(int* removelist)
{
    for(int i = 2; i >= 0 ; --i)
    {
        int index = removelist[i];
        array* elementToDelete = array[index];
        for(j=index; j < numofelements -2; j++)
        {
            array[j] = array[j+1];
        }
        delete [] elementToDelete;
        numofelements--;
    }
}

因此，在每次迭代中，removelist 索引仍然有效，因为您要从条目中的最高条目到最低条目进行删除。在纸上解决这个问题，你会发现如果你反转遍历 removelist 数组的方式，你应该看到它是如何工作的，而不是继续遍历 removelist 数组。

您的代码还有其他问题，例如将 malloc 与 delete[] 混合使用。这样做是未定义的行为——永远不要在 C++ 程序中像这样混合分配/释放方法。

话虽如此，这是您程序的另一个版本，但未使用手动内存管理：

#include <vector>
#include <algorithm>
#include <iostream>
#include <array>

struct element {
   int n;
};

int main() 
{
    std::vector<element> arr(5);

    for (int i = 0; i < 5; ++i)
       arr[i].n = i;

    std::array<int, 3> removelist = {1,3,4};
    // sort the list 
    std::sort(removelist.begin(), removelist.end());

    // work backwards, erasing each element
    std::for_each(removelist.rbegin(), removelist.rend(),[&](int n){arr.erase(arr.begin() + n);});

    // output results
    for( auto& v : arr)
       std::cout << v.n << '\n';
}

Live Example

注意反向迭代器 rbegin() 和 rend() 的用法，从而模仿 removelist 容器的反向遍历。

C++：从动态结构数组中删除元素并移动其他元素

C++: Remove element from dynamic struct array and shift other elements

c++

malloc

free

delete-operator