We help IT Professionals succeed at work.

Removing all items in an array list in C++

veeaechone
veeaechone used Ask the Experts™
on
Need assistance in completing the section on removing all items in an array list.  I would like someone to talk me through on how to correct the code I currently have. Remove-All.doc
Comment
Watch Question

Do more with

Expert Office
EXPERT OFFICE® is a registered trademark of EXPERTS EXCHANGE®
You already have a function to remove "all items  in an array list":
  void clearList();   //Function to remove all the elements from the list   //After this operation, the size of the list is zero.   //Postcondition: length = 0;   void clearList();
Your removeAll method removes "all occurences of an item from the list". So, just put an infinite loop around the body of this method, and break out when seqSearch returns an invalid location.

Also, the length-- should be moved before your existing for-loop.

You can improve performance by adding a second parameter, location whose default value is 0, to seqSearch.

Author

Commented:
would it be better to start from here?


template <class elemType>
void arrayListType<elemType>::removeAll(const elemType& removeItem)
{
      int loc;

      if(length == 0)
            cerr<<"Cannot delete from an empty list."<<endl;
      else
      {
            loc = seqSearch(removeItem);

            if(loc != -1)
                  removeAt(loc);
            else
                  cout<<"The item to be deleted is not in the list."
                        <<endl;

            
      }
} //end removeAll
>> would it be better to start from here?
Yes, now you are reusing removeAt() - good. And it fixes the the out-of-bounds problem in your original version.

To remove all the occurrences of the item, add an infinite loop, for(;;) after the else and break out when
loc < 0.

Just display "The item to be deleted is not in the list." if no items were deleted. (new length != old length)

Author

Commented:
I'm still working on this, but I'm not getting anything to work yet.  I'll keep trying.
Do you have any questions? Also, you can post what you have and I'll give you a tip.

Author

Commented:
I have tried so many different things.  I'm just curious...were you able to get the program to run correctly?
I got the following results. Is this what you want?
=========================================
$ g++ arrayListTemplate.cpp
$ ./a
List 11: The list you entered is: 1 2 0 1 2 0 1 2 0 1

Line 14: Enter the item to be deleted: 0
Line 17: After removing 0, the list is:
1 2 1 2 1 2 1
$ ./a
List 11: The list you entered is: 1 2 0 1 2 0 1 2 0 1

Line 14: Enter the item to be deleted: 1
Line 17: After removing 1, the list is:
2 0 2 0 2 0
=========================================

Author

Commented:
Yes, it is.  LOL!  You make it look so easy!!
Experience, study, and exercising makes you stronger.

Author

Commented:
Back to my problem...using your suggestion will I still be including
 loc = seqSearch(removeItem);?
If you don't use seqSearch, then how will you find what you are looking for? You have already tested this, and it works, right? So, why not use it?

Is there a question of efficiency that you may be thinking about? Recall that I said earlier:
>> You can improve performance by adding a second parameter, location whose default value is 0, to seqSearch.
For this particular problem, I recommend just getting the functionality working; and then if you like, we can talk about what is inefficient about the solution, and a simple way to improve it.

Author

Commented:
I just want to keep it as simple as possible.  I have a tendency to over complicate things.  I will try a few more things then get back with you.  Thanks for hanging in there.
Keep things simple as possible, but no simpler. You should talk about what issues are related to "over complicate things". You may actually be on to something useful, and not realize it unless you speak out. Don't be shy about discussing anything.

Author

Commented:
I know this is wrong, but am I getting anywhere?

template <class elemType>
void arrayListType<elemType>::removeAll(const elemType& removeItem)
{
      int loc;

      if(length == 0)
            cerr<<"Cannot delete from an empty list."<<endl;
      else
      {
            loc = seqSearch(removeItem);

            for(loc = 0; loc < length; loc++)
         if(loc != -1)
                  removeAt(loc);
            else
                  cout<<"The item to be deleted is not in the list."
                        <<endl;
            
      }
      
} //end removeAll
You are making progress - since you want to remove possibly more than one item, you have added a loop.

What compiler and debugger are you using? I may be able to help you better understand your function by using a debugger.

