[LLVM] Incorrect output for stable_partition when _Pred is stateful and depend on invocation order #135589
Description
stable_partition code in the LLVM doesn't work as expected when the invocation order of _Pred function for the elements is important and _Pred function can return different value depending on the order it is called for the elements.
Ideally, the function _Pred should be called in the sequential order for the given iterator i.e. from begin() to end(). I can confirm that gcc and vc++ are checking the _Pred value in sequential order and giving the desired behavior.
In the example below, Ideally element at position 2 and 4 should have been promoted, but rather than that it promoted element at position 2 and 6. This happens because the _Pred function is not called in the sequential order but in a arbitrary order.
What would be the best next step? I'm inclined toward modifying the current implementation to ensure that elements _Pred function is called in sequential order. If not, then the document should be updated to highlight this limitation and make it widely known.
Happy to contribute in fixing this issue!
#include<iostream>
#include<vector>
#include<algorithm>
#include <string>
using namespace std;
void promoteOneEvenAndOneOddNumberToFrontExcludingZero(std::vector<int>& v) {
bool odd_number_promoted = false;
bool even_number_promoted = false;
stable_partition(v.begin(), v.end(), [&odd_number_promoted, &even_number_promoted](int number){
std::cout << "Evaluating number : " << number << std::endl;
if (number == 0) {
return false;
}
// number if even number
if (number % 2 == 0) {
// even number already promoted
if (even_number_promoted) return false;
even_number_promoted = true;
return true;
}
// number must be odd
if (odd_number_promoted) return false;
odd_number_promoted = true;
return true;
});
}
int main()
{
std::vector<int> v{0, 0, 1, 1, 2, 3, 4};
promoteOneEvenAndOneOddNumberToFrontExcludingZero(v);
for (int element : v) {
std::cout << element << " ";
}
std::cout << std::endl;
return 0;
}
clang (LLVM) Output:
You can see here that after the first 0 is evaluated, since the _Pred will return false, the function moves to the last element (i.e. value: 4).
Evaluating number : 0
Evaluating number : 4
Evaluating number : 0
Evaluating number : 1
Evaluating number : 1
Evaluating number : 2
Evaluating number : 3
1 4 0 0 1 2 3
GCC Output:
Evaluating number : 0
Evaluating number : 0
Evaluating number : 1
Evaluating number : 1
Evaluating number : 2
Evaluating number : 3
Evaluating number : 4
1 2 0 0 1 3 4