时间戳

首页 > 解决方案 > Visual Studio 错误：在使用向量实现 QuickSort 时“无法在开始之前寻找向量迭代器”

c++ - Visual Studio 错误：在使用向量实现 QuickSort 时“无法在开始之前寻找向量迭代器”

问题描述

我试图使用向量和迭代器来实现快速排序。但是编译器给了我一个错误，比如：“Cannot seek vector iterator before begin”。我不明白为什么，因为代码适用于 Codeblocks。谁能帮我？有一种方法可以输入向量的大小并使用 rand 自动生成它。此外，我添加了一种在快速排序之前和之后打印向量的方法。

#include <iostream>
#include <vector>
#include <ctime>
#include <cstdlib>
using namespace std;

void printVector(vector<int> v) {
    for (auto i = v.begin(); i < v.end(); i++)
        cout << " " << *i;
    cout << endl;
}

void printVectorIterator(vector<int>::iterator begin, vector<int>::iterator end) {
    for (auto i = begin; i < end; i++)
        cout << " " << *i;
    cout << endl;
}

vector<int>::iterator Partition(vector<int>::iterator begin, vector<int>::iterator end) {
    auto partitionIndex = begin;
    auto pivot = end;

    for (auto i = begin; i < end; i++) {
        if (*i <= *pivot) {
            iter_swap(i, partitionIndex);
            partitionIndex++;
        }
    }
    cout << "pivot" << *pivot << endl;
    iter_swap(partitionIndex, pivot);
    return partitionIndex;
}

void QuickSort(vector<int>::iterator begin, vector<int>::iterator end) {
    if (begin < end) {
        auto q = Partition(begin, end);
        QuickSort(begin, q - 1);
        QuickSort(q + 1, end);
    }
}

vector<int> random_vector() {
    int n;
    vector<int> A;
    cout << "Size of the vector: ";
    cin >> n;

    srand((unsigned)time(0));

    for (auto i = 0; i < n; i++) {
        int random_integer = 1 + rand() % 100;
        A.push_back(random_integer);
    }

    return A;
}

int main() {
    vector<int> A = random_vector();

    cout << "\nUnsorted vector: " << endl;
    printVector(A);
    QuickSort(A.begin(), A.end() - 1);
    cout << "\nSorted vector: " << endl;
    printVector(A);

    return 0;
}

标签： c++vector

解决方案

在Quicksort函数中，如果Partition(begin, end)设置q为begin或end然后您可能会遇到问题。所以你需要一张支票。

void QuickSort(vector<int>::iterator begin, vector<int>::iterator end) {
    if (begin < end) {
        auto q = Partition(begin, end);
        if (q != begin) QuickSort(begin, q - 1);
        if (q != end) QuickSort(q + 1, end);
    }
}

推荐阅读