Sign in to follow this  

vector and interators problem

This topic is 4222 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello, Im trying to solve a problem in my text Accelerated C++ (chapter 5 ex 6) but having no luck. Can anyone help out. (Sorry but the book has no associated forum) I have a programe that allows a user to input student names and their associated grades. This is stored in a vector of Student_info where Student_info is a structure containing the necessary elements to store the name etc. The exercise asks me to try different ways of removing those students who failed from the vector. One way is to inspect and test each element in the vector and to insert (vector.insert(...)) all the pass structures to the begining. Then the vector is resized to the number of pass structures copied which ultimately results in all the fail grades being chopped off. Whether this is an efficient method or not is the aim of the exercise. I tried to implement this alogorithm however the results were different. As a result i decided not to resize the vector and instead simply view the result of the inserting as a way to test the alogrithm. This is my code for the extract function

using std::vector;

void extract_fails(vector<Student_info> &students) //students is a record of students and thier grades.
{

	std::vector<Student_info>::iterator iter = students.begin();
	std::vector<Student_info>::size_type counter = 0; //to count how many pass grades have been inserted into the front
	while (iter != students.end())
	{
		if (!fgrade(*iter)) //this funciton simply tests if a passed grade is less than 70 percent.
		{
			//if this is a pass grade insert it before the begining
			students.insert(students.begin(), iter, iter);
			counter++;
		}
		iter++; //go to the next student record in the vector
	}
	//resize
	//students.resize(counter); //i have removed this for testing purposes
}



If i enter the following students data Adam fail Barry fail Charlie pass it should result in the following vector Charlie pass Adam fail Barry fail but it shows Adam fail Charlie pass Barry fail. could anyone comment as to why its doing this? Surely if i use students.insert(students.begin(),....) it should insert the requested elements BEFORE the begining of the vector. But it doesnt. Any help would be greatly appreciated.

Share this post


Link to post
Share on other sites
You have two problems. First of all:

students.insert(students.begin(), iter, iter);

Will not insert anything into the vector. The iterators should form a half-open range, which means the first iterator points to the first element in the range and the second iterator points to one element beyond the last element in the range. By specifying that the first element is also one element beyond the last element you are specifying an empty range (all elements following iter (first iterator passed) except for those elements from iter (second iterator passed) onwards). You should probably use the single element insert, which requires you to pass a value rather than two iterators.

Secondly if your insert did ever insert anything into the vector it would invalidate iter.

Σnigma

Share this post


Link to post
Share on other sites
Indeed, the insert() member function will invalidate iterators when something actually gets inserted. That's because everything gets conceptually "shifted over" to make room for the inserted element(s). The container makes no guarantees what will happen when you try to use an invalidated iterator - welcome to undefined behaviour land. For a std::vector in particular, it will often seem to be OK - it will pick up the data that was newly shifted into the same spot - but will sometimes explode (the insert may trigger a resize, which would mean the whole shebang gets copied off to somewhere else in memory, and the old chunk of memory no longer necessarily even belongs to your process).

You are encouraged to think about the performance ramifications of that movement of elements, since "whether this is an efficient method or not is the aim of the exercise".

The standard library provides algorithms std::remove and std::remove_if, which can be used for a task like this. If you "remove" failing grades, these algorithms will put (copies of) the passing grades at the start of the vector, but will not change the vector's size, and make no guarantees about the contents of the elements past that point. (You are encouraged to think about how it may help performance to not make that guarantee; specifically about how the algorithm might be implemented similar to what you are currently doing and in light of the above discussion).

Share this post


Link to post
Share on other sites

This topic is 4222 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this