17 replies to this topic

[Chad Smith]

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.

[Álvaro]

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.

[Waterlimon]

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)

[Servant of the Lord]

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, 28 January 2013 - 01:33 PM.

[Chad Smith]

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.

[Paradigm Shifter]

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.

[Álvaro]

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.

[Servant of the Lord]

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, 28 January 2013 - 03:46 PM.

[Paradigm Shifter]

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

[rip-off]

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!

[Chad Smith]

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!

Actually thanks for that. Because I'm not far into my CS degree (mostly a theory class studying ideas of some techniques) the ideas taught aren't always fully explained and just the basics behind them. Although I of course have known about recursion and have used it before (I'm sure a loop would had prolly been better), did know about all that on recursion. Though I did know a little about the runtime on it (did study that a little bit last semester).

Tomorrow I plan to work on this fully to see what I can come up with. Did a little reading and I think I have some ideas. Thanks everyone!!

[Khatharr]

Code reviewer's dictionary:

 

Curse (v) \ˈkərs\ - To say a bad word.

Recurse (v) \ˈhwät thə hel\ - To say a bad word more than once.

[Chad Smith]

Code reviewer's dictionary:

 

Curse (v) \ˈkərs\ - To say a bad word.

Recurse (v) \ˈhwät thə hel\ - To say a bad word more than once.

lol.

 

Also I talked to my my professor today.  She said that I do need to preserve the order.  She would like us to move every element after the one you are removing to the left.  This is what I figured she would want actually.

 

Sadly I do not like this project really.  Mostly because I don't think I would ever use an array for what she wants us to do (in the class we haven't gotten to other data structs to use so she just describes everything we lean as implementing it as an array). Because of this I am a little lost on what to do exactly on removing the element, then preserving the order by moving every element afterwards to the left.

 

If I could get some ideas, maybe some pseudo code or something that would stay within the guidelines of this site.  I have every other part of the project finished as it was pretty easy, but I guess because I would have never thought of using an array for this I am not very sure how to use arrays to do this.

 

Thanks for any help.

Edited by Chad Smith, 29 January 2013 - 05:56 PM.

[Paradigm Shifter]

Pseudocode you say?

remove ith_element(array, i):
while i < array.size - 1 do
{
array[i] = array[i+1]
i = i + 1
}
array.size = array.size - 1

/*cocking formatting bugs on this site*/

Edited by Paradigm Shifter, 29 January 2013 - 06:07 PM.

[Chad Smith]

Pseudocode you say?

remove ith_element(array, i):
while i < array.size - 1 do
{
array[i] = array[i+1]
i = i + 1
}
array.size = array.size - 1

/*cocking formatting bugs on this site*/

 

That was pretty close to what a function that I just started writing after I thought about during my last class this evening.  Works great right now.

 

I just pass in the array, the number of elements by reference, and the element to delete.  Everything gets updated perfectly.  Thanks everyone!  

[Khatharr]

It's something that you'd get yelled at for professionally, but instructors have to build coursework around manipulating what the class has covered already, so if you've learned arrays and loops then she's going to throw together arbitrary exercises using arrays and loops just to get your fingers moving. It's kind of like practicing katas at the dojo - you endlessly repeat pointless motions so that when it's time to spar the actions are automatic and you can focus on what to do rather than how to do it.

[Chad Smith]

It's something that you'd get yelled at for professionally, but instructors have to build coursework around manipulating what the class has covered already, so if you've learned arrays and loops then she's going to throw together arbitrary exercises using arrays and loops just to get your fingers moving. It's kind of like practicing katas at the dojo - you endlessly repeat pointless motions so that when it's time to spar the actions are automatic and you can focus on what to do rather than how to do it.

 

Yea I understand that.  The class thought is beyond the first two programming courses you take at a University really.  So we all know loops, arrays and all that.  The assignment is a first part assignment just to get us going this semester really.  I believe we will later take this assignment and move it to use Sets something we are studying now.  It's not quite a Data Struct class though we are studying and implementing some basic data structs in a very basic way (sometimes too basic that our programs will actually leak memory as they don't have us go more advanced and have write the remove/delete code for some of these).

 

Though I should know that what we are doing must help me later on as the University is rated pretty high in Computer Science in the country.  Some of it just seems odd to do (I don't like writing some code that is very basic that could self destruct and leak memory).  

[rip-off]

I don't like writing some code that is very basic that could self destruct and leak memory

Then don't. Write a proper implementation. You will not be penalised for going beyond the call of duty, and you'll learn a lot in the process. That said, get your program working the way the university expects first, and ensure you have a copy of that first (hint: version control is your friend).