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?
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.
Re: push_back on a vector crashing
Quote:
Originally Posted by
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.
You are reinventing the wheel -- std::stable_partition() does all of this work for you already.
Regards,
Paul McKenzie
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?
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
Re: push_back on a vector crashing
Quote:
Originally Posted by
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...
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
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 :(
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.
Re: push_back on a vector crashing
Quote:
Originally Posted by
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.
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
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.
Re: push_back on a vector crashing
Quote:
Originally Posted by
IntoCoding
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
Re: push_back on a vector crashing
Quote:
Originally Posted by
laserlight
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
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.
Re: push_back on a vector crashing
Quote:
Originally Posted by
laserlight
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
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.
Re: push_back on a vector crashing
Quote:
Originally Posted by IntoCoding
I know it says the pointers will get invalidated after push_back, so how exactly they get invalidated?
Basically, if the size after the push_back will exceed the capacity, there must be a reallocation. Once there is a reallocation, all pointers, references and iterators to elements in the vector are invalidated.
So, if you must use push_back and yet avoid reallocation, then you should use the reserve member function, but that assumes that you know the maximum number of elements that will be inserted.
Besides, there's still the issue that push_back pushes to the back, not the front.
Re: push_back on a vector crashing
Quote:
Originally Posted by
IntoCoding
Thank you all for the help. I am still looking over this code and trying to understand what is not working here:
The problem as pointed out by laserlight is that any operation on the vector that increases the vector's number of elements invalidates any iterators pointing to it.
A vector's internal representation is a dynamically allocated array. Therefore it must store its data in contiguous memory -- that maybe the key point you're missing.
If you forget about vector for a moment -- what if this was a non-vector implementation? You would have dynamically allocated memory to hold n StudentInfo objects. Then you write your loop, and you realize that to add another student at the end, you need to go find another chunk of contiguous memory to hold the next student and all the other previous students.
Code:
Student_info *allStudents = new StudentInfo[10];
//...
Student_info *pCurStudent = allStudents;
Student_info *pLastStudent = allStudents + 9;
//...
while (pCurStudent != pLastStudent )
{
// in here you add another student
}
How would that code look like to add a student?
1) You need to call new[] again to get the larger memory area.
2) You copy the old data to the new area.
3) You must reseat the pCurStudent and pLastStudent to point to the correct items in this new area
4) You delete the old data
It's point number 3 that is analogous to iterators being invalidated. If you didn't do step 3, the low-level while() loop would fail for the same reasons your vector implementation is failing.
Does that make things a little more clear?
Regards,
Paul McKenzie
Re: push_back on a vector crashing
Yes, this makes much more sense, thank you Paul and laserlight. I have revisited this code again and digged some more info on re-allocation online and I think I got it now. The problem I am having in my loop is that once there is a non-failing student found in the vector, that is, when if statement is true, it adds that student to the back of the vector and takes care of any re-allocation needed. But then I am not doing anything with my iterator, and so next time it goes through a while condition, it might be pointing to the same element as before, and so I end up adding that element infinitely at the end of the vector. But then I tried incrementing my iterator in the if statement, that sometimes runs, sometimes doesn't. Well, I guess, my main question is answered so it is now up to me to get it to work.
Thank you very much for your help. I am so glad I found this forum and some experts who can really help.:wave:
