c++ - 在自定义冒泡排序实现中比较迭代器崩溃程序而没有错误

Question

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

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
}

但是，当程序停止时，它不会显示任何异常。我还 try catch 了它停止的部分，但它没有进入 try catch 。此外，每当我取消注释第一行打印时:

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 .

这虽然不会修复冒泡排序实现，但对于更复杂的序列仍然存在缺陷，请采用以下样本 vector :

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

As you can see here ，它不会被正确排序。

可能的更正是:

Demo

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;
}
//...

综合考虑，我会使用 something like this :

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

正如 linked thread 中所说，性能取决于几个因素，其中包括 CPU 架构、SO 或编译器，您必须测试这些解决方案，看看哪一个给您最好的性能。

您还可以使用编译器优化选项来根据需要调整编译。