Jump to content
  • Advertisement
Sign in to follow this  
Chad Smith

Moving Elements in an array

This topic is 2089 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

First off I just want to say that this is a school assignment, so to keep this within the guidelines of this site I am not looking for a premade function or anything.  Just some ideas.  

 

This sounds like a simple problem but for some reason but I've never had to deal with it mostly because most of time I would just use std::vector in my projects.  Though because this is a school assignment, for this one we are not allowed to use std::vector but must use an array.

 

Let's say I have an array and I want to delete index 4.  I will need to fill in the gaps of the array by shifting all index's above 4 down.  I know this is getting in the range of a dynamic array, though in this example their will always be a set number of elements in the array.   I just need to move all elements down while the others just won't have anything in them but junk.  It is said in the assignment that we can assume the user won't access elements past a certain amount or check for the junk values.

 

Some of my ideas that maybe some of y'all could help me with to lead me in the right direction.

I was thinking a recursive approach of moving one element at a time until we get to the end of the array.

 

Next would be a loop until you reach the end of the array (seems it would close to the recursive approach, except looping instead).

 

These are the two ideas that I thought off.  Though I am unsure of the exact way to implement it.  Would I need to company every element of the array over to a new one?  Or what?

 

Thanks for any ideas or thoughts over this.  If you have any other ideas to present to me I am all ears.  Thanks.

Share this post


Link to post
Share on other sites
Advertisement

Next would be a loop until you reach the end of the array (seems it would close to the recursive approach, except looping instead).

That's how I would do it. You can also use the standard algorithm std::copy for this.

Share this post


Link to post
Share on other sites
I would use a for loop that moves every element to direction x by y units.

Note that the loop should start from the element at the direction where youre moving them (unless you make a whole new array and are actually copying all the values)

Share this post


Link to post
Share on other sites
Moving every element down costs you one copy (or one 'move-semantics' move if you are using C++11) for every element above the deleted element, but is necessary if you are preserving the relative order of the elements.

If the relative order of the elements in the array doesn't matter:

You could swap (std::swap()) the element you are deleting and the last element in the array. (Good: Three* copies or three moves (if C++11))
Or, since you're discarding the deleted element anyway, you could just copy (std::copy()) the last element over the deleted element. (Better: One copy)
Or, since you aren't saving the previous usage of the last element and only want one copy of it, you could just use move-semantics (C++11) to move (std::move()) the last element over the deleted element. (Best: One move)

*temp = A, A = B, B = temp

Normally I wouldn't bother mentioning the costs of each option (pre-optimization is generally considered a bad idea), but for the sake of understanding the differences between the options I thought it relevant to the discussion.

This same information applies also to std::vector, since std::vector suffers from alot of the same limitations of a regular array (being held in a single continuous block of memory for faster reads and writes). These limitations don't apply to std::list though, since an std::list is optimized for insertions, movements, and deletions. Edited by Servant of the Lord

Share this post


Link to post
Share on other sites

Moving every element down costs you one copy (or one 'move-semantics' move if you are using C++11) for every element above the deleted element, but is necessary if you are preserving the relative order of the elements.

If the relative order of the elements in the array doesn't matter:

You could swap (std::swap()) the element you are deleting and the last element in the array. (Good: Three* copies or three moves (if C++11))
Or, since you're discarding the deleted element anyway, you could just copy (std::copy()) the last element over the deleted element. (Better: One copy)
Or, since you aren't saving the previous usage of the last element and only want one copy of it, you could just use move-semantics (C++11) to move (std::move()) the last element over the deleted element. (Best: One move)

*temp = A, A = B, B = temp

Normally I wouldn't bother mentioning the costs of each option (pre-optimization is generally considered a bad idea), but for the sake of understanding the differences between the options I thought it relevant to the discussion.

This same information applies also to std::vector, since std::vector suffers from alot of the same limitations of a regular array (being held in a single continuous block of memory for faster reads and writes). These limitations don't apply to std::list though, since an std::list is optimized for insertions, movements, and deletions.

 

Thanks for all this.

 

I am not entirely sure if our school compilers are updated for C++11 so I will have to log onto our CSE Machines to check that out.  I will look into everything to see what I should do.  

 

I also probably should make sure I'm allowed to use any of those from the standard library.  Professor has been somewhat picky on us using the standard library in some places.

Share this post


Link to post
Share on other sites
Deleting elements from the middle of an array is possibly the worst use-case for an array data structure, I hope your Prof tells you about that, IF you need preserve the relative ordering of the elements.

SotL's suggestion to move or copy the last element over the deleted one is the best method if the order is unimportant.

If the order needs to be preserved after deletion you should be using a linked list if this is a common use-case for the data. Other data structures such as a set implemented as a red-black tree are good if insertion and deletion is common and the members must be sorted ascending (or descending) at all times.

Share this post


Link to post
Share on other sites

If the order needs to be preserved after deletion you should be using a linked list if this is a common use-case for the data. Other data structures such as a set implemented as a red-black tree are good if insertion and deletion is common and the members must be sorted ascending (or descending) at all times.

Depending on the size of your container and the size of the objects contained in it, the std::vector solution might actually be very good in practice: Node based containers require lots of dynamic memory allocation and are less cache friendly.

In any case, I also hope the professor discusses all of these things.

Share this post


Link to post
Share on other sites

I am not entirely sure if our school compilers are updated for C++11 so I will have to log onto our CSE Machines to check that out.  I will look into everything to see what I should do.  
 
I also probably should make sure I'm allowed to use any of those from the standard library.  Professor has been somewhat picky on us using the standard library in some places.

You don't have to use the standard library for it. Even if you don't have move-semantics (one move cost for moving the last element over the deleted element) you could still do a simple copy (just making it one copy cost).

<array element at elementToDelete> = <array element at lastElement>

That's alot faster than...
for every element above elementToDelete
: <previous element> = <current element>


But, as mentioned, doesn't preserve the relative order of the elements - which may have been part of the class assignment's requirements. Edited by Servant of the Lord

Share this post


Link to post
Share on other sites

Álvaro, on 28 Jan 2013 - 21:42, said:

Paradigm Shifter, on 28 Jan 2013 - 21:33, said:
If the order needs to be preserved after deletion you should be using a linked list if this is a common use-case for the data. Other data structures such as a set implemented as a red-black tree are good if insertion and deletion is common and the members must be sorted ascending (or descending) at all times.

Depending on the size of your container and the size of the objects contained in it, the std::vector solution might actually be very good in practice: Node based containers require lots of dynamic memory allocation and are less cache friendly.

In any case, I also hope the professor discusses all of these things.

Yeah, those containers are a bit overkill for something like a high score table... was going to mention that. However, if performance isn't important then I reckon the simplest implementation should be used instead (and a list has the simplest interface for deleting an object from the middle of the container - assuming you know where it is and don't have to search for it beforehand).

Share this post


Link to post
Share on other sites

I was thinking a recursive approach of moving one element at a time until we get to the end of the array.

Note that iteration is preferred to recursion in almost all cases. Loops are simpler to reason about in most popular languages. Recursion is most typically used for the kind of problems where you have keep track of where you were. rather than just where you are.

 

As an example of why you might avoid recursion, recursion relies on the algorithm completing before stack space is exhausted. Some platforms default to a small amount of stack space that doesn't grow (e.g. executables on Windows typically have up to one Megabyte of stack space). Thus your application may now have an unintentional arbitrary limit - once the data size crosses a certain threshold it may crash!

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!