Sign in to follow this  

Deleting the end of an array

This topic is 4094 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

hey everyone, im fairly ne to programming and am currently writing a graphics engine for pocket pc and am wondering if this
template<typename T>
void DeleteEndOfArray(T* Array, int Size, int NumToDelete)
{
    T* element = Array + Size - NumToDelete;
    for (int i = 0; i < NumToDelete; i++)
    {
        delete element++;
    }
}


will delete the end of the array and saying
delete[] Array;
later in my code will still work or if i have to use something like this
template<typename T>
T* DeleteEndOfArray(T* Array, int Size, int NumToDelete)
{
    T* tempArray = new T[Size - NumToDelete];
    memcpy(tempArray, Array, Size - NumToDelete);
    return Array;
}


or some one knows another alternative (i was going to use std::vector but read some were that it is to slow on embedded devices is this true?) thx in advance all EDIT: Typo left of element++ [Edited by - Julian90 on September 29, 2006 6:54:07 AM]

Share this post


Link to post
Share on other sites
You'll end up in troubles with the code your presented. It isn't possible to delete any of the singular element of an array. Ie. if you allocated the array with new[] (and hopefully delete it with delete[]) you cannot delete a single element of the array with "delete". Beside, the code is deleting the same pointer quite many times which will hang your program.

You could write a resize function which makes a copy of the array and adds new elements to the end or drops out the elements which don't fit.

Otherwise, I'd go for std::vector. It keeps the data in continuous array and I assume that only overhead comes when resizing the array.

Cheers

Share this post


Link to post
Share on other sites
Unfortunately, it is very likely that you'll get an exception !
When allocating an array, the compiler must stash its length somewhere.When you call operator delete[] , it retrieves the length to perform the necessary deallocation.

I would suggest using std::vector , or create your own linked-list template classes, but honestly - how slow can std::vector be ?

Share this post


Link to post
Share on other sites
When you call new/new[], that memory allocated can only be freed by a corresponding call to delete/delete[] respectively.

No syntax exists for freeing part of an array.

Share this post


Link to post
Share on other sites
Assuming we are talking about an array created with new[], no it won't work. It will crash horribly. You can only call delete e; if e is created by new as a single element like e=new element();

If you are determined to use raw arrays (and I'm not getting into the argument about std::vector because I don't know enough about embedded systems) then if you want to make the array smaller, you will have to allocate a new, smaller array, copy the elements in (correctly) and delete the original array.

You may be better off using a linked list. While this adds the overhead of a pointer-sized group of bytes to each element in your list, it means you can delete individual elements without having to move the rest of the elements in the list.

Also, bear in mind that using memcpy like that in your second example will only work correctly with PODs and will fail silently with unpredictable results if the array contains classes with dynamic data. std::copy would be a safer alternative and should reduce down to std::memcpy for PODs anyway.

Share this post


Link to post
Share on other sites
Quote:
Original post by grekster
Quote:
Original post by Pro-XeX
....... how slow can std::vector be ?


itll depend on how his compiler implements it wont it?


To be a bit more precise, it depends on how well the library implements it versus how I, or you, implement it. I tend to assume a commercial standard library writer can do a better job than I can.

Share this post


Link to post
Share on other sites
Quote:
Original post by grekster
Quote:
Original post by Pro-XeX
....... how slow can std::vector be ?


itll depend on how his compiler implements it wont it?



I don't think a compiler 'implements' anything, std::vector has constant time insertion and removal of elements at the end, I don't think this should differ
on embedded systems !

Nevertheless, if you use std::vector<T*> and store only pointers
to your objects, you can still use a function like

void DeleteEndOfArray(...)

If speed is such a tough issue, then you might look into using your custom
allocators for the std::vector class !

Share this post


Link to post
Share on other sites
ok ill probally swap to std::vector but a linked list is out because i need to garuntee cach integrity, also i just tested this


int* array = new int[100];
delete (array + 5);
delete [] array;


and it runs fine but i think if array+5 were allocated for something else before the delete [] array thats when id see problems thx all

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
1.
"std::vector has constant time insertion and removal of elements at the end"
this is wrong. std::list has this, not a vector.

2.
dont do delete when you use new[]
this will run in debug builds, but in a release build this will do something unexpected.
your "delete" doesn't free any memory.

3.
if you try to do something like this, reallocate your array.
this means allocate one with more space, then memcpy and add the new element,
and then delete [] your old array.

4.
memory allocations are slow.
so if you "new" and "delete" for every object, this decreases speed.
you should do this in "batches".
e.g. reserve space for 4 objects, when its full, your next array will be 16 objects, if it gets full very fasten, then alloc space for 32 objects etc.
do the same when deleting.

5.
use std::vector, it does the thing mentioned in 4. very effectively.
and it makes use of processor-specific things.
it WILL be faster than your implementation, believe it or not.

6.
if its still too slow, just use another lib.
(stlport runs on mobile devices, i think. or try boost or sth.)

7.
when adding/deleting things very often, use a std::list, not an array

8.
a cache just stores recently used data to speed up access on often used things.
theres no diffence if you use a vector or a list...
(well, there can be, but only if you use objects in your array that are smaller than the processor bus, i dont think you are doing bitshifting etc. to keep your array-entrys small...)

Share this post


Link to post
Share on other sites
actually I am doing a lot of bit shifting but ignoring that I don't allocate or deallocate a large number of objects frequently but when I am doing my allocation I know the maximum number of objects that I will need to allocate but I will generally only end up allocating about one tenth of this so is there any way I can get std::vector to take advantage of this? thx again

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
yes, of course.
you can tell the std::vector how many objects you would like to have space for:

std::vector vec;
vec.reserve(1000); //room for a thousand ints

int cap, cnt;
cap = vec.capacity(); //returns 1000
cnt = vec.size(); //returns 0 (no objects in it)

and you can access it like any array with the brackets

int x = vec[0];

and its "managed", you dont need to free any memory or sth.
(but you may, if you want to)

Share this post


Link to post
Share on other sites
Quote:
Original post by Julian90
ok ill probally swap to std::vector but a linked list is out because i need to garuntee cach integrity, also i just tested this


int* array = new int[100];
delete (array + 5);
delete [] array;


and it runs fine but i think if array+5 were allocated for something else before the delete [] array thats when id see problems thx all


That is well into the grounds of undefined behaviour. If it worked, it is by sheer chance and could cause horrible problems on another occasion.

Before you can decide whether or not to use std::vector, you need to profile to see if it is genuinely causing speed or space issues. I'd be surprised if it is since if you don't use vector, you'll probably just have to reimplement everything it does anyway.

Share this post


Link to post
Share on other sites

This topic is 4094 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this