removing an item from a char** array 1

[bitwise]

I have a runtime char** array. Now assuming all allocation is done correctly (which it is), how could I remove an element from this array? I don't want to replace the element I want to remove it completely. Example:

I have:
array[0] = "string1";
array[1] = "string2";
array[2] = "string3";

I want to be able to remove any index - for example let's say index 1. How could I make the array now look like this:

array[0] = "string1";
array[1] = "string3";

The results have effectively removed "string2" and repositioned the contents of the array. Is there a simple way to do this in C with an array w/o having to implement linked list or something.

Thanks,
-bitwise

 

[rbobbitt]

Not really, this is an *ideal* job for a linked list or a binary tree or a hash table or similar ADT, depending on your data and what you need to do with it. It isn't tough to do this with plain "arrays," the big disadvantage is that it's very inefficient when compared to using data structures like those mentioned above.

Basically (using your example above), you'll have to free memory for array[1]. Then iterate through the remaining elements, "shifting" them down one space. At some point, you'll probably want to shrink the memory that holds your "array" of pointers using realloc().

Post your code if you get stuck.






Russ
bobbitts@hotmail.com

http://home.earthlink.net/~bobbitts

 

[bitwise]

Yeah, that is what I figured - remove, reposition, realloc. I know a linked list is perfect for this job and I would implement it if I had the time and if it was a big deal, but the problem that it is solving just isn't a huge part of the app. Thanks for the post - now I know for sure.

-bitwise

 

[Guest_imported]

Depends on how often you wish to add. Using hashtables, binary trees etc is fine on big lists. If your list is relatively small, removing itens *can* be done rather trivially if you remember that an array of starings is a array of pointers to char.

static char test[4] = {
"test1",
"test2",
"test3",
"test4"
};

you cound simply say

test[0] = test[1];
test[1] = test[2];
test[2] = test[3];
test[3] = NULL;

It rather depends on the tradeoff between size and speed you must make yourself. As a general hint (from a pro) don't make it more complicated than ABSOLUTELY neccesary. The good ol' K.I.S.S. principle.

Eowine
.

 

[rbobbitt]

static char test[4] = {
"test1",
"test2",
"test3",
"test4"
};

This should be:

static char *test[4] = {
"test1",
"test2",
"test3",
"test4"
};

If the strings are dynamically-allocated (not the case above obviously), the pointer must be freed first. And yes, if the list is small, removing items and readjusting the array is not very expensive compared to using linked lists, etc. and may even be faster, depending on how you design your list.

Russ
bobbitts@hotmail.com

http://home.earthlink.net/~bobbitts

 

[bitwise]

Hmm, the array will probably never grow over 5 items. In light of that, it really wouldn't be that expensive of an operation. So I wrote this function to do it. Does it look as efficient as it can be?

/* 'index' is the item to be removed */
static int delete(int size, int index, char* array[])
{
int x;
for(x=index+1;x<size;x++)
{
strcpy(array[index], array[x]);
index++;
}

size--;
realloc(array, size);
return size;
}

What about the function memcpy(), could that possibly be used in some way to speed things up? Not that this is slow, but it is inefficient on a large scale.

-bitwise

 

[rbobbitt]

You don't have to copy the data at all. Since you're using pointers, you can just reassign the pointers:

/*** untested ***/

static int delete(int size, int index, char* array[])
{
if (index>=size || NULL==array[index]) {
/* error, either index is out of bounds
* or value at index is &quot;empty&quot;
*/
return 1;
}
/* free memory for the item */
free(array[index]);

/* start at the place where the item was
* removed and iterate through the rest
* of the elements
*/
for (x=index;x<size;x++) {
if ((x+1)==size) {
/* one item deleted, last element becomes
* &quot;empty&quot;
*/
array[x]=NULL;
} else {
array[x]=array[x+1];
}
}
/* return success */
return 0;
}

I've changed the semantics of your function because the function always deletes one item from the array (if possible), so the user can easily calculate this.

You don't want to realloc() the entire &quot;array&quot; every time you delete an item. realloc() is an expensive function, so you should only do it periodically. If your list will only contain 5 items at the most, I wouldn't even bother.

At any rate, your realloc() call needs some work:

realloc(array, size);

Instead, you should do something like this:

char **tmp=realloc(array,size * sizeof *tmp);

if (tmp!=NULL) {
/* success, assign array the shortened memory */
array=tmp;
} else {
/* realloc() called failed, do whatever's
* appropriate
*/
}

Since array is a double pointer you need to multiply size by the pointer size. The temporary pointer is necessary because if the realloc() call fails, you need a way to access the originally-allocated memory. If you set your only pointer to it to NULL (which a failed realloc() call will do) you've lost your last reference to it and can't free it, creating a memory leak.

Russ
bobbitts@hotmail.com

http://home.earthlink.net/~bobbitts

 

[bitwise]

Thanks for the tips - I'll be sure to change that over.

-bitwise