🔒 Locked

Dynamic array Delete function

Started by jrdmellow Aug 13, 2011 at 7:57 PM 6 replies 1.9k views

Original Post

Aug 13, 2011 at 7:57 PM

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

rip-off

Aug 13, 2011 at 9:04 PM

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).

jrdmellow

Aug 13, 2011 at 10:06 PM

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

Thanks for the reply

rip-off

Aug 13, 2011 at 10:39 PM

The remove/erase idiom.

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.

jrdmellow

Aug 13, 2011 at 11:05 PM

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?

Edit: 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 (at least for my purposes it is)

rip-off

Aug 14, 2011 at 1:34 PM

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.

jrdmellow

Aug 14, 2011 at 2:14 PM

Ah, yea.. I guess I didn't mean to say blank spaces. Oops.

Anyway, that cleared everything up! Thanks for your help

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.

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.

rip-off

Aug 14, 2011 at 5:22 PM

If you're interested in more feedback you could post your current implementation.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.