C++：動的構造体配列から要素を削除し、他の要素をシフト

Question

私は構造体の配列を持っています。その配列から要素のリストを削除し、他の要素を左に移動しようとしています。要素をシフトした後、私はもはや必要としない配列の最後にメモリを削除/解放しようとしています。

#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 *** 

私はこれを引き起こしているのか理解していない私は、次のコードを持っています。多くの人が他のフォーラムで提案しているように、私は '新しい'演算子を使って新しい動的要素を作成しています。

EDIT：

私は、次の変更を加えました：

私はint index = removelist[i]-i

へfor(j=index;j<numofelements-1;j++){に

int index = removelist[i]をfor(j=index;j<numofelements-2;j++){を変更し、私はdelete [] array[j+1]を削除し、両方のためのループの外delete array[numofelements+1]を置きます。 私は1つの要素に対してのみ削除を使用しましたが、それは他の冗長要素に対してもメモリを解放しました。これは面白いです。

#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

removelistアレイを最初にソートした後、最初のエントリに向かう最後のエントリから順番にそのアレイを処理すると、メモリ管理の明白なエラー以外に、一般的にアプローチが簡単になる可能性があります。

arrayは、影響を受けないエントリに対してサイズ変更（要素のシフト）を行っていたという点で、arrayのサイズが変更されていました。あなたの現在のコードでは、エントリをシフトしています。ループのその後の反復では、削除されたインデックスが今度は "無効な" removelistのインデックスセットでシフトされたエントリを再訪する必要があります。

各アイテムを削除した後で無効なエントリの問題を説明するための回答を参照してください（removelistアレイの最下位エントリから最高エントリまで）。指摘したように、std::vectorの使用法であっても、この問題は要素を削除するために使用されている基本ロジックの欠陥を指摘するので、役に立たなかったでしょう。

removelistアレイで逆方向に作業する場合は、現在のコードでこれをどのように対処していますか（これは完全にテストされていないためですが、作られているポイント）：削除するエントリの中で最も低いエントリに最高のエントリーから行っているので、

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を前に進めるのではなく、これがどのように動作するかを確認する必要があります。

---

また、このようなdelete[]とmalloc混合などのコードと他の問題を、持っています。そうすることは未定義の動作です.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コンテナの横断。

Answer 2

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]が最初に削除されるはずではないと考えています。

2回目の反復中にarray[4]が再び削除されます。これはすでに削除されたオブジェクトを指しているため、動作は未定義です。

さらに、内部ループのarray[j] = array[j+1]のために、削除されたポインタのコピーがアレイに残っていますが、ポインタの一部が上書きされ、メモリがリークします。アルゴリズムへの単純な修正：最初にインデックスでポインタを削除し、削除後に要素をシフトします。

さらに：ループが意図どおりに機能した場合、最初の2回の反復で配列の要素が削除され、numofelementsが3になります。次に、配列のインデックス4の要素を削除します。インデックス0..2に有効なポインタを持つ。恐らく除去される指標はソートされなければならない。その場合は、シフトを計算するためにインデックスremovelist[i] - iを削除することでこれを修正することができます。もう一つの巧妙な戦略は、Paulが示唆しているように、指数を高いものから低いものに取り除くことです。考慮すべき

---

他のもの：

• プログラムはarrayに割り当てられたメモリリークが発生します。この簡単なプログラムには問題はないかもしれませんが、重要なときに忘れないように割り当てられたすべてのメモリを解放する習慣を持つことは良い考えです。
• mallocは、具体的かつ合理的な理由がない限り使用しないことをお勧めします。通常は、mallocを使用する合理的な理由がありません。
• RAIIコンテナを使用せずにダイナミックメモリを割り当てるのは悪い考えです。 std::vectorを使用した場合、このプログラムのバグは避けられました。

Answer 3

この行：

delete [] array[j+1]; 

要素のアレイが 'アレイ[J + 1]' によって指し示さ削除します。ただ一つの要素ではなく、要素の配列を割り当て

array[i] = new element; 

をするので、削除は唯一ならびに単一の要素を削除する必要があります。しかし、「配列は[jは+ 1]」この行で初期化されました。たとえば、

delete array[j+1]; 

ただし、間違った要素が削除されています。理由を調べるために、 'array'を初期化するループがA、B、C、D、Eと呼ばれる5つの '要素'構造体へのポインタを割り当てていると仮定しましょう。

removeelements

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]'にコピーされます。その「アレイ」の後に次の含まれています。この点「J」で

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

3はそう含ま「配列を削除[J + 1]」によって指し示さ「配列[4]」である要素を削除します'E'。

「numofelements」は次いで「numofelements」は今4であるため、除去される第二の要素は3である。4.

にデクリメントされ、内側のループは次のようになります。

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

' j 'は3に初期化されます。これは2より大きいため、ループの本体は実行されず、'配列 'は変更されません。

'j'が3 'であるため、配列[j + 1]を削除すると' E [4] 'が削除されます。取得。

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

：

は、これは、このような内部ループを与えるだろう。4.だろう削除される、「numofelementsは3」までデクリメントされるだろうと私たちは第三の要素に移動したい継続するためのプログラムでした

'j'は4に初期化され、ループの本体は実行されません。 'delete array [j + 1]'は 'array [5]'の指す要素を削除しようとします。これは 'array'の境界を超えており、例外が発生します。

他の人も示唆しているように、これを処理する最良の方法はstd :: vectorを使用することです。しかし、あなたのコードが構造化されている方法でさえ、std :: vectorはあなたに必要な結果を与えることはできません。なぜなら、ある要素を '配列'から削除すると、それに続くすべての要素のインデックスが変わります。 'removelist'のインデックスはもはや正しいとは言えません。

上記のように、コードを手動で実行して、配列の内容と関連する変数を追跡し、コードが何をしているのかを正確に理解できるようにすることをお勧めします。