比较迭代器，在自定义气泡排序实现中程序崩溃而不出错。

Question

我对C++比较陌生。我一直在尝试使用迭代器对一个向量进行排序。我使用的是气泡排序。我不想知道我的气泡排序的实现是否有效，我只想知道是什么让我的程序崩溃。

template<typename iter>
void bubbleSort(iter start, iter end) {
    for (iter &j = end; j != start; j--) {
        for (iter &i = start; i != end; i++) {
            // std::cout << *i << std::endl;
            if (*i > *(i + 1)) { // this line is where it stops
                std::iter_swap(i, i + 1);
            }
        }
    }

    std::cout << "ended"; // this line never gets called
}

不过当程序停止时，它没有显示任何异常。我也尝试捕捉了它停止的部分，但它没有进入尝试捕捉。另外，每当我取消对第一行打印的注释时。

std::cout << *i << std::endl;

它就会打印出 1168169449 永远。这里到底出了什么问题？

我是这样测试的。

std::vector<int> vector = {1, 2, 3, 6, 4, 5};
std::vector<int> temp = vector;
//std::sort(temp.begin(), temp.end());
bubbleSort(vector.begin(), vector.end());
for(auto& num : vector) {
    std::cout << num << std::endl;
}

Answer 1

在这一行中，你是在引用 i + 1，在循环的最后一次迭代中，它将取消引用 .end() 它调用了未定义的行为。.end() 是在最后一个元素之后的一个元素，它不能被取消引用。

快速解决方法是将停止条件改为 i != end - 1.

但这并不能解决气泡排序的问题，对于更复杂的序列来说，气泡排序的实现还是有缺陷的，比如这个样本向量。

std::vector<int> vector = {1, 2, 7, 3, 6, 4, 5};

如你所见，它将不会被正确排序。

一个可能的纠正方法是

演示

template<typename iter>
void bubbleSort(iter start, iter end) {
    for (iter i = start + 1; i != end; i++) {
        for (iter j = start; j != end - 1; j++) {
            if (*i < *j) {
                std::iter_swap(i, j);
            }
        }
    }
    std::cout << "ended" << std::endl;
}

这个版本，虽然它的工作原理是一样的，但可以进行优化，你可以取消其中一个副本，代价是代码的可读性稍差，并优化迭代次数。

template<typename iter>
void bubbleSort(iter start, iter end) {
    while(start != end) {
        for (iter j = start; j != end; j++) {
            if (*start > *j) {
                std::iter_swap(start, j);
            }
        }
        start++;
    }
    std::cout << "ended" << std::endl;
}

另一个可以做的事情是添加一个条件do，以避免在同一位置的去引用和比较值，消除一些开销，减少间接调用。

//...
if(start == j){ // will compare the iterators and skip the loop if they are equal
    continue;
}
//...

综合考虑，我会使用 这样

template<typename iter>
void bubbleSort(iter start, iter end) {
    for (iter i = start; i != end; i++) {
        for (iter j = i; j != end; j++) {
            if(i == j) {
                continue;
            }
            if (*i > *j) {
                std::iter_swap(i, j);
            }
        }
    }
    std::cout << "ended" << std::endl;
}

如上所述。连线性能取决于几个因素，其中包括CPU架构，SO或编译器，你必须测试这些解决方案，看看哪一个给你最好的性能。

你也可以使用你的编译器优化选项来调整编译以满足你的需求。

Answer 2

你是在dereferenence结束迭代器，你不能dereference。

在你的循环中，你通过每个迭代器直到最后。问题是，你每次都要加上迭代器。当迭代器等于 end - 1 然后你再加上那一个，你就会收到。end 然后你再去引用它。这是未定义的行为，因此是随机数。

你可以尝试将循环条件改为 != end - 1 这意味着 i + 1 不可能 end.