1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: C++ Lists & Iterators

  1. Feb 16, 2010 #1
    We're only second semester programmers who don't know too much.

    1. The problem statement, all variables and given/known data

    Using lists and iterators, write a program which accepts string inputs from the console and outputs them in alphabetical order. If the whole program has to be rewritten, fine. I've spent way too much stupid time on it already.

    3. The attempt at a solution

    Here's a snippet of the code. I'm having problems writing out how to get the string to go BEFORE the first myList entry.

    Code (Text):
        list<string> myList;
        string myString;

        int i=1; //counter
        do
        {

            //ask for String
            cout << "Insert a string: ";
            //put string into myString
            cin >> myString;

            if (i==1)
                myList.push_back(myString);


            for (list<string>::iterator pos = myList.begin(); pos != myList.end() && i != 1; ++pos)
            {

                if (myString < *pos)
                {
                    myList.insert(pos, myString);
                    break;
                }

            }


            i++;
        } while (i<=STRINGS_TO_USE);
    -Extremely frustrated.
     
  2. jcsd
  3. Feb 16, 2010 #2

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Your code does indeed have a problem, but the issue cited above isn't the problem.

    I built a main around your little snippet of code.
    Code (Text):
    #include <list>;
    #include <string>;
    #include <iostream>;
    using namespace std;

    #define STRINGS_TO_USE 5

    int main (void)
    {
       list<string> myList;
       string myString;

       int i=1; //counter
       do {
          //ask for String
          cout << "Insert a string: ";
          //put string into myString
          cin >> myString;

          if (i==1) {
             myList.push_back(myString);
          }  

          for (list<string>::iterator pos = myList.begin();
               pos != myList.end() && i != 1;
               ++pos) {
             if (myString < *pos) {
                myList.insert(pos, myString);
                break;
             }  
          }

          i++;
       } while (i<=STRINGS_TO_USE);

       cout << endl << "List contents:" << endl;
       for (list<string>::iterator pos = myList.begin();
            pos != myList.end();
            ++pos) {
          cout << *pos << endl;
       }  

       return 0;
    }
    So, lets test this.
    Code (Text):

    prompt> gcc foo.cc
    prompt> ./a.out
    Insert a string: foo
    Insert a string: bar
    Insert a string: baz
    Insert a string: qux
    Insert a string: quux

    List contents:
    bar
    baz
    foo
    As you can see, the program has no problem with inserting "bar" before "foo". The problem is with the "qux" and "quux". Here is the program run with a slight rearrangement of the inputs:

    Code (Text):
    prompt> ./a.out
    ./a.out
    Insert a string: quux
    Insert a string: foo
    Insert a string: bar
    Insert a string: baz
    Insert a string: qux

    List contents:
    bar
    baz
    foo
    quux
    This time everything but the string "qux" was added to the list. One more time,
    Code (Text):
    prompt> ./a.out
    Insert a string: qux
    Insert a string: foo
    Insert a string: bar
    Insert a string: baz
    Insert a string: quux

    List contents:
    bar
    baz
    foo
    quux
    qux
    Can you see what's happening here?
     
  4. Feb 16, 2010 #3
    I've been staring at it and rearranging and rewriting for SIX Hours. The program was due 5 hours ago. I have done everything I can to understand how to fix it and I just can't. I am completely lost as to how to attack the problem in the problem.
     
  5. Feb 16, 2010 #4

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    With three different arrangements of the same strings for input, your code snippet worked correctly once. The one time where it did work correctly was when the last item (sort order) is input first.

    Keep it simple: Suppose STRINGS_TO_USE is 2 and the user types in "aaa" and then "zzz". What happens? Execute the code by hand. (Always a good exercise.)
     
  6. Feb 16, 2010 #5
    I've done that. I've drawn pictures. I've drawn tables. I've done everything I can.

    Even with two STRINGS_TO_USE (foo, bar), I can't figure out how to get the script to work with either order being entered.

    I *CAN'T* figure this out without some concrete help, something to point me in a direction. I'm beyond frustrated at this point.
     
  7. Feb 16, 2010 #6

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Before you can fix the problem you have to find out what the problem is.

    What is the problem here? It is *not* inserting an item before another item in the list. Your code has no problem with "foo" and "bar". It has a problem with "bar" and "foo".
     
  8. Feb 16, 2010 #7
    Look. I can't both check (myString>*pos) and (myString<*pos) in the same if statement. THAT's the problem. If I could understand the bug, I could fix it. I don't understand it, therefore, I can't fix it. I don't know HOW to find the bug because I'm obviously not familiar with the ins and outs of lists and iterators yet.

    So, the answer is, I can't define the bug. I can't isolate the bug. I don't know how to maneuver around the bug because this is BRAND NEW material for us. without experience with it, I have absolutely no way of knowing what I'm doing wrong.
     
  9. Feb 16, 2010 #8

    Mark44

    Staff: Mentor

    But you can check (myString>*pos) and (myString<*pos) in two different if statements, or a single if statement with an else clause. I think that might be what D H is getting at.
     
  10. Feb 16, 2010 #9
    I've tried that. But I can't figure out a way to differentiate when it's to .insert() after an entry and when it's to push_back because there aren't any more entries left.

    For instance. If I have this in myList:

    bar
    end
    simple
    tend

    and myString is now 'mom'. I can compare 'mom' to 'bar' and say (mom > bar?) {yes, do nothing}. then have the loop *pos to 'end' and check that (mom > end?) {yes, do nothing}. have the loop iterate again and check (mom > simple?) {NO, else myList.insert(pos, myString)} and it puts mom before simple and after end.

    However, if myString is 'your', I can comare 'your' to 'bar' and say (your > bar) {do nothing}, (your > end) {do nothing}, (your > simple) { do nothing}, (your > tend) {do nothing}.......at this point it's nonfunctional because I can't use the same else statement as above. I can't insert anything because there's nothing to compare 'your' to.. *pos is no longer at a valid point.

    THIS Is why I've been staring at this thing for HOURS longer than it should have ever taken.

    I HAVE NO IDEA HOW TO PROGRESS FROM THIS POINT WITHOUT SOME ABSOLUTE SCRIPT TO POINT ME IN THE RIGHT DIRECTION. I have until midnight to submit my program or it's a zero and it's pretty obvious that after nearly 7 hours on it, I'm not going to figure it out on my own.
     
  11. Feb 16, 2010 #10

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Think of this as a good exercise. You are trying to solve the problem before you know what the problem is. You most certainly can say what the bug is. Since you are having problem even finding your problem, here it is:

    Your program does not add an item to the *end* of the list. Any time the user supplies a string that is greater than the last element in the list that newly supplied string is dropped on the floor rather than pushed onto the end of the list.

    The job of the loop as written is to insert an string into the list if the object belongs somewhere before the last item of the list. The loop does not do the full job. You need some other code to handle the special case of an item that belongs at the end of the list.

    If you solve this problem, you can get rid of that ugly stuff dealing with i equalling one (the if statement before the loop) (i==1) and i being not equal to one (the second condition in the loop conditional). Think of it this way: The very first item added to the list can be looked at as being the end of the list.
     
  12. Feb 16, 2010 #11

    Mark44

    Staff: Mentor

    If the string you want to insert into your list is "greater than" each string already in the list, you need to append it to the list, making the list longer. That's what push_back is for, according to the docs.

    One way to keep track of this is to have a boolean variable that starts off each iteration as false, and is reset to true if a string is inserted or appended. Just a thought.
     
  13. Feb 16, 2010 #12

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    push_back() works. So does inserting before the end() of the list. The end() of the list is in a sense one past the last item on the list.
     
  14. Feb 16, 2010 #13
    You can't .insert() without comparing to *pos. And since there's nothing in myList on the first entry, you can't do the .insert().

    I've tried this too many times with no luck.

    still lost. clock is ticking. 8 hours now.
     
  15. Feb 16, 2010 #14

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Where did you get this idea? insert() doesn't check that a comparison was done before and doesn't check that the insertion will keep the list sorted. All insert() does is to insert an item into a specific location in a list. Period. One way to shuffle a list is to temporarily transfer the contents of a list to another list and then insert() the elements back into original list in random locations.

    There is absolutely nothing wrong with doing myList.insert (myList.end(), myString);. This will always put myString at the end of the list. The effect is exactly the same as myList.push_back (myString);. In fact, the Gnu c++ STL implements push_back() in terms of insert():
    Code (Text):

          void
          push_back(const value_type& __x)
          { this->_M_insert(end(), __x); }
     
  16. Feb 16, 2010 #15
    The very first thing I said in this thread was "We're only second semester programmers who don't know too much.". I don't have a frame of reference for what's right and wrong yet. We're still learning the basics. Therefore, I really don't have a platform to stand on that's secure enough to hold anything in my hands firmly. Iterators and lists were thrown to us today in class and we were told to complete this assignment after 15 minutes of 'lecture'. So excuse me if I don't have terminology right, or understand the basics of programming the way you do.

    I'm at the point where I don't care anymore. I think the Homework Helper status often gets in the way of actually HELPING someone who has no foundation upon which to derive the answer. I've been working on this thing NONSTOP since noon today with NOTHING to show for it and I'm on the verge of just closing it up and taking the zero. I've tried hundreds of builds trying to get it to work and you sit there and talk to me like I'm supposed to know this stuff inside and out, tearing apart the nuances of programming as an expert would.

    Sometimes, teachers have to give the answers in order for the student to understand what he's missing. I've helped numerous people with homework over the years who only 'got it' after seeing how it was done. The avoidance of such routines on this website often make it extremely frustrating to get help here.

    You've danced around actually helping me in a manner in which I need to continue and without it, I just can't finish the assignment. So I'll take the zero and fall behind in the class. That's just how it is. Whatever.
     
  17. Feb 16, 2010 #16

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Did you read posts #10 and #11?

    You are trying to make your insertion loop do too much. The solution is simple: Don't make your insertion list do everything. If that loop doesn't insert myString into the list then you know where myString has to go: At the end of the list. So just keep track of whether the insertion loop did something. If it did, you're done. If it didn't add the item to the end of the list.
     
  18. Feb 16, 2010 #17
    Of course I read the posts. I've read over this thread 157 times trying to extract something out of it. I've been through countless c++ reference sites, and web forums and you name it and I've read it.

    I've tried using booleans to do this a bazillion times. I don't know how to create the if checking within the for loop to be able to
    1.) insert myString if myList is empty
    2.) do nothing if myString > *pos
    3.) insert myString at end().

    I don't know how many ways I can say it. I CANNOT SOLVE THIS. I've attempted it for over 9 hours in dozens or even hundreds of ways with the knowledge I have. I simply DO NOT have the ability to put together a loop that does what I need it to.
     
  19. Feb 16, 2010 #18

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    You are trying to hard. All you need is a variable that indicates whether the loop successfully inserted the string into the list. If the loop didn't do the insert, add the item to the end of the list.

    Let's go over those three items one at a time.
    • insert myString if myList is empty
      You don't need to do this. You shouldn't do this. Doing so just makes the job harder. Leave the loop empty. Now the loop won't do anything because the list is *empty*. The status variable will indicate no success. Add the item to the end of the list.

    • do nothing if myString > *pos
      The if statement inside the loop has no else statement. You are already doing nothing if myString > *pos.

    • insert myString at end().
      insert (myList.end(), myString) works fine, as does push_back(myString).
     
  20. Feb 16, 2010 #19

    Mark44

    Staff: Mentor

    IMO, you seem to be equating "helping" with "giving the answer to."
    That might be true, but a student who has worked the problem through has a much greater understanding of the whole problem than one who has been shown the answer.
    It is a stated principle on this forum to NOT give answers, but instead, help students work toward them.
    D H and I (mostly D H) have given you what I think are good suggestions, WITHOUT ACTUALLY WRITING YOUR CODE FOR YOU. At every step of the way you have insisted that you just can't do this problem, and have all but asked for the code. That's just not how it works here.
     
  21. Feb 16, 2010 #20
    There's a point at which working backwards is beneficial as well. I'd say that attempting nonstop for nearly 10 hours is a good point to start looking to help from a different direction.
    Agree. But if after ten hours, the student *still* doesn't understand, the teacher should try a new approach. The teacher should have tried something different after the first few attempts didn't create that spark in the student's head.
    There's, again, a point at which the student turns to giving up in which he'll learn nothing at all in comparison to a student possibly understanding the material if the teacher gave it from a different perspective (i.e. backwards). A teacher is not a teacher if the student doesn't walk away with some satisfaction of knowledge.

    If you've done any research and looked into my other 250 posts, you'll see that there were only a handful of times where I was so lost that I couldn't go any further. Most of the time, the explanations given to me by the other Helpers were enough for me to figure it out. They didn't give me answers, either.

    There's a point in which giving NO answers is not helpful at all. The point is to help, in any ways possible, I'd think. But whatever.

    I've been having trouble with the logic behind the loop. If this had been said hours ago, I would have gotten further earlier. For whatever reason, I couldn't figure it out. Sometimes, it's in the *how* you say something. It's probably not efficient, or pretty, but I don't care much anymore at this point. It seems to work for 2 strings, and 5 strings, so I'm hoping it works for n strings.
    Code (Text):
    if (i==1)
            {
                myList.push_back(myString);
            } else
            {

                for (list<string>::iterator pos = myList.begin(); pos != myList.end(); pos++)
                {
                    if (myString < *pos)
                    {
                        myList.insert(pos,myString);
                        whatever = true;
                        break;
                    }
                   
                }

                if (whatever == false)
                {
                    myList.push_back(myString);
                }
            }
    I don't know how to do the loop without first putting the first element in with the if(i==1) statement. The for loop never starts because when it's empty, I don't know how to look at myString vs [something] to determine what to do.

    DH didn't have to explicitly give me the answer in code, but giving me the logic was the working backwards I was talking about. I spent TEN HOURS working with failed logic. I don't care if you don't agree, but helping me see the logic showed me how the problem was solved. And because of that, I can see my mistakes, and understand how the problem works now. ... which is infinitely further than I was when NO help was given to me.
     
  22. Feb 16, 2010 #21

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    I gave you a bit too much help. I might well get a warning from the powers that be.

    Anyhoo, try removing that initial processing (i.e., the if (i==1) {...}). You don't need it, and it may well cost you points. Just because the program works right does not mean you get a 100. Extraneous code typically merits a subtraction in an assignment. It can merit much worse in the real world.

    BTW, I don't see the pre-loop assignment to whatever. Presumably you are setting that to variable to false. Where? The best place for doing that is right before the loop.
     
  23. Feb 17, 2010 #22

    Mark44

    Staff: Mentor

    If you're talking about working backwards from the "answer," in the real world, there is often no answer to work backward from. Approaching the problem from a different angle is usually a good idea if one approach isn't yielding results.
    You spent ten hours on this; neither D H nor I did. Forty-one minutes after you posted this problem, D H responded. He took the time to enter your code in a complete program and analyze what it was doing. He gave suggestions for what you could focus your attention on. Instead of taking his advice, you complained about already working SIX hours on this problem, but didn't answer the question he asked.

    Each of your responses to pointed questions from him did not address what he was saying (at least you provided no code to show what you had tried), but instead complained that you couldn't do it or couldn't figure it out and so on. If I can speak for D H, he wasn't necessarily trying to teach you something, but rather trying to get you to realize what the code you presented was doing and why it wasn't working for you.
    I agree completely that different approaches are good, and different strokes for different folks. But I disagree with the "backward" part, as I interpret that to mean "give me the answer so I can understand how it was reached." Maybe that's not what you mean, but that's how it has seemed in this conversation.

    Also, having earned my living as a teacher for 21 years, I can speak with some authority about this endeavor. A few of my students did not walk away with some satisfaction of knowledge, in some cases because they were not prepared enough for the class they were in, and in others, because they weren't much interested in learning anything. On the other hand, I went out of my way to help those students who were interested in learning and put in some effort.
    No, I didn't look into any of your 250 posts. I spend a lot of time in this forum, but not so much that I have the time to look at all of the posts of everyone who posts a question here.
    You should count yourself lucky that you have a resource like this. When I went to college there was nothing like this around.
    And likewise, there is a point in which giving the complete answer is not really helpful, either, at least not in the long run. Are you saying that the responses you received in this thread were not at all helpful?
     
  24. Feb 17, 2010 #23

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Yeah. I wasted some of that time writing a working version of the code and then making a very terse working version of the code that would make IOCCC judges cheer (three lines to do the insertion, and no auxiliary boolean).

    I was trying to teach him something. How to debug, for one. How to code well for another. I often ask of leading questions as a teaching style. This style obviously wasn't work here, so I offered exitwound *a lot* of help. Far too much help, in my opinion.


    To all you struggling computer science students: Don't bang your head against the wall for hours, twiddling with the code until it kinda-sorta works. Learn to debug. Learn to execute your code by hand: Be the dumb computer against which you are hurling invectives and blunt objects. Learn to identify the simplest case that still elicits the problem. Learn to back away from your code.
     
  25. Feb 17, 2010 #24
    I'll just make a few points and then walk away from this.

    • I spent many hours on this before I even came to these forums.
    • Posting every single code attempt I tried in these forums would have meant me actually trying much less code overall. The more time I spent here, the less time I was in Visual Studio actually TRYing to solve the problem.
    • I'm a student barely scratching the surface of the material with an intent to learn. I wouldn't be paying $8000/semester if I didn't want to be in the class and have an interest in learning it. I'm looking UP at the pyramid. You're both looking down. It's not fair for you to say that I should be able to solve a problem in a few minutes the way you do because I don't have a foundation built upon which to draw conclusions, infer results, or to debug a glitch. In fact, I may not even *have* the tools to even know what my error might be.

      Looking at it from the field of view of a car owner. I may know how to turn the key to start it, how to operate it, and how to make it stop. But when it starts making clunking noises, I may be able to pinpoint where the noises are coming from, but that IN NO WAY means I have the ability to fix it myself because I may not have the necessary knowledge to tear it apart and understand how it all works.
    • If you think you gave me too much help, then you're absolutely 100% wrong. There is no way I could have figured that on my own. I would have given up and accepted the lost credit on the assignment. That was worth just closing the program and actually getting to bed. You would look me in the eye and tell me, as a tutor or a teacher, that it's better for me to accept the zero, learn nothing, and NEVER get an answer from you, than it is to give me "too much help" so that I may learn from it? That's ridiculous and unacceptable to me. If I posted this thread asking for a "do my homework", then I would accept your dismissal. However, I would think that out of compassion, and out of understanding, you would do everything in your power to get the student to understand the material he came here asking help with. If your title prohibits you doing that, then I will gladly find help elsewhere online. I'd rather *not* have the answer spoon fed to me anyway. I'm far too old to accept that and have learned it's not productive in any way. All I wanted was some **help**. And if you can't understand that sometimes giving "too much help" is a good thing, then you'll never understand my points.
    • I don't care any more about this assignment. I don't care if I lose points on it due to inefficiencies or clutter. I honestly don't care one iota about it. I spent an entire day trying to figure it out, bombed my Statistics quiz today because I didn't have time to study for it as a result. I honestly don't care what grade I get on it, even if it is a zero for being crap code. What's most comforting is that I got an answer I can now REFLECT back upon for help when I need it.
    • whatever's declaration was omitted from the final snippet.
    I'm done with this thread.
     
  26. Feb 17, 2010 #25

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Us giving you an answer so that you get a good grade is ethically unacceptable -- it's better known as cheating.

    Whether you learn from help is completely up to you.


    But in the analogy you are not a car owner -- you are a mechanic-in-training.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook