使用帶有qsort（）的向量

Question

我正在使用qsort（）來處理涉及向量的作業分配。我能夠獲得代碼編譯，但我收到一個錯誤，說Expression: vector subscript is out of range和Expression: Standard C++ Libraries out of range &&0任何人都可以幫助我在哪裏以及爲什麼我的矢量下標超出範圍？

#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 
} 

Answer 1

不要在C++中使用qsort。如果可能的話使用std :: sort（）。

問題是您傳遞給qsort的基礎不是vi，而是& vi [0]，因爲容器可能有其他數據來管理向量。

另請參閱Using qsort() with class pointers瞭解更多答案和解釋。

Answer 2

當你已經對你的元素進行了分區，直到你在每個分區只剩下1個元素，如果我理解正確，你將返回0作爲頂部。

當你打的代碼qsort(vi, low, split-1);拆分將包含0

你需要治療的特殊情況是你的分區有1個元素