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

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

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)

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.