Delete an element in a dynamic array?

**beta3designs** · 08-04-2011

Ok as part of my project described here I was trying to delete a complete row and column of a 3d dynamic array some kind of 2d matrix of strings...
Well I'll try to ask the simple question for 1d arrays so I can extend it to multidimensional arrays... Let's suppose I have a dynamic allocated array and I have n elements and I want to delete an element of it, so that now the array has n - 1 elements... My question is, is there a simple way of doing this? And if there isn't which I think is the answer to that, my second question is:
I think maybe the best way of doing this is, copying one array element by element, to another array which has size n-1, except the element I wanted to 'delete'?
But then I'll end up having two arrays in stead of one... Let's say I don't want to use another array...
Is it then the best way to do this to shift all elements except that one I want to delete and then reallocating the memory to n-1?
Thank you very much! ;D

**tabstop** · 08-04-2011

Given the (completely traditional) way you were allocating your 2D matrix:

deleting a row will be pretty easy -- you just have to reassign the row pointers after the deleted row (move them up one spot) and free the row you're not using anymore/
deleting a column will be obnoxious, as you'll have to actually move data around, and realloc every row to the new size (unless you just say to heck with that and use a bit more memory than you really need).
If you find yourself deleting more than maybe once, you may want to consider linked lists, unless you need the random access.

**beta3designs** · 08-04-2011

Oh nice, so Instead of reallocating the memory I need to free it? Or is it the same? I mean let's say I reassign my row pointers which is moreless what I had thought of when I said shifting the elements (for the 1d array example) then should I reassign the memory to be one row less or should I just free the last row? Thanks!
I won't need to delete more than one at a time so I don't think I need linked lists right now but thanks for the tip

P.S: By completely traditional do you mean it's bad to allocate my 2d matrix like I was doing or something or is it just a comment?

**whiteflags** · 08-04-2011

Oh nice, so Instead of reallocating the memory I need to free it? Or is it the same?

You can realloc the first dimension, because you only made one malloc call for the entire first dimension. The second dimension can't be done with one realloc call, you would have to use realloc for every malloc.

**tabstop** · 08-04-2011

Originally Posted by beta3designs

Oh nice, so Instead of reallocating the memory I need to free it? Or is it the same? I mean let's say I reassign my row pointers which is moreless what I had thought of when I said shifting the elements (for the 1d array example) then should I reassign the memory to be one row less or should I just free the last row? Thanks!

You shouldn't (necessarily) free the last row; you should free the row you want to remove. You can (and probably should) realloc the bunch-of-row-pointers if you want, but an extra pointer isn't much extra.

P.S: By completely traditional do you mean it's bad to allocate my 2d matrix like I was doing or something or is it just a comment?

I was just trying to give a little context for those people who didn't click your link to the other thread.

**beta3designs** · 08-04-2011

Sorry I got a bit lost then you mean I should free the row I want to delete, reasign pointers and then reallocate the memory?

I was just trying to give a little context for those people who didn't click your link to the other thread.

Ok ;D
Thanks in advance and sorry to ask the "same" question again but I'm not sure enough of what to do :P

**quzah** · 08-04-2011

Originally Posted by beta3designs

Sorry I got a bit lost then you mean I should free the row I want to delete

Like so:

1,2,3,4
5,6,7,8
9,0,1,2
3,4,5,6

There is our data. We want to get rid of the one starting with a 5.

1. Allocate 3 row pointers. (type **data = malloc( ROWS * sizeof *data ))
2. Assign the first row. (type[ 0 ] = olddata[ 0 ])
3. Assign the 3rd row. (type[ 1 ] = olddata[ 2 ]
4. Assign the 4th row.
5. Free the second row. (free( olddata[ 1 ])
6. Free our old row pointers. ( free( olddata ) )

Now lets do columns:

1,2,3,4
5,6,7,8
9,0,1,2
3,4,5,6

Get rid of the column starting with the 3.

1. Allocate the first row of N-1 columns.
2. Copy the first two values of the first row there.
3. Copy the fourth value there. ( newdata[0][ 2 ] = olddata[0][ 3 ] )
4. Repeat for each row. ( newdata[ ROW ][ COL ] olddata[ ROW ][ COLX ]
5. Free the old data.

You don't really want realloc in either of these examples, unless you are throwing out the last column or last row. In which case, since you would have already worked out how to do it without realloc, there's no real reason to do it for one special case.

Quzah.

**beta3designs** · 08-04-2011

Ok thanks very explanatory ^^
I'll try to code it and see if I get it right and I'll come back with the result

Thanks again ^^

**tabstop** · 08-04-2011

I was thinking realloc/copying in place (instead of the above malloc a new table and copy over) just because I have a bad habit of thinking "dynamic" = "large". But in any event, you never have more than one "row" of extra memory in use at any one time (either an extra set of row pointers, or one row of data) so you really won't have an outrageous memory footprint, plus the malloc solution allows for a little bit cleaner error checking I would guess.

**Bayint Naung** · 08-04-2011

erm, may be I don't get your question at all.
If you want to delete row from 2D dynamic array.
Let's say( I'll use quzah's example

For dynamic 2D array p. (type of p = int **)

Code:

p[0] =  {1,2,3,4}, p[1] = { 5,6,7,8}, ...

1,2,3,4
5,6,7,8
9,0,1,2
3,4,5,6

Code:

temp = p[1];
p[1] = p[2] ;  p[2]  = p[3];
free(temp);  // if you want to or ...

**beta3designs** · 08-05-2011

Ok, the problem with your solution quzah is that I should delete the olddata which I don't want to do I want to modify the original table (or data)... I coded this and it seems to work, it is what I tried to say about shifting rows and freeing the last one (which would be duplicated):

Code:

void delete_row(table *t, int n){
    int i;

    for(i = n; i < t->rows; ++i)
        t->cell[i] = t->cell[i + 1];

    // Decrease rows count
    free(t->cell[t->rows - 1]);

    --(t->rows);
}

But I don't know if this is ok or I'm misunderstanding something and I'll be having a memory leak... although it seems to work.
Thanks in advance again!

**whiteflags** · 08-05-2011

the problem with your solution quzah is that I should delete the olddata which I don't want to do I want to modify the original table (or data)..

The new pointers point to the same place as the old ones. I'm not sure I see the problem.

But I don't know if this is ok or I'm misunderstanding something and I'll be having a memory leak... although it seems to work.
Thanks in advance again!

You can't diagnose a memory leak based on what seems to work. If I were you, I would watch all the pointers in the table with a debugger and see how the function really works. You would end up losing a pointer value during the shifting step in this algorithm, if at all. I'm suspicious since your stated goal was to delete any row in a table, but you're fine with this:

I coded this and it seems to work, it is what I tried to say about shifting rows and freeing the last one (which would be duplicated):

This is not the same thing.

**beta3designs** · 08-06-2011

The new pointers point to the same place as the old ones. I'm not sure I see the problem

But I need to modify the table t, the function doesn't return anything it's a void and if I create new pointers I shall return them so I can work with them later shouldnt I? the function I'm coding needs to delete a row in table t not create a new table or pointers which don't contain that row... but maybe it's my problem that I don't understand what you are tryin to explain me with creating the new pointers, etc.? :S

**quzah** · 08-06-2011

You can't realloc something you pass and have the new pointer kept anyway.

Code:

void foo( int *a, size_t s )
{
    int * n = realloc( a, s );
    a = n; /* you'll have an invalid pointer as soon as this returns */
}

You always need a pointer-to-type to modify type through a function.

Quzah.

**beta3designs** · 08-19-2011

Sorry but I was a bit busy this week so I couldn't get to code this but here I am again, this is what I wrote with the algorithm quzah told me again:

Code:

/* delete_row: delete row n from table t */
void delete_row(table *t, int n){
    int i;
    char **data = malloc(t->rows * sizeof(char *));
    for(i = 0; i < n; ++i)
        data[i] = t->cell[i];
    for(i = n; i < t->rows; ++i)
        data[i] = t->cell[i+1];
    free(t->cell[n]);
    --(t->rows);
    free(t->cell);
}

But it doesn't work anyway, I'm getting:

Code:

warning: assignment from incompatible pointer type

In marked lines :S
Thanks in advance guys!

Thread: Delete an element in a dynamic array?

Thread Tools

Search Thread

Display

Delete an element in a dynamic array?

Similar Threads

dynamic array and losing data of the first element

how delete 1th element of a sorted array

delete same array element in C

Delete Samllest Array Element

Cannot delete last element in array

Tags for this Thread