c++ - using vectors with qsort()

Question

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
}

score 3 · Accepted Answer

各パーティションに要素が1つしか残らないように要素を分割すると、正しく理解できれば、0がトップとして返されます。

コードqsort(vi, low, split-1);分割をヒットすると、0が含まれます。

パーティションに 1 つの要素がある特殊なケースを処理する必要があります

score 0 · Accepted Answer

C++ で qsort を使用しないでください。可能であれば、std::sort() を使用してください。

問題は、qsort に渡すベースが vi ではなく &vi[0] であることです。これは、コンテナーがベクターを管理するための他のデータを持っている可能性があるためです。

より多くの回答と説明については、 Using qsort() with class pointersも参照してください。

c++ - using vectors with qsort()

2 に答える 2

Related

Reference