Sign in to follow this  
PixelStation

Dynamic array Delete function

Recommended Posts

Hey everyone.

I'm writing a dynamic array in C++ just as practise (since I've never done it before). I have written a template class that creates an array of type X and fills it one at a time until it reaches capacity and then resizes (some code below). I have an iterator class that can iterate in either direction. Pushing and popping all works beautifully for my purposes. My issue is how to handle deleting elements at a random point in the array.

I saw an article on a random website that suggested shuffling the data in the array back one (seems time consuming). Also thought that I could memcopy the data to a temp location, then memcopy it back to restore contiguity, but again I think that may be costly. Another idea I had was to keep track of the number of deletes (and store dummy data in the array) and once it had exceeded a certain threshold I would run a resize to restore the contiguity of the array... but the thought of that makes me feel dirty and that would make iterating messy.

The goal here is to have a container that I can iterate in either direction, push and pop and delete at any index at any time and still maintain contiguity in memory. I don't expect to delete all that often (most of the time I'll be using push/pop) so I think I'll end up going with the 2xmemcopy method.

Any ideas?

Thanks for reading :)

Share this post


Link to post
Share on other sites
Be aware that you cannot memcpy() non-POD data. Thus, copying the data to and from the temporary location will end up being more expensive than shuffling.

Shuffling isn't all that bad. If the client doesn't care about the order, they will use the "swap and pop" trick, if the order is important they can use the remove/erase idiom (if your interface supports these).

Share this post


Link to post
Share on other sites
Hmm.. I like the "swap and pop", I think I'll leave that as a possibility for a fast erase. Could you explain the "remove/erase idiom". This is what I'm looking for, I'm just having a hard time getting google to give me anything but tutorials on how to use STL vectors [img]http://public.gamedev.net/public/style_emoticons/default/dry.gif[/img]

Thanks for the reply :)

Share this post


Link to post
Share on other sites
The [url="http://en.wikipedia.org/wiki/Erase-remove_idiom"]remove/erase idiom[/url].

The main difference here is that any element will only be moved once during the remove() part of the algorithm, whereas if you do several "random access" erase calls then elements may end up being moved several times.

If your iterator types follow the standard library's conventions you should be able to use them directly with std::remove or std::remove_if.

Share this post


Link to post
Share on other sites
Ok, so if I understand correctly, the remove pass takes all the elements you want remove and puts them 1 past the end of the container, then the container takes care of filling the holes and re-sizing itself?

eg. I have a list like so;
a b C d C e C f

I want to remove all the C's so remove does this
a b [] d [] e [] f C (where [] are now blank spots)

and erase then shuffles all that data back
a b d e f [] [] []

and resizes
a b d e f

Is that right?

[b]Edit: [/b]I implemented a swap function as well as an erase function so I can use either method as needed. The erase works the way I stated above ^ and works just great (also uses the swap to shove each value down while shoving the erased one up). Since it's all contiguous, like you said it really doesn't have much of an impact to bubble erased the values out of range.

So I'm happy with my implementation and it's blazing fast :D (at least for my purposes it is) Edited by jrdmellow

Share this post


Link to post
Share on other sites
The standard remove algorithms don't leave "blank spots" (there is no such thing in general). What they do is traverse the range once, with two iterators, a read and a write iterator. The read iterator is moved to the next location we want to "keep", and this value is copied over the write iterator. In this way, each value we want to keep is copied either 0 or 1 times, regardless of the number of elements being removed. The write iterator is returned.

For your list: a b C d C e C f
std::remove would result in: a b d e f | e C f

std::remove is an algorithm, it doesn't know about the container so it cannot instruct the container to remove the last few elements. To do this, we pass the returned iterator (at the pipe mark) and end() to erase(), which removed the last 3 elements.

Remember, writing your own container is a fun learning exercise, but that is all it should be. You should use the standard containers in production code.

Share this post


Link to post
Share on other sites
Ah, yea.. I guess I didn't mean to say blank spaces. :P Oops.

Anyway, that cleared everything up! Thanks for your help :)

[quote name='rip-off' timestamp='1313328868' post='4848949']
Remember, writing your own container is a fun learning exercise, but that is all it should be. You should use the standard containers in production code.
[/quote]
Yea, I may be proud of my little container but it seems like it'll be very limited (and quite possibly very buggy). It definitely was a good learning experience though.

Share this post


Link to post
Share on other sites

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