push_back on a vector crashing

[IntoCoding]

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:

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?

[laserlight]

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:

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:eque with push_front.

[Paul McKenzie]

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

[IntoCoding]

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?

[Paul McKenzie]

For an example:

#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

[Paul McKenzie]

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:istance() 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

[IntoCoding]

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

[IntoCoding]

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.

[Paul McKenzie]

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

[laserlight]

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.

[Paul McKenzie]

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

[Paul McKenzie]

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

[laserlight]

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.

[Paul McKenzie]

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

[IntoCoding]

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

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.