I see that you compute loc to find the first slot where the item is. And you do delete it. Good.

There is some inconsistent code for you to think about.
>> for(loc = 0; loc < length; loc++)
In this loop, loc is never negative. Yet your next line, if(loc != -1), tests if loc is negative.
   

Author

Commented:
Ok, I see your point.  If I set them both at zero I still do not get the desired result.  Am I on the right track or is there more I'm not seeing?

Author

Commented:
I am using Visual Studio 2008.
Set a breakpoint at
     loc = seqSearch(removeItem);
and hit F5 to run the program in debug mode.

When it stops at the above line, then hit F10 repeatedly to step through the loop. Look carefully at the values of loc as it changes; and look at the resultant array each time you step over
     removeAt(loc);

Also, the first time you are at seqSearch and removeAt, hit F11 to step into these functions, and then hit F10 to step through them. Again look at the change in the variables as you walk through the program. First guess what the change should be; then hit F10, and verify that your guess was right.

If you are currently uncomfortable with the debugger, then add cout statements to give you this information.
If you have any questions about VS debugging, let me know.
Whenever I get stuck on an routine, I throw away the computer for awhile and get out a paper and pencil or sometimes a deck of cards is useful.

>> The list you entered is: 1 2 0 1 2 0 1 2 0 1

Now write this down on paper. Select all items with a "2" to be removed.
Starting left to right, write down sequentially how you would proceed manually.
Show the progression of the list as you make progress.
How do you know when to stop?
Do the above sequentially - don't think of programs or loops - just pencil and paper (if you find yourself over-complicating this little exercise, then ask a 7-year old to do this for you - from left to right, one step at a time).

After doing this exercise, now bring in this sequence two friends, named seqSearch, who will be willing to return the first location of "2" in this list, and removeAt who is willing to remove this list entry.

Again, write down the progression of this list and which friend helped you. Do this sequentially - don't think of programs or loops. Write down exactly when you ask a friend to help you, and what information they give you when they do help you.
Fixing your original routine in the current way will be a good learning experience; and you are very close to a solution. If you just need to get something done quickly, I see that you have a "remove" function. You could just call that routine repeatedly until there are no more of the particular item found in the list. But, you still need to figure out how to stop the loop.

BTW - an infinite loop can be implemented as:
for(;;) {
...
}

Author

Commented:
I appreciate all your help but I've run out of time for this one.  I will award the points for your patience and attentiveness.  I'm just a slow learner.

Author

Commented:
Just wanted to let you know I figured it out!  Thanks!
I'm glad you figured it out! For this particular problem it was very important that you figure it out yourself (I hope you did it yourself). Earlier I said that getting this to work was the important first step; and then at least be aware of the efficiency of the particular implementation.

Assuming that you did not change the design much, and just figured out the bugs in the design, then it is likely that the algorithm is very inefficient.

Even if you do not have time to make it efficient, it is important (if you are planning a career in CS) to understand how inefficient it is. Here's an extreme example to make the illustration of the problem easier. Suppose you have 10000 entries; and every 25th entry, you have the number 1234; and you want to remove all of these entries having 1234.

For this particular array, you should ask yourself how many comparisons of 1234 will the function make and how many move operations it performs before returning. Then just think about this - is there anything that can be done to significantly improve. If you post the code of your solution, I'll do two things for you - I'll test it to make sure it works for multiple cases, and I'll start the ball rolling a little on the efficiency issue. Sometime, if you do get time, you can pursue the efficiency issue further in another question.

BTW - In the future, you are not supposed to award points based on good intentions, or time spent, or effort - just award if you learned something of value pertinent to the question. (There are some exceptions to this rule if you run out of time to continue or abandon a question - then the moderators may have to make a decision.) In this thread, I know that you learned some things so I don't see an issue with awarding points.

Overall, your code had a very nice look about it. So, keep up the good work. I hope to work with you again.

Author

Commented:
It was your guidance that allowed me to figure it out so you deserve the points...and I did complete it on my own.  It is not perfect, but it will get me by.
Good for you!
>> but it will get me by
This is actually an industry standard for many companies. If it weren't, there would never be a need for monthly or yearly releases - the first release would be perfect! I think you will do well.