push_back on a vector crashing
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 1 of 2 12 LastLast
Results 1 to 15 of 18

Thread: push_back on a vector crashing

  1. #1
    Join Date
    Apr 2012
    Location
    Wichita, KS
    Posts
    9

    Unhappy push_back on a vector crashing

    Hi Guys,

    Could someone please help me figure out what I am trying to do here. I have a function that takes a vector of structures(in this example single structure is a student record) and returns that same vector after doing some re-arrangements to it. So I have a while loop to go through the vector and check each element to see if the student passed or failed the class. If it passed, I want to add that element back to the existing vector (push_back into it). If it failed, I don't want to do anything. At the end, I want to resize the vector to only how many students passed, since every time I push_back passed student into the vector, I increment int p and that way I will know how much to cut at the end. Here is the code:

    Code:
    vector<Student_info> extract_fails(vector<Student_info>& students){
        vector<Student_info>::iterator it = students.begin();
        int p = 0;
    
        while(it != students.end()) 
        {
            if (!fgrade(*it)) { // if student didn't fail
                p++;
                students.push_back(*it); // add to the beginning of the vector
            }
            else
            {
                ++it;  // do nothing, go to next record
            }
        }
        students.resize(p); // cut the vector to contain only the first p elements (so I return the vector of only those students who passed the class)
        return students;
    }
    The problem is that my program totally crashes somewhere along these lines and stops working. I am suspecting that after push_back operations, my iterators on the vector are invalidated and I really have no idea where it starts next in the while loop.

    Any thoughts?

  2. #2
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,245

    Re: push_back on a vector crashing

    If a reallocation happens when you do a push_back, all iterators to the elements of the vector are invalidated.

    In this case, it looks like you want to create a new vector containing the Student_info of students who passed (which means that the function name could be misleading). Instead of doing this round-about method, it would be simpler to write:
    Code:
    vector<Student_info> extract_fails(const vector<Student_info>& students)
    {
        vector<Student_info> passed;
        for (vector<Student_info>::const_iterator it = students.begin(), end = students.end(); it != end; ++i)
        {
            if (!fgrade(*it))
            {
                passed.push_back(*it);
            }
        }
        return passed;
    }
    You could also consider using a generic algorithm instead of the explicit for loop, or use auto instead of verbosely specifying the iterator type.

    By the way, your comment that it is done to "add to the beginning of the vector" is wrong. push_back adds to the end of the vector (i.e., push to the back). If you want to add to the front, use a std::deque with push_front.
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  3. #3
    Join Date
    Apr 1999
    Posts
    27,422

    Re: push_back on a vector crashing

    Quote Originally Posted by IntoCoding View Post
    Hi Guys,

    Could someone please help me figure out what I am trying to do here. I have a function that takes a vector of structures(in this example single structure is a student record) and returns that same vector after doing some re-arrangements to it.
    You are reinventing the wheel -- std::stable_partition() does all of this work for you already.

    Regards,

    Paul McKenzie

  4. #4
    Join Date
    Apr 2012
    Location
    Wichita, KS
    Posts
    9

    Re: push_back on a vector crashing

    laserlight

    Thanks for your reply. You are absolutely right about creating a new vector and storing the passed records into it. I already had this program working perfectly, until I came over this exercise which is asking me to rewrite this function I posted to use resize method. I used to call erase method to remove the failing students from the vector. But they want me to rewrite it to use resize and I have no idea if I should keep the vector or use lists instead for this...

    here is the ex.:

    Rewrite extract_fails function so that instead of erasing each failing student from the input vector students, it copies the records for the passing students to the beginning of the students, and then uses resize function to remove the extra elements at the end of students.

    I was also confused as to how they imagine copying records of the passing students to the beginning of the students... Then I thought maybe they meant using lists to accomplish this?

  5. #5
    Join Date
    Apr 1999
    Posts
    27,422

    Re: push_back on a vector crashing

    For an example:
    Code:
    #include <algorithm>
    
    bool isPassingGrade(const Student_info& info)
    {
        return !fgrade(info);
    }
    
    vector<Student_info> extract_fails(vector<Student_info>& students)
    {
        // Partition students -- passing is on left of partition, failing is on right of partition
        vector<Student_info>::iterator it = std::stable_partition(students.begin(), students.end(), isPassingGrade);
    
        // iterator "it" is the partition point, so erase failures starting there
        students.erase(it, students.end());
        return students;
    }
    All of that code that you're writing is in those few lines.

    Regards,

    Paul McKenzie
    Last edited by Paul McKenzie; June 1st, 2012 at 04:38 AM.

  6. #6
    Join Date
    Apr 1999
    Posts
    27,422

    Re: push_back on a vector crashing

    Quote Originally Posted by IntoCoding View Post
    laserlight

    Thanks for your reply. You are absolutely right about creating a new vector and storing the passed records into it. I already had this program working perfectly, until I came over this exercise which is asking me to rewrite this function I posted to use resize method. I used to call erase method to remove the failing students from the vector. But they want me to rewrite it to use resize and I have no idea if I should keep the vector or use lists instead for this...
    Use std::distance() to determine how much to resize.

    If you look at my version, the number of elements that are good start from the beginning of the vector until the "it" iterator is reached. The distance() function counts the number of elements between two iterators. So I would use it to determine the number of good students, and then resize from there.

    The trick is this -- read up on the C++ library and what is available to you. Nothing in your assignment says to not use the algorithm functions. If you're doing anything that requires erasure, movement, etc. then there is a better than even chance that an algorithm or set of algorithms do this job already. You just need to know which ones to use. The best part about using algorithms is that they never fail if called with the proper arguments, unlike writing your own for-loops with logic to do all of this work within the loop.

    I won't go into it too much, since this is your assignment. I can almost guarantee you will be questioned on it by the teacher if you use anything posted here, so you better do self-study on what was posted.

    Regards,

    Paul McKenzie
    Last edited by Paul McKenzie; May 31st, 2012 at 09:55 PM.

  7. #7
    Join Date
    Apr 2012
    Location
    Wichita, KS
    Posts
    9

    Re: push_back on a vector crashing

    Paul McKenzie,

    That std::stable_partition() trick is really awesome and replaces how many lines of code! I tried it and worked just fine. I just started learning C++ and I have yet to learn about all these smart methods. And I completely agree with you that this really does the job and it's simpler and much stable then writing your own. But the thing is, if you are learning to code, the best way to learn is write your own stuff, break it down so that you really understand what you are doing. And so I am still puzzled as to how they wanted me to rewrite that function to use resize, and even though they never said not to use library algorithms, I don't think they expected students to do that, and that's why they specifically mentioned which methods to use and where to insert what... But anyway, I really appreciate your help on this and I really liked the proposed solution.

    BTW, I am not student anymore, I am learning C++ to become a developer at work (currently working for a different department) and so haven't touched my C++ since college, but now really trying to go in depths to be able to pass the interview which I heard is tough

  8. #8
    Join Date
    Apr 2012
    Location
    Wichita, KS
    Posts
    9

    Re: push_back on a vector crashing

    Oh, I was just looking up the reference on the stable partition algorithm. I see that it returns an iterator type pointer as a separation border between the partitioned values. This is so neat. I am just thinking in how many other algorithms I wrote it could have saved me. I need to spend more time browsing C++ library, seriously. Thanks so much for sharing this.

  9. #9
    Join Date
    Apr 1999
    Posts
    27,422

    Re: push_back on a vector crashing

    Quote Originally Posted by IntoCoding View Post
    Oh, I was just looking up the reference on the stable partition algorithm. I see that it returns an iterator type pointer as a separation border between the partitioned values. This is so neat. I am just thinking in how many other algorithms I wrote it could have saved me. I need to spend more time browsing C++ library, seriously. Thanks so much for sharing this.
    Thanks -- glad to be of help.

    Don't be ashamed -- the partition() and stable_partition() algorithms seem to be overlooked or not known by many programmers, so they spend their time fighting (and fixing) while() and for-loops to do the work of arranging the data.

    Regards,

    Paul McKenzie
    Last edited by Paul McKenzie; June 1st, 2012 at 04:42 AM.

  10. #10
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,245

    Re: push_back on a vector crashing

    Quote Originally Posted by Paul McKenzie
    Don't be ashamed -- the partition() and stable_partition() algorithms seem to be overlooked or not known by many programmers, so they spend their time fighting (and fixing) while() and for-loops to do the work of arranging the data.
    For the job of removing the failures, I would prefer to use remove_if with the range based erase. partition is sensible when you really want to keep all the elements; stable_partition is sensible when you want to keep all the elements while maintaining the original relative order.
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  11. #11
    Join Date
    Apr 1999
    Posts
    27,422

    Re: push_back on a vector crashing

    Quote Originally Posted by IntoCoding View Post
    But the thing is, if you are learning to code, the best way to learn is write your own stuff, break it down so that you really understand what you are doing.
    Yes, but when you advance past that point, any competent C++ programmer can write (and debug) for() and while() loops to do whatever they want them to do. However that is not the big picture.

    The point of the algorithms is that you no longer have to do this work -- the goal then for you as a programmer is to take working components, i.e. containers, algorithms, and other aspects of the C++ library, to create a stable, relatively bug-free program as quickly as possible. Also, the programs become almost immediately understandable to any C++ programmer who knows the language library.

    Take your example, and assume it wasn't commented. I would have to look at the loop a few times to

    1) Understand what you're doing in that loop. I may need to look at it two or three times to see what is being done, and even then maybe I won't be sure what you're doing.

    2) I would need to test if that loop actually works correctly, and if not, fix the bugs.

    On the other hand, my example using stable_partition -- assume it wasn't commented. A C++ programmer

    1) knows right away what is being done (stable_partition, erase(), begin(), end(), etc. are well-defined and documented), and

    2) that same programmer knows by sight the code works correctly all without having to test or debug anything, saving time not having to do these steps.

    Regards,

    Paul McKenzie

  12. #12
    Join Date
    Apr 1999
    Posts
    27,422

    Re: push_back on a vector crashing

    Quote Originally Posted by laserlight View Post
    For the job of removing the failures, I would prefer to use remove_if with the range based erase. partition is sensible when you really want to keep all the elements; stable_partition is sensible when you want to keep all the elements while maintaining the original relative order.
    Yes, remove_if() would work, but many times, a programmer doesn't understand that remove_if() invalidates all of the "bad" items, even though they're still in the container. This leads to bugs if the code then tries to do something with the bad items (other than erasing them from the container). I have personally seen this, where the programmer used remove_if(), but then thought that calling a member function of the removed items would work.

    So yes, remove_if() if it is perfectly clear that the bad items will definitely not be used for any purpose after the remove_if() is called. Otherwise, stable_partition() or partition().

    Regards,

    Paul McKenzie
    Last edited by Paul McKenzie; June 1st, 2012 at 05:19 AM.

  13. #13
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,245

    Re: push_back on a vector crashing

    Quote Originally Posted by Paul McKenzie
    Yes, remove_if() would work, but many times, a programmer doesn't understand that remove_if() invalidates all of the "bad" items, even though they're still in the container. This leads to bugs if the code then tries to do something with the bad items (other than erasing them from the container). I have personally seen this, where the programmer used remove_if(), but then thought that calling a member function of the removed items would work.
    The use of a generic algorithm conveys information about the intention of the author through its name. So, if it is a bug to use the removed elements, then using partition instead of remove_if won't help: you're just conveying the wrong idea to the reader, even as you may avoid an immediate problem as the elements that are later used are valid, even though they should not have been used.
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  14. #14
    Join Date
    Apr 1999
    Posts
    27,422

    Re: push_back on a vector crashing

    Quote Originally Posted by laserlight View Post
    The use of a generic algorithm conveys information about the intention of the author through its name. So, if it is a bug to use the removed elements,
    The particular case I'm referring to dealt with calling "delete" on a container of pointers. The memory had to be deleted, but the remove_if() algorithm was used beforehand.

    So even though it seemed sound to call delete on a set of pointers that have been "removed", it turned out not to be the case. Simple error, but could have been avoided.

    Regards,

    Paul McKenzie

  15. #15
    Join Date
    Apr 2012
    Location
    Wichita, KS
    Posts
    9

    Re: push_back on a vector crashing

    Thank you all for the help. I am still looking over this code and trying to understand what is not working here:

    Code:
    vector<Student_info> extract_fails(vector<Student_info>& students){
        vector<Student_info>::iterator it = students.begin();
        int p = 0;
    
        while(it != students.end()) 
        {
            if (!fgrade(*it)) { // if student didn't fail
                p++;
                students.push_back(*it); // add to the beginning of the vector
            }
            else
            {
                ++it;  // do nothing, go to next record
            }
        }
        students.resize(p); // cut the vector to contain only the first p elements (so I return the vector of only those students who passed the class)
        return students;
    }
    I want to understand where the program is crashing in particular. I know it says the pointers will get invalidated after push_back, so how exactly they get invalidated? Vector is random access, right? So is it just switching all pointers in round robin manner, or adjusting all pointers down the vector by incrementing/decrementing them? I need to understand, so if for instance my it points to the very first element in the vector and I am through the first iteration of that loop, suppose I get true value in the if statement, I get down to students.push_back(*it). After I pushed that same element to the back of that vector, what is my it next time I traverse the loop? Or immediately after the push_back? I am not expecting you to tell me the exact value of that iterator, rather to what it points now, to which element in the vector, previous, subsequent, current...

    Thanks, and sorry for asking so many questions. I just can't leave that piece of code without having a good understanding of what worked and what didn't and why.

Page 1 of 2 12 LastLast

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center