I have an array of structs. I am trying to delete a list of elements from that array and shift other elements to the left. After shifting the elements I am trying to delete/free the memory at the end of the array which we don't require anymore. I have the following code:
#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++;
}
}
But delete [] array[j+1]; is causing an exception:
*** Error in `main': double free or corruption (fasttop): 0x0000000001861cb0 ***
I don't understand what's causing this. As many people have suggested in other forums, I am using the 'new' operator to create a new,dynamic element.
EDIT:
I made the following changes:
I changed for(j=index;j<numofelements-2;j++){ to for(j=index;j<numofelements-1;j++){
int index = removelist[i] to int index = removelist[i]-i
I removed delete [] array[j+1] put delete array[numofelements+1] outside both the for loops.
Though I had used delete only on one element, It dealloced memory for the other redundant elements as well, which is interesting.
This is the final code:
#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++;
}
}
I got it working using this code. But I am going to use std::vector as many of you suggested.
Apart from the obvious errors in memory management, the approach in general could have been made simpler if you first sorted the removelist array, and then work backwards in that array starting from the last entry going toward the first entry.
Doing this would have changed the way the array was being resized in that you would have been doing the resizing (shifting elements) on entries that will no longer be affected. In your current code, you are shifting entries, and in subsequent iterations of the loop, you need to revisit those shifted entries with a now "invalid" removelist set of indices to remove.
See mayaknife's and user2079303 answers to illustrate the issue of invalid entries after removing each item (going from lowest entry to highest entry in the removelist array). As pointed out, even a usage of std::vector would not have helped you, since this issue points out the flaw in the basic logic being used to remove the elements.
Here is how you might have addressed this in your current code if you were to work going backwards in the removelist array ( I say "might have addressed", since this is not fully tested, but it illustrates more or less the point being made):
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--;
}
}
Thus on each iteration, the removelist index will still be valid, since you're going from highest entry to lowest entry in the entries to delete. Work this out on paper and you see if you reversed the way you iterated through the removelist array, you should see how this works, as opposed to going forward through the removelist array.
You also have other issues with the code, such as mixing malloc with delete[]. Doing so is undefined behavior -- never mix allocation / deallocation methods like this in a C++ program.
Having said this, here is another version of your program, but not using manual memory management:
#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';
}
Note the usage of the reverse iterators rbegin() and rend(), thus mimicking the backwards traversal of the removelist container.