<table border="1" cellspacing="0" cellpadding="8">
    <tr>
        <th>Issue</th>
        <td>
            <a href=https://github.com/llvm/llvm-project/issues/135589>135589</a>
        </td>
    </tr>

    <tr>
        <th>Summary</th>
        <td>
            [LLVM] Incorrect output for stable_partition when _Pred is stateful and depend on invocation order
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            new issue
      </td>
    </tr>

    <tr>
      <th>Assignees</th>
      <td>
      </td>
    </tr>

    <tr>
      <th>Reporter</th>
      <td>
          deep9539
      </td>
    </tr>
</table>

<pre>
    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](https://github.com/llvm/llvm-project/blob/ebba554a3211b0b98d3ae33ba70f9d6ceaab6ad4/libcxx/include/__algorithm/stable_partition.h#L265-L269) 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 
```

</pre>
<img width="1" height="1" alt="" src="http://email.email.llvm.org/o/eJy8V02P27wR_jX0ZfAaMiX54-CD1xu3C6RNDy9atJcFJY4sNhSpkpS8---LoSTb8dobNAVewXHWGnLmmWc-OBTeq6NB3LL8ieXPM9GF2rqtRGw3ebqZFVa-b30QhcbXVriggrIGSisRlIFQI3z9-ve_gLToDeOrACfrvoPwgG8tlgElnGocFirT21LE_dZJdGArYMvk9W8OJVsmUHWmjNLKurgBNTZoggflQTWtdUGYAMLI-9tKYcBh6JwBqaoKHZoAvdAdgsQWjVTmCHbAMgBQgVSXQmuUH6zOgSU7luxeJAqt3xnfR_HZ3DUGX9tOSyhwUjZy4_E_HZqghB4tTkaOqkcDKqATwTpQc5xD5WxDWgs8KsP4mvEN6Q6WXqKR51dzeInOltZUyjUQahHgWJaRmr5k_InxJxAOoayx_E5uk81rwAMtynxESDqOqp82SfTKIblWi15ZNx9JGfzDN9G0GqFAbU_E0EjWRCKIAK31Q9LwqDubyKpFTxvRQOtsYwNKUlB0AZwINRJPwgy-qXBe84nm5Rx-r5WHWrQtGg8FlqLzGIFGxy-xUx5Y_mRsGOPF8mfG13UIrWfpjvED44ejCnVXzEvbMH7Qup_--6119t9YBsYPhbYF4wcsCpHnmUj5YlEkxWYtU4FpWohVUm3kskQhiqWQGSlQRfn2xvhBmVJ3Ehk_vL4KfbROhZos3JbavGY8_cqX-W9f-XLD-OZhahFzyoAA4QoVnHDvg2CM2D-IyNOUpqShQB_A4FsAH7Bl6QFeGF81QNCUQQnBnoST0FipqvcpIcrOxcJSFHiKxFDRwQIa3zkcInYu3Y_EXyrk1oU5vFRgbBhLbfBT2rKLAb_UWNdKESI-qNWx1upYBwgUeq0aNQKijGjEd6TkOSmJ-h2-G3syIx1_Fm37ThpKa4JTRRdiOVTqbXCUWo73HTK-GDawZTJ-kh3j6RS_dK-sDw5Fw9Ivt6Iey2DdHcEl4jcyYOneB6fMcZQku84TIiMa9K0oEXyQLH0aZL1VciqNbwa_9Gh2Rn4z-E3Kv3ZNge53e3DWhC9vpF6Z47_QWcbXUcmOpbsJ4l6ZQCb5EnrKMrYiE1BYq8FK-WqittdzGbL0GSqhPQ5YAGBYiz2any6-TXLG1_38uu3xPfTzS8vjeypXxpd3kEQhX96zO1S1MgEGAalaTWjpObNQ2i4Q9SwlZfwLtUcRIu9xJ7B0R4Jpzflt_HVWg0bqCx_0qAoYX5-XPxMTyRW_V894dN2QSg9bPV__it1pgqCqSPnk4SPLPAf-E_uj3ittILRDId8vDfrHHYOJu8zzzWcO0fMwUYLr7iwflX0UfkZO0_lADcNKSYf5CPhuEm0-gfso_z-CuYuSEPLNWLMRLUt2lJWNOCc8ScbSuF-Y0LPVU0LJHr8W5y9OXyl9ZaR8sPorLaE_gyTQNKiMxTOduFQD_cfcuVtElz1TTdG_HzkZ_rq7_UFFjfQmN1z-0Jqpm9Kn1MIcyQWaTwn1ty60XYjHe_wku3_aLs5RHhFqnI4uUQUchrRKOR8goUMLh44wtBuvTHk9VpyU1j-mz-2s2NgePZ029FYLf0UqX8fhLw5kxHDG-GZ-49T9fvRYkv3CnsUvSPhDScqS3QIySCCBBXBI4VGc_rTf3wnN_-P9H-njY_7J68H7FLJb72dym8pNuhEz3C5WWbZMVsssmdXbstqsJSbFMsvz1TpFueEpz2VeFkVSpkk2U1ue8DzJFlmSL7IkmfN8va5WIsGVXGVVWrIswUYoPadZdW7dcRbnmO0izfP1ZqZFgdrH2x7nBk_TlMPp8ue2ccAtuqNnWaKVD_6iJqig4zUxFlT-DC-mtM5hGcDG-MWe8eGqGK9_Q50oT-KAVafjeDbcyuhKdns1nHVOb__ncTy64hk_jL72W_7fAAAA___QgLJE">