Reduce inclusion for `<queue>` and `<stack>`

[frederick-vs-ja]

Towards #3599.

Test options

• cl /nologo /Bt /Zs /TP /w repro.cpp /std:c++14 /permissive- repro.cpp
• cl /nologo /Bt /Zs /TP /w repro.cpp /std:c++17 /permissive- repro.cpp
• cl /nologo /Bt /Zs /TP /w repro.cpp /std:c++20 /permissive- repro.cpp
• cl /nologo /Bt /Zs /TP /w repro.cpp /std:c++latest /permissive- repro.cpp

Test programs

#include <stack>
int main() {}

#include <queue>
int main() {}

Results

On my old laptop, the changes reduced the consumed time

• for <queue>, from ~1.08s to ~0.57s in C++23 mode;
• for <queue>, from ~0.62s to ~0.49s in C++20 mode;
• for <queue>, from ~0.43s to ~0.37s in C++17 mode;
• for <queue>, from ~0.37s to ~0.33s in C++14 mode;
• for <stack>, from ~0.77s to ~0.51s in C++23 mode.
• not significantly for <stack> in older modes.

Notes

Escape hatch _LEGACY_CODE_ASSUMES_QUEUE_INCLUDES_ALGORITHM can be used to restore the inclusion of <algorithm>.

MSVC-internal changes are needed due to the new internal headers.

[StephanTLavavej]

After thinking about the changes, I'm not sure whether we should merge this. Extracting the heap algorithms is fine, but I'm uncomfortable with the magnitude of the ranges changes. The diff is easy enough to review, but it ends up splitting apart one of the STL's most complicated headers, and in a complicated way. Ultimately it's "stuff that ranges::to needs" but that ends up being a lot of machinery. Throughput is generally desirable but I'm not convinced that <queue> and <stack> are popular enough to be worth this.

I'm also deeply concerned about splitting up overloads of ranges::to - users are notoriously undisciplined about including what they need, but the unspecified behavior that they get should ideally be all-or-nothing, it's very confusing to get some overloads but not others. However, that would be easily fixable, so it's not my real concern about merging this.

[StephanTLavavej]

I thought about this some more and I think I can resolve my concerns with some simple changes. Stand by...

[StephanTLavavej]

I pushed commits:

• Rename to <__msvc_ranges_to.hpp>.
  • I found <__msvc_transform_view_to.hpp> confusing because it defines a lot more than transform_view and ranges::to. I think it's better to focus on how it provides ranges::to, instead of mentioning some-but-not-all C++20 machinery in the filename.
• Add a comment explaining what the header provides.
  • But then let's clarify the intent of the header here.
• Move _HAS_CXX23 <xmemory> inclusion to avoid disrupting auto-sorting.
• Transfer all overloads of ranges::to.
• <algorithm>: Fuse _HAS_CXX20 namespace ranges regions.
• Update comment to mention both <xutility> and <__msvc_ranges_to.hpp>.
• <ranges>: Fuse _HAS_CXX23 regions.

[StephanTLavavej]

I'm mirroring this to the MSVC-internal repo - please notify me if any further changes are pushed.

[StephanTLavavej]

Thanks for queuing up this giant stack of throughput improvements! :joy_cat: :tada: :cat: