Valentin Valentin - 22 days ago 10
C++ Question

Having problems understanding a sorting bug

I wrote a program that generates a couple of random numbers and sorts them with a simple algorithm.
But in the sorting algorithm I have these two variants of swapping the numbers in my loop:

for (iterator i = intv.begin(); i < intv.end(); i++)
{
for (iterator j = i + 1; j < intv.end(); j++)
{
if (max(*i, *j) == *i)
{
/* Problem
uint temp = *i;
intv.erase(i);
intv.insert(i, *j);
intv.erase(j);
intv.insert(j, temp);
*/

uint temp = *j;
intv.erase(j);
intv.insert(j, *i);
intv.erase(i);
intv.insert(i, temp);
}
}
}


Here's an output from the working program:

6;3;5;2;5;9;0;6;6;5;
0;2;3;5;5;5;6;6;6;9;


And here's one from the problematic program:

5;5;1;1;6;9;3;2;5;4;
4;4;4;4;4;4;4;4;4;9;


Can somebody please explain to me what's the difference between the swapping mechanisms?

Answer Source

To swap elements from iterators you should use std::iter_swap:

for (auto i = intv.begin(); i < intv.end(); i++) {
    for (auto j = i + 1; j < intv.end(); j++) {
        if (std::max(*i, *j) == *i)
        {
            std::iter_swap(i, j);
        }
    }
}

As for the part "whyy is the first piece of code not working while the second does?" That's because it's undefined behavior. When you enter undefined behavior, your code can work as expected like in your second example, crash, produce incorrect result, like in your first example. It can also delete everything in your disk, but I highly doubt compilers will output the code to actually do that.

Here's a great quote from Is segmentation fault actual undefined behavior when we refer to a non-static data-member answer's:

An implementation could

  • explode your computer and harm you physically
  • make a black-hole which swallows the entire solar system
  • do nothing serious
  • light some LED on your keyboard
  • make some time-travel and kill all your grandparents before the birth of your > own parents
  • etc....