Accelerated C++, problem 5-6 (copying values from inside a vector to the front)

I'm working through the exercises in Accelerated C++ and I'm stuck on question 5-6. Here's the problem description: (somewhat abbreviated, I've removed extraneous info.)

5-6. Write the extract_fails function so that it copies the records for the passing students to the beginning of students, and then uses the resize function to remove the extra elements from the end of students.

(students is a vector of student structures. student structures contain an individual student's name and grades.)

More specifically, I'm having trouble getting the vector.insert function to properly copy the passing student structures to the start of the vector students. Here's the extract_fails function as I have it so far (note it doesn't resize the vector yet, as directed by the problem description; that should be trivial once I get past my current issue.)

// Extract the students who failed from the "students" vector.
void extract_fails(vector<Student_info>& students)
{
    typedef vector<Student_info>::size_type str_sz;
    typedef vector<Student_info>::iterator iter;
    iter it = students.begin();
    str_sz i = 0, count = 0;

    while (it != students.end()) {
        // fgrade tests wether or not the student failed
        if (!fgrade(*it)) {         
            // if student passed, copy to front of vector
            students.insert(students.begin(), it, it);      
            // tracks of the number of passing students(so we can properly resize the array)
            count++;                                        
        }

        cout << it->name << endl;   // output to verify that each student is iterated to
        it++;
    }
}

The code compiles and runs, but the students vector isn't adding any student structures to its front. My program's output displays that the students vector is unchanged.

Here's my complete source code, followed by a sample input file (I redirect input from the console by typing " < grades" after the compiled program name at the command prompt.)

#include <iostream>
#include <string>
#include <algorithm>    // to get the declaration of `sort'
#include <stdexcept>    // to get the declaration of `domain_error'
#include <vector>       // to get the declaration of `vector'

//driver program for grade partitioning examples

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::domain_error;
using std::sort;
using std::vector;
using std::max;
using std::istream;

struct Student_info {
    std::string name;
    double midterm, final;
    std::vector<double> homework;
};


bool compare(const Student_info&, const Student_info&);
std::istream& read(std::istream&, Student_info&);
std::istream& read_hw(std::istream&, std::vector<double>&);
double median(std::vector<double>);

double grade(double, double, double);
double grade(double, double, const std::vector<double>&);
double grade(const Student_info&);

bool fgrade(const Student_info&);

void extract_fails(vector<Student_info>& v);

int main()
{
        vector<Student_info> vs;
        Student_info s;
        string::size_type maxlen = 0;
        while (read(cin, s)) {
                maxlen = max(maxlen, s.name.size());
                vs.push_back(s);
        }

        sort(vs.begin(), vs.end(), compare);

    extract_fails(vs);


    // display the new, modified vector - it should be larger than
    // the input vector, due to some student structures being
    // added to the front of the vector.
    cout << "count: " << vs.size() << endl << endl;
    vector<Student_info>::iterator it = vs.begin();
    while (it != vs.end())
        cout << it++->name << endl;
    return 0;
}


// Extract the students who failed from the "students" vector.
void extract_fails(vector<Student_info>& students)
{
    typedef vector<Student_info>::size_type str_sz;
    typedef vector<Student_info>::iterator iter;
    iter it = students.begin();
    str_sz i = 0, count = 0;

    while (it != students.end()) {
        // fgrade tests wether or not the student failed
        if (!fgrade(*it)) {         
            // if student passed, copy to front of vector
            students.insert(students.begin(), it, it);      
            // tracks of the number of passing students(so we can properly resize the array)
            count++;                                        
        }

        cout << it->name << endl;   // output to verify that each student is iterated to
        it++;
    }
}


bool compare(const Student_info& x, const Student_info& y)
{
    return x.name < y.name;
}


istream& read(istream& is, Student_info& s)
{
    // read and store the student's name and midterm and final exam grades
    is >> s.name >> s.midterm >> s.final;

    read_hw(is, s.homework);  // read and store all the student's homework grades
    return is;
}


// read homework grades from an input stream into a `vector<double>'
istream& read_hw(istream开发者_如何学JAVA& in, vector<double>& hw)
{
    if (in) {
        // get rid of previous contents
        hw.clear();

        // read homework grades
        double x;
        while (in >> x)
            hw.push_back(x);

        // clear the stream so that input will work for the next student
        in.clear();
    }
    return in;
}


// compute the median of a `vector<double>'
// note that calling this function copies the entire argument `vector'
double median(vector<double> vec)
{
    typedef vector<double>::size_type vec_sz;

    vec_sz size = vec.size();
    if (size == 0)
        throw domain_error("median of an empty vector");

    sort(vec.begin(), vec.end());

    vec_sz mid = size/2;

    return size % 2 == 0 ? (vec[mid] + vec[mid-1]) / 2 : vec[mid];
}


// compute a student's overall grade from midterm and final exam grades and homework grade
double grade(double midterm, double final, double homework)
{
    return 0.2 * midterm + 0.4 * final + 0.4 * homework;
}


// compute a student's overall grade from midterm and final exam grades
// and vector of homework grades.
// this function does not copy its argument, because `median' does so for us.
double grade(double midterm, double final, const vector<double>& hw)
{
    if (hw.size() == 0)
        throw domain_error("student has done no homework");
    return grade(midterm, final, median(hw));
}


double grade(const Student_info& s)
{
    return grade(s.midterm, s.final, s.homework);
}


// predicate to determine whether a student failed
bool fgrade(const Student_info& s)
{
    return grade(s) < 60;
}

Sample input file:

Moo 100 100 100 100 100 100 100 100

Fail1 45 55 65 80 90 70 65 60

Moore 75 85 77 59 0 85 75 89

Norman 57 78 73 66 78 70 88 89

Olson 89 86 70 90 55 73 80 84

Peerson 47 70 82 73 50 87 73 71

Baker 67 72 73 40 0 78 55 70

Davis 77 70 82 65 70 77 83 81

Edwards 77 72 73 80 90 93 75 90

Fail2 55 55 65 50 55 60 65 60

Thanks to anyone who takes the time to look at this!

---

Inserting at the beginning of a vector invalidates all the iterators pointing into that vector. If I'm not mistaken you are supposed to use <algorithm> - the std::remove/std::erase pair.

---

It's worth noting for other people trying this problem that there was another issue here:

insert(students.begin(), it, it)

isn't putting anything into the beginning of the vector because the range denoted by the last two argument iterators make a half-open range, which means a range that starts at the first iterator and goes up to but does not include the element denoted by the last iterator.

In other words, the range denoted by [it, it) is an empty range. To get a range of just 'it', you'd need [it, it+1).

Of course, this would still have the problem of invalidating all of the iterators ahead of it.

---

I'm surprised that worked for you Darel. I tried using

students.insert(students.begin(), students[i++]);

and I got a bad_alloc thrown at me. I had to use this format:

students.insert(students.begin(), 1, students[i+count]);

to make it work. The added 1 is the number of elements to insert, initialized to the value of students[i+count]

The reason I used i+count for the index of students is because as you add more students to the beginning, you have to add the count to the index to compensate for this. Same goes for the index of the failing students.

I'm writing this now more for anyone who is having trouble with this problem, I'm sure Darel are already done with the book by now!