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

    <tr>
        <th>Summary</th>
        <td>
            [libc++] Optimizations for algorithms on flat containers
        </td>
    </tr>

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

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

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

<pre>
    We could do something like this:

```c++
template <class Iterator, class Pred>
  requires same_as<Pred, _Compare> &&
 (__desugars_to_v<__less_tag, _Pred, _Reference, _Reference> ||
 __desugars_to_v<__greater_tag, _Pred, _Reference, _Reference> || ...)
bool is_sorted(__ra_iterator<flat_set<_ValueType, _Compare, _Container>, typename _Container::iterator> first,
 __ra_iterator<flat_set<_ValueType, _Compare, _Container>, typename _Container::iterator> last,
               Pred pred) {
  return true;
}
```

Other things we probably want to do if we go down that route:
- We might want a typedef for `__flat_set_iterator<...>` which expands to `__ra_iterator`?
- We might want to have some sort of trait instead of matching `flat_set` directly, maybe something like `__is_sorted_with_respect_to<Iterator, Predicate>` that we can then specialize for any container that is sorted as an invariant?
- In `std::flat_set::insert(Iter, Iter)` & friends, we could add `std::sorted_unique_t` when we see that `Iter` is a fellow `flat_set` iterator (or any kind of sorted iterator, really).
</pre>
<img width="1" height="1" alt="" src="http://email.email.llvm.org/o/eJy8VcGOozgQ_RrnUuqImISEA4c03ZHmNKvVaueICijAO8Zm7CKZzNevbJLudGtOe9iWJWg79areq-cCvVe9ISrE7llIOczqp6I8EVKK3csKZx6sK3SrrDG0qm17Lb4RNHbWLbQWvB2JB2V60Oo7AQ_Ki_QokriyZFmNkM9hJUemcdLIBCItG43ewxcmh2ydkCUsO384akX6KpIjgKMfs3LkweNIFXqRlvFYllCVdpzQkUhfQcgsrOQIQh6qqiU_9-h8xbY6i7SsKk3eV4x9DHxD-JM6cmQa-vRfQNyXYSVH-B1c7wiZ3H9AhPV6LWQukmNtrQblK28dh-hDVTms1F2OtOw0cuWJQ8a_Uc_013WiD8yXd8OoDLkgmSyBrxMZHOnDyVGkx3fkV-iU8yzkjd__llbjW9aPf0E_mKKIOYj98633PDsD7GYSadgS-5dHVy0m-8oDOYgW9HAhmJytsdZXuKBhYBtMqrpw0of3iwEekMHZmWlx6hN8IxhVP_ASg5FMSx101oHIkqq6a_KoU2hk-iqyBC6DagagnxOa1oeUMeZR1SwR6ek3qdjCgGeKtwiCEcB2wA4VgzKeCduwMSI38YqJLHnrTpZAqxw1rK9B_xGvNX2-jbGON4tVF8VD5chP1HDFVqTl4-ULPVANBlUiqyjThaDBIBkZCHEKtfpFURg0V2juvV5-rTwsqQA9oAFlzugUGr6z_2JCTZ7bxRvvVotOMZ4cC3kIVYWKlmceihEyg84pMq0PJ5f7BMK2_YB4Yzob9WOmipfukAkBnmipUmRJRM6SUDBCR1rby2dx770LE-XG9rsysR83jupBPEeoQyPy9aot0jZPc1xRsdlv5e6QbbJsNRR5t6FDl2K9qZs23W6yei8JN213yPIGUa5UIRO5S1K52eRbKeUaD81uS-lu2-3l4bDfim1CIyq91vo8rq3rV8r7mYpNKre7fKWxJu1vY1yr-j51pQx3TsqJXGfdiHE6xeHuioD0VM-9F9tEK8_-HZsV6_hReIDavcDXidWofiEra_xiBN1bp3gYPVgDQcN3X_jV7HQxME_xsyBPQp56xcNcrxs7CnkK6W6Pp8nZf6hhIU-RlxfydKN2LuS_AQAA___6jymv">