Thread: Deleting 1 element of an array

  1. #1
    Registered User eth0's Avatar
    Join Date
    Dec 2003
    Posts
    164

    Deleting 1 element of an array

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

  2. #2
    Registered User
    Join Date
    Feb 2003
    Posts
    60

    here's how I'd do it...

    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.
    Last edited by NickESP; 01-10-2004 at 06:04 AM.
    "It compiled, let's ship it!"

    Guitar Australia
    my site for some easy tutorials.

  3. #3
    Registered User glUser3f's Avatar
    Join Date
    Aug 2003
    Posts
    345
    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.
    Last edited by glUser3f; 01-10-2004 at 05:51 AM.

  4. #4
    Registered User eth0's Avatar
    Join Date
    Dec 2003
    Posts
    164
    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.

  5. #5
    Registered User
    Join Date
    Nov 2003
    Posts
    53
    I dont know what you want to do but, it might be more easy to use lists than arrays
    Its all a matter of willpower

  6. #6
    Registered User eth0's Avatar
    Join Date
    Dec 2003
    Posts
    164
    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

  7. #7
    Registered User
    Join Date
    Feb 2003
    Posts
    60

    linked lists and the heap

    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
    "It compiled, let's ship it!"

    Guitar Australia
    my site for some easy tutorials.

  8. #8
    Registered User eth0's Avatar
    Join Date
    Dec 2003
    Posts
    164
    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.

  9. #9
    Registered User
    Join Date
    Feb 2003
    Posts
    60

    The beauty of templates

    -"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.
    "It compiled, let's ship it!"

    Guitar Australia
    my site for some easy tutorials.

  10. #10
    Registered User
    Join Date
    Nov 2003
    Posts
    168
    Aww comeon, i posted something but the engine lamed and it went to a search machine
    -Felix
    Rots Soft
    If the facts don't fit the theory, change the facts.
    Albert Einstein (1879 - 1955)

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 4
    Last Post: 01-05-2008, 11:30 PM
  2. Replies: 19
    Last Post: 07-20-2007, 01:46 AM
  3. Replies: 6
    Last Post: 11-09-2006, 03:28 AM
  4. Deleting element from an array problem
    By xamlit in forum C Programming
    Replies: 5
    Last Post: 12-03-2005, 04:53 PM
  5. Struct *** initialization
    By Saravanan in forum C Programming
    Replies: 20
    Last Post: 10-09-2003, 12:04 PM