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

    <tr>
        <th>Summary</th>
        <td>
            [libc++] Introduce a concept for "product" iterators
        </td>
    </tr>

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

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

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

<pre>
     Here we materialize the iterator's `value_type` and we insert the elements one by one. If we had some kind of "protocol" that allows us to detect that an iterator is in fact a product of other iterators, we could decompose it to get the underlying iterators in the product and pass that directly to the containers. That way, we could call the underlying container's range-based `insert` method instead of inserting elements one-by-one.

This would apply to e.g. a zip view over two vectors, or when inserting into a `flat_map` from another `flat_map`. And given that we have significant optimizations in e.g. `std::vector::insert(first, last)` for contiguous iterators, this could end up making a big difference.

Example idea:
```c++
template <class _InputIterator, class _Sentinel>
  requires __is_product_iterator<_InputIterator>
_LIBCPP_HIDE_FROM_ABI size_type __append_no_check(_InputIterator __first, _Sentinel __last) {
  auto __first1 = std::__get_product_iterator_element<0>(__first);
  auto __first2 = std::__get_product_iterator_element<1>(__first);

  auto __last1 = std::__get_product_iterator_element<0>(__last);
  auto __last2 = std::__get_product_iterator_element<1>(__last);

  size_type __before = __containers_.keys.size();
 __containers_.keys.insert(__containers_.keys.end(), __first1, __last1);
 size_type __after = __containers_.keys.size();
 __containers_.values.insert(__containers_.values.end(), __first2, __last2);

  size_type __num_of_appended = __after - __before; // can we do better than that?

  // We could also have some kind of check like this, but we'd need to do that without making
  // the assumption that __first & __last are random access.
 _LIBCPP_ASSERT_INTERNAL((__last1 - __first1) == (__last2 - __first2), "something went horribly wrong");

  return __num_of_appended;
}
```

This makes me think about segmented iterator. It's not a category by itself, but it provides a (very useful) side channel to provide additional information to various places in the library. We don't have to implement this optimization day one (in fact we probably shouldn't for simplicity), but I think we really should consider doing it as a follow-up.

CC @philnik777 since this is the kind of stuff you generally like

_Originally posted by @ldionne in https://github.com/llvm/llvm-project/pull/98643#discussion_r1759243579_
 
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJycVkuP4zgO_jXKhaggJVfi5JBDPTEBZmcG3Q3s0aAt2tZGlrySnGz61y_oVyXVNRh0A4VKEFLkx49PDEFXlmgv1k9i_bLALtbO743Szlpa5E5d9vAbeYIzQYORvEajvxPEmkBH8hidFzINIDarE5qOsnhpSWxWgFbxI20D-djrk6GGbAzgLEF-4Y8lHErWqlFBcA3BUVsFrgQhZetddIUzQkqINUZAY9w5QBcgOlAUqYijwM5YQAfQFkosIiC03qmuiGzQxZr8rBaEfGa_heuMAkWFa1oXOCS2XdEAuLOKvLloW70_ZOssm0xzmC2GMCBR2lMRzYWtsFbhbERtyYclfGOFM15uXBdozEdf86OeWI-2orscAykmeeCTCW4o1k4xwZGwJ22QsYlrqu_yyx1TLVYvYvU4_P9W6wDnHgG27YCXltUSEL7rFk6azuBO5CGeHZyomChzHs412StP2kYHyMhKgzFrsGVspXcNoB1Iv5Ut4dEqqPSJ7MBZn_4TAVeiLnWBNoJro270d4za2Z7yHpzYrEJUInkUyeMAavg-ciK3pfYhMk6D_LnroTjfM6qrznXhtgIi0zAkgqyCroUGjxwVQq4rULosyZMtbsl7_R82rSHQipABDKLNavgrhHziv_7XSE1rMBKI5LkwXCbZwbZdPMyt8wzj71_JRm3JiOR1eAvg6b-d9hQgy3TIxorL5rZLnj8Ym15mvx-env_6K_vt8PKavX3581_Z49MBgv4-dCdkGbYtWZVZlxU1FUcht7emIMtmLmdkkGUjryDSpwkkdtFN6vcgkheYc5RlFcUfcGdjcYrkecWQ5XZ2thPJp3blT9q9_1u7H6xzPL8MeiqyHzCz4Jchf7Q62b5OX06l89R7yLL3GZMtj3QJS9YUcnsD7RO1uWs-kZFVowUugDG5w_eeshvbN4VVRu74XwXWr5C_hTZKPwMn38HJf2LPdk3myrEHeKr2aAfkdzO7InkCId-EfIMCLU8p5SCnyFqxxmF4ieTt1s_44t_TfEcT3Djertdb33Vg9JH6GcTg845HoZCpAkuk-h3nxgmpY-26OA6nD654eWAIXdPysBwejKSAkJuRFEBPvEoUz-WioBCWUwLGYfH49evrl2_Z4Y9vr1_-ePy9Z3g7dcjdVRHsmDDmbJbLd7kc0yKk5IBjzdP0TDZC7bzXubnA2TtbCflpmjzFztsfc_SumL58mLc_rLUGjxSg6Zm1R8CcqQtUcaORmhfAEg6xX7DW8alQYKTK-QsfJjoGMuWUFB152Z-0osCLTm5P5C_QBSo7w2wErQiKGi2PyOgmZUClNKcEDWhbOt_gkCAHJ_Sad1FrsKD5ojA69-gvSy4e5ayQaRwqJzrQvHA4gGFlXa9HUNifUoxsunzO_X2SI9Mdai7EwRzvwsC2dKHjZUwVx3gYyToTeEIzP-PNyfF5UG44gwCZhdLxLXbXtTeL8fkZxMOqrbWx-pimKQRti6HC-S7jIKcGCLErS7i4Diqy5HuX3A7X5rI_va607WWtC5y8_MIexvOUiatjbAOP2L4ZKh3rLl8WrhHyzZjT9HHXevcfKqKQb21njJBvu-3mIREyUToUXQja2czfp-udfEjW6S4b63Gh9onaJTtc0P4-lRu5lutduqj3q-0OH8qNUlik-bpIH9Yk01yuZbrJV4jpQu_lSj6sdvfJ_TbZJOlyK4uNVGW6w7K8R9yIhxU1qM2S8S2drxY6hI7296vtRj4sDOZkQn-WS2l0Pl0VUvKZ7vd9VHlXBaZDhxje7UQdTX_QXz1bv8DBxn77EBe7swW1Qz0MlzavJT605_No0Xmz_2l2-xiCkG9jGKe9_H8AAAD__1T8Gr0">