1

I am working on a homework assignment involving vectors using qsort(). I am able to get the code to compile, but I am receiving an error saying Expression: vector subscript is out of range and Expression: Standard C++ Libraries out of range &&0 Can anyone help as to where and why my vector subscript is out of range?

#include    <iostream>
#include    <fstream>
#include    <iomanip>
#include    <string>
#include    <vector>

using namespace std;

#include    "functions.h"

typedef vector< int >::size_type size_t;


int main( )
{
    ifstream ifs = get_ifs( );

    sort( ifs );

    return 0;
}


void sort( ifstream &ifs )
{
    vector< int > vi;
    int value;

    while( ifs >> value )
    {
        vi.push_back( value );
    }

    cout << "unsorted vi:\n" << vi << '\n';

    qsort( vi );

    cout << "\nsorted vi:\n" << vi << '\n';
}


void qsort( vector< int > &vi )
{
    int bot = 0;
    int top = vi.size() - 1;

    qsort(vi, bot, top);
}

void qsort( vector< int > &vi, size_t low, size_t high )
{


    if (low < high)
    {
        int split = partition(vi, low, high);
        qsort(vi, low, split-1);
        qsort(vi, split+1,high);
    }
    else
    {
        return ;
    }

}

size_t partition( vector<int>& vi, size_t low, size_t high )
{
    int pivot = vi[high];
    int bottom = low - 1;
    int top = high;

    bool notdone = true;
    while(notdone)
    {
        while(notdone)
        {
            bottom += 1;
            if (bottom == top)
            {
                notdone = false;
                break;
            }
            if (vi[bottom] > pivot)
            {
                vi[top] = vi[bottom];
                break;
            }
        }
        while (notdone)
        {
            top = top-1;

            if (top == bottom)
            {
                notdone = false;
                break;
            }
            if (vi[top] < pivot)
            {
                vi[bottom] = vi[top];
                break;
            }
        }
    }
    vi[top] = pivot;
    return top;
}





void print_vec( const vector< int > &vi, size_t n, size_t t )
{
    cout << vi;

    for( size_t i = 0; i < t; ++i )
    {
        cout << setw( 3 ) << vi[ i ] << ' ';
    }

}


ostream &operator <<( ostream &out, const vector< int > &vi )
{
    vector< int >::const_iterator iter;

    for( iter = vi.begin( ); iter != vi.end( ); ++iter )
    {
        out << setw( 3 ) << *iter << ' ';
    }

    return out;
}


ifstream get_ifs( )                             // get input file stream
{
    string filename;                            // input file name

    cerr << "name of file to read from? ";
    cin  >> filename;

    ifstream ifs( filename, ifstream::in );
    if( ! ifs )                                 // cannot open file infilen
    {
        cerr << "cannot open input file '" << filename << "'\n";
        exit( 1 );
    }

    return ifs;                                 // return input file stream
}
4

2 回答 2

3

当您对元素进行分区直到每个分区中只剩下 1 个元素时，如果我理解正确，您将返回 0 作为顶部。

当您点击代码qsort(vi, low, split-1);拆分时将包含 0。

您需要处理特殊情况是您的分区有 1 个元素

于 2013-03-14T00:17:39.480 回答
0

不要在 C++ 中使用 qsort。如果可能，请使用 std::sort()。

问题是您传递给 qsort 的基础不是 vi 而是 &vi[0] 因为容器可能有其他数据来管理向量。

另请参阅 Using qsort() with class pointers以获得更多答案和解释。

于 2013-03-14T00:16:44.493 回答