libstdc++: Improve complexity of flat_map insertion.
The flat_map::_M_insert function now merges in linearithmic time, rather than logarithmic time, for sorted input.
The flat_map::_M_insert function now has optimal complexity N + M log M instead of N log N when inserting already-sorted data. This improvement uses ranges::inplace_merge and views::zip which are now correctly C++20 iterator aware. This change should improve the performance of inserting sorted data into flat_map.
In Details
std::flat_map is a container that stores elements in a sorted vector, offering memory locality and cache-friendliness. The _M_insert function is a helper function used for inserting elements into the flat_map's underlying sorted vectors. The change leverages C++20 ranges to improve the merge complexity when inserting already-sorted data, which matters for bulk loading scenarios. This optimisation doesn't directly interact with other subsystems but improves the performance of the flat_map container.
For Context
A flat map is a data structure similar to a dictionary or map, but it stores its data in a sorted array rather than a tree or hash table. This can lead to better performance in some cases due to improved memory locality. Inserting elements into a flat map requires maintaining the sorted order of the array. This commit improves the efficiency of inserting already-sorted data into the flat map, reducing the time it takes to perform the insertion. This optimization makes flat_map a more appealing choice when the input data is known to be sorted.