比较迭代器会在自定义冒泡排序实现中没有错误地使程序崩溃
Comparing iterators crashes program without errors in custom bubble sort implementation
我对 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;
}
在那一行你取消引用 i + 1
,在循环的最后一次迭代中它将取消引用 .end()
调用未定义的行为,.end()
是最后一个元素之后的一个,它不能取消引用。
快速修复是让你的停止条件 i != end - 1
。
虽然这不会修复冒泡排序的实现,它对于更复杂的序列仍然存在缺陷,但请使用此样本向量:
std::vector<int> vector = {1, 2, 7, 3, 6, 4, 5};
As you can see here,不会正确排序
可能的更正是:
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;
}
正如 中所说,性能取决于几个因素,其中包括 CPU 体系结构、SO 或编译器,您必须测试这些解决方案,看看哪个给您最佳表现。
您还可以使用编译器优化选项来根据需要调整编译。
您正在取消引用您无法取消引用的结束迭代器。
在你的循环中,你遍历每个迭代器直到结束。问题是,你每次都加上迭代器。当迭代器等于 end - 1
并且您将其添加到它时,您将收到 end
然后您取消引用。这是未定义的行为,因此是随机数。
您可以尝试将循环条件更改为 != end - 1
,这意味着 i + 1
永远不会是 end
。
我对 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;
}
在那一行你取消引用 i + 1
,在循环的最后一次迭代中它将取消引用 .end()
调用未定义的行为,.end()
是最后一个元素之后的一个,它不能取消引用。
快速修复是让你的停止条件 i != end - 1
。
虽然这不会修复冒泡排序的实现,它对于更复杂的序列仍然存在缺陷,但请使用此样本向量:
std::vector<int> vector = {1, 2, 7, 3, 6, 4, 5};
As you can see here,不会正确排序
可能的更正是:
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;
}
正如
您还可以使用编译器优化选项来根据需要调整编译。
您正在取消引用您无法取消引用的结束迭代器。
在你的循环中,你遍历每个迭代器直到结束。问题是,你每次都加上迭代器。当迭代器等于 end - 1
并且您将其添加到它时,您将收到 end
然后您取消引用。这是未定义的行为,因此是随机数。
您可以尝试将循环条件更改为 != end - 1
,这意味着 i + 1
永远不会是 end
。