insert() and resize()

[Tinnin]

Hi everyone.
This regards exercise 5-6 of "Accelerated C++".
I am asked to rewrite a function so that instead of using erase() to remove an element (of a failing student), I should copy the elements (of the passing students) to the beginning of the vector and then use resize() to remove the unnecessary elements from the end of the vector.
The program compiles but crashes once it gets to this point. It ran fine using erase().

My code for this function is as follows, where container_Student_info is a typedef for vector<Student_info>:

Ignore std::list. It is there as part of another exercise I'm working on and also failing at ;P.

#include "fail.h"
#include "grade.h"

using std::vector;      using std::list;

container_Student_info extract_fails(container_Student_info& students)
{
    container_Student_info::size_type p = 0;                        // code for copy and resize
    container_Student_info fail;
    container_Student_info::iterator iter = students.begin();
    container_Student_info::iterator it = students.begin();         // code for copy and resize

    while(iter!=students.end())
    {
        if(fgrade(*iter))
        {
            fail.push_back(*iter);

            ++iter;                                     // code for copy and resize
            //iter = students.erase(iter);
        }
        else
        {
            it = students.begin();                      // code for copy and resize
            students.insert(it, *iter);                 // code for copy and resize
            ++p;                                        // code for copy and resize

            ++iter;
        }
    }

    students.resize(p);                                 // code for copy and resize

    return fail;
}


bool fgrade(const Student_info& s)
{
    return grade(s) < 60;
}

So my question is, why is it crashing? Cheers.

[vijayan121]

So my question is, why is it crashing?

container_Student_info::iterator iter = students.begin() ;
while(iter!=students.end())
{
        if(fgrade(*iter))
        {
            // ....
        }
        else
        {
            it = students.begin();  
            students.insert(it, *iter) ; // the iterator 'iter' is no longer valid
            // because we have modified (added a new item into) the container  
            // ..
            ++iter ; // this leads to undefined behaviour
        }
        // ...

[Tinnin]

Thanks vijayan121. I had my suspicions :)

My corrected code:

#include "fail.h"
#include "grade.h"

using std::vector;      using std::list;

container_Student_info extract_fails(container_Student_info& students)
{
    int x = 0;
    int y = 0;
    container_Student_info::size_type p = 0;
    container_Student_info fail;
    container_Student_info::iterator iter = students.begin();
    container_Student_info::iterator it = students.begin();

    while(iter!=students.end())
    {
        if(fgrade(*iter))
        {
            fail.push_back(*iter);

            ++iter;
            ++x;
            //iter = students.erase(iter);
        }
        else
        {
            it = students.begin();
            students.insert(it, *iter);
            ++p;
            ++x;
            ++y;

            iter = students.begin();
            for(int i=0;i!=x+y+2;++i) ++iter;

            //++iter
        }
    }

    students.resize(p);

    return fail;
}


bool fgrade(const Student_info& s)
{
    return grade(s) < 60;
}

[vijayan121]

Couple of points

for(int i=0;i!=x+y+2;++i) ++iter;

If the iterator is a random access iterator (in this case it is, container_Student_info is a std::vector<>), we could just write iter += n ; to advance the iterator by n positions. This would be more efficient.

However, if the iterator is not a random access iterator (which would be the case if container_Student_info was changed to be a std::list<>), we have to increment it n times in a loop.

We can get the best of both worlds with std::advance() which first discovers what kind of iterator is being avanced and then does it in the most appropriate way. http://en.cppreference.com/w/cpp/iterator/advance

I should copy the elements (of the passing students) to the beginning of the vector and then use resize() to remove the unnecessary elements from the end of the vector.

You could do this more elegantly (and also more efficiently) with a classic in-place partitioning algorithm. Start with two iterators, one 'ponting' to the first student and the other 'pointing' to the last student in the vector.

In a loop, while first != last

• keep incrementing the first iterator till you reach a student who has failed (or last).
• keep decrementing the last iterator till you reach a student who has passed (or first)
• swap the two students with a std::iter_swap() http://en.cppreference.com/w/cpp/algorithm/iter_swap

Needless to say, std::partition() is there in <algorithm>
http://en.cppreference.com/w/cpp/algorithm/partition

With it, the code would look like:

container_Student_info extract_fails( container_Student_info& students )
{
    // partition the sequence into two parts with failed students towards the end
    auto iter = std::partition( students.begin(), students.end(),
                [] ( const Student_info& info ) { return !fgrade(info) ; } ) ;

    // copy info for failed students into the result
    container_Student_info  result( iter, students.end() ) ;

    // remove failed students at the end of the sequence
    students.erase( iter, students.end() ) ;

    // and return the sequence of failed students
    return result ;
}

Perhaps you might want to try to write the function with your own code to partition the sequence. A possible implementation is given in the cppreference page.

[Tinnin]

Thanks again. I figured my code would be inefficient. A lot of new stuff for me to look at there :)