STL sort strangeness August 2, 2008
Posted by Olexandr Melnyk in : Programming , 5commentsWorking on a simple Sudoku solver, I’ve run across a memory-related issue, which isn’t uncommon when developing C/C++ programs, but in my case it seemed somewhat weird since I haven’t been doing any dynamic memory allocations or using pointers explicitly.
After spending some time searching for the bug, I realized that the problem lied in the array shuffling code, which was similar to the code below:
#include <vector>
#include <algorithm>
...
bool random_cmp(const int a, const int b)
{
return (rand() % 2 == 0);
}
...
vector<int> a;
sort(a.begin(), a.end(), random_cmp);
After running it a couple of times in the loop, we get a “double free or corruption” error with a couple dozen lines long backtrace and memory map (program was compiled with G++ 4.1.3). The reason of this, at the first glance, strange behaviour was the fact that comparison function must be deterministic (if a < b and b < c then a < c must be true as well). In the other case, the sort() behaviour is undefined, which it really was in our case. :)
This just teaches me once more to read the documentation carefully before doing something.
P. S. In the end, I used a simple shuffling algorithm, suggested by Sergij Tyhanskij:
void shuffle(vector<int> nums)
{
int a, b, count = nums.size();
for (int i = 0; i < count; i++)
{
a = rand() % count;
b = rand() % count;
swap(nums[a], nums[b]);
}
}
As for the Sudoku solver, I have added a dedicated page for it and updated this website projects section.
