Deleting 1 element of an array

What is the best / most efficient way of doing this?

Well, an array is just a coniguous block of memory. You can't delete one element without leaving a 'gap' in your array, as you probably know. So the only way to delete one item is to create an array of size one less than the original. Then populate that new array with all the elements of the original array, bar the one you want deleted. You will need to use malloc() to get memory for the new array.

Code:

---

.
.
.
//assuming you want an array of ints.
int array1[10];

//populate the array with 10 ints
for(int j = 0; j < 10; j++)
    array[j] = /*some form of input*/;

//ask os for a new array, one less than array1
int * array2 = (int*)malloc(9*(sizeof(int)));

//remove element [5]
for(int i = 0; i < 10; i++){
    if(i == 5)
        continue;
    array2[i] = array1[i];
}

---

That will effectively remove one element from your array. I hope you weren't talking about the STL... LOL

To be ultra efficient, you could make your array sizes multiples of 4. This is efficient because on a 32bit computer (if that's what you're using) memory is addressed starting on double word boundaries. Now it's possible to retrieve an address from a none double word boundary, but an extra cycle or two are needed to 're-arrange' the returned address. Here is a simplistic example:

Imagine memory address start at zero(they do...) The x86 type CPU is hardwired to return data from it's memory in byte chunks, 4bytes at a time. These bytes are independant, in their own channels if you like. If you ask the CPU to get you the data stored at address 0, it will come back already in the correct order. But... If you ask it to return some data stored at an address not beginning on a double word boundary, the double word returned will be out of order. Why? It's because of the hard wiring. The first byte the CPU returns is always the one that begins on the dword boundary. The CPU puts everything back in order for you, but it takes a little bit of time.

That's going to extremes, and most compilers will arrange arrays efficiently for you, but, when you want the most out of something, those are the kinds of areas you'll need to look into.

Nick.

you mean you want to delete 1 element of an array allocated like this:

Code:

---

int* array = new int[SIZE];
//or
int* array = malloc(sizeof(int) * SIZE);

---

?

there is no way I'm aware of, if you want to do so, allocate each element alone.

Thank you, a very detailed reply makes things so much easier for us beginners. :)

Also, how about the possibility of bulding your array on the heap, using an array of pointers to point to each array element and just deleting the pointer you want to remove.

Is this possible?
If so, how would you go about it?

Thanks.

I dont know what you want to do but, it might be more easy to use lists than arrays

Are you reffering to linked lists?

If so, I haven't started to study them yet, so I have no idea about how to use them :(

etho,

When you use malloc(); you are getting heap memory. I forgot to mention the use of the function free(). You should do this before your program exits if you are using malloc();

Code:

---

.
.
.
int elements = 10;

int * array2 = (int*)malloc(elements*(sizeof(int)));

//do something with your new array

free(array2);    //tells the OS that it can use that memory
                        //again
.
.
.

---

You can be as dynamic as you wish with your allocation/deallocation of memory. malloc() itself, simply asks the operating system to return a pointer to some available heap memory. You should check that malloc() doesn't return NULL, as it will if no memory can be given. The operating system then 'remembers' not to let any other processes use your block of memory, as pointed to by array2 in our case.

As far as all that goes, it's really not the way of C++. C++ provides what's known as the Standard Template Library(STL). It's a collection of data structures and functions that can be used with any data types. I won't go into it here, but check out this quick example:

Code:

---

#include<iostream>
#include<vector>

using namespace std;

int main(void){

    vector<int> intvec;

    intvec.pushback(1);
    intvec.pushback(2);
    intvec.pushback(7);
    intvec.pushback(3);
    intvec.pushback(2);
    intvec.pushback(8);

    for(int j = 0; j< intvec.size(); j++){
        cout << intvec[j];

    return 0;
}

---

See how easy that is??? You can add things or take things willy nilly from vectors, and still use them like an array. I made a vector to hold ints, but you can make it hold anything you wish.

There's some stuff to think about, anyway. Hope I helped a bit.


Nick

Nick,

Thanks for the reply.
I'm trying to stay away from C so as not to fall into bad practice of mixing 2 lanuages, so i'm using new and delete. However, its very quite easy for me to interperet what you are saying with the malloc function. :)

I'm actually using an array of stuctures, not just a straight forward array. Is it possible to use vectors with this, or are they contained to normal data types?

Thanks.

-"I'm actually using an array of stuctures, not just a straight forward array. Is it possible to use vectors with this, or are they contained to normal data types?"-

The vector class is a 'template' class. That means that the types that it can handle are left 'open' until you choose which type you want. If you made a linked list in C++, you would normally hard code the type of object (that includes any type... int, char etc) that you wish to store in your list.
This is fine for the type you have hard coded, but it falls down pretty quick when you want to re-use the linked list code. It's easy to cut and paste, or even use search and replace to change all the references to a particular type, but when you start changing the functionality for specific types, or you re-use the code in lot's of different places, you have a maintenance problem. (That was a big sentence, did you take a breath??? :))

Now, the STL provides robust, efficient and typesafe data structures and functions for whatever you want to throw at them! You can make structs, pointers to structs, classes, pointers to class objects etc. As long as you declare which 'type' you want the STL data structure or function to work with, it'll do it well.

Code:

---

vector<int> int_vector;
vector<Nicks_Big_Special_Class> NBSC_vector //I really made that one!!
typedef struct* new_struct;
vector<new_struct> ns_vector;

---

So just try little things, see if it works, and build on what you have found. I couldn't speak highly enough of the STL. It's really a programmer's dream in my opinion.

Nick.

Aww comeon, i posted something but the engine lamed and it went to a search machine :(