Like Tree2Likes

Delete an element in a dynamic array?

This is a discussion on Delete an element in a dynamic array? within the C Programming forums, part of the General Programming Boards category; Ok as part of my project described here I was trying to delete a complete row and column of a ...

  1. #1
    C <3er
    Join Date
    Jul 2011
    Posts
    46

    Thumbs up Delete an element in a dynamic array?

    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

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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.

  3. #3
    C <3er
    Join Date
    Jul 2011
    Posts
    46
    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?

  4. #4
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,673
    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.

  5. #5
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by beta3designs View Post
    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.
    quzah likes this.

  6. #6
    C <3er
    Join Date
    Jul 2011
    Posts
    46
    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

  7. #7
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by beta3designs View Post
    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.
    Last edited by quzah; 08-04-2011 at 05:11 PM.
    tabstop likes this.
    Hope is the first step on the road to disappointment.

  8. #8
    C <3er
    Join Date
    Jul 2011
    Posts
    46
    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 ^^

  9. #9
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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.

  10. #10
    Registered User
    Join Date
    May 2010
    Location
    Naypyidaw
    Posts
    1,314
    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 ...

  11. #11
    C <3er
    Join Date
    Jul 2011
    Posts
    46
    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!

  12. #12
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,673
    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.
    Last edited by whiteflags; 08-05-2011 at 09:05 PM. Reason: More stuff.

  13. #13
    C <3er
    Join Date
    Jul 2011
    Posts
    46
    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

  14. #14
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Hope is the first step on the road to disappointment.

  15. #15
    C <3er
    Join Date
    Jul 2011
    Posts
    46
    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!
    Last edited by beta3designs; 08-19-2011 at 05:52 AM.

Page 1 of 3 123 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. dynamic array and losing data of the first element
    By fx69 in forum C++ Programming
    Replies: 9
    Last Post: 02-25-2010, 04:15 AM
  2. how delete 1th element of a sorted array
    By vicky_4040 in forum C Programming
    Replies: 4
    Last Post: 10-11-2009, 06:12 AM
  3. delete same array element in C
    By tasosa in forum C Programming
    Replies: 12
    Last Post: 04-09-2009, 09:36 AM
  4. Delete Samllest Array Element
    By ptysell in forum C Programming
    Replies: 5
    Last Post: 11-22-2004, 06:27 PM
  5. Cannot delete last element in array
    By Simon in forum C Programming
    Replies: 10
    Last Post: 09-12-2002, 08:29 PM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21