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

    <tr>
        <th>Summary</th>
        <td>
            [libc++] Don't use std::stable_sort in flat_map
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            libc++
      </td>
    </tr>

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

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

<pre>
    In `std::flat_map::insert(first, last)`, we currently use `std::stable_sort`. While discussing this with @huixie90 and reading https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2023/p2767r2.html#stable-sorting, we agreed that

1. The tree-based associative containers specify that `insert(first, last)` inserts in an unspecified order
2. Not using `std::stable_sort` inside `flat_map` is consistent with that
3. MSVC doesn't use `std::stable_sort` in its implementation
4. Using `std::sort` is usually more efficient than `std::stable_sort`

Since the Standard doesn't require us to sort stably and doing so is more expensive, we should switch to just `std::sort`.
</pre>
<img width="1" height="1" alt="" src="http://email.email.llvm.org/o/eJyEU02P2zgM_TXKhRjDpp04PviQdhBgD7uX2Y9jIVtMzIEieUV60vz7hZzMtsV2W8CATFvv8fGRtCJ8DkS92X4wiNPCn5m60iCa7fPGLjrF1HvHMQTaDNHd-l8CmF0p6kx9MPXh5K1-utj5HnEQSmpwf-IkavAjeJvPzuzKHF0JxiUlCupvsAh9QyVqB0-fJCY1u7KAvyb2BI5lXEQ4nEEnFriyTmCa8l0q2OAgkXX5xqQ6S2bDo8Hj9Xot4kzhSdQVMZ0NHl91rAweZUTMF86YIxdHMXic7Uwpv2CJdY6x3bUJi0kv3mB9l_eU5XE4P6qx50TkQCerpjyY8lAV8PtEoInoabBCDqxIHNkqvxGMMajlQElAZhr5dFuh2YYfWQf3nwIcwAZYwh3M5CAmR8mUByzgt6iwrEb9v6uZid3q-7-dy18lSxMWpaB3ix8l1QX8-vLnR3CRJBhs9SdtyxI5K73Mni4U1CrHYMpDU8Af_xX3DhJYZLHe3-ASEwGdTjxy1qKTDT9Idzf9hcNIoBPBi9rgbHJf6U3098KJYBHQCBkHK8dtnRwXsyaJWcI99eeZgvAbPTosU1y8A7myjlNmeF1Ev1dEsXF97bq6sxvqq7ZuWsR902ymfhgrZ9vqVFaua9yua4a63dNYumbvqn07bLjHEpsKsaw6bLEpuqrFHe632wq7bmha05R0sewL798ueZQ3LLJQX2HZ7vcbbwfy8thhz8No8MP6rFuc-ox6GpazmKb0LCpfeJTVr9v_FWz7DM_xS7O_Z31u8_sAbZbk-28378w6LUMxxovBY871OJ7mFF9pVIPHtYC8bY8a3nr8JwAA__9pdHlp">