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!

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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: C++ Lists & Iterators
  1. Linux listing (Replies: 7)

Loading...