libstdc++: Optimize std::vector construction from input iterators [PR108487]

libstdc++: Optimize std::vector construction from input iterators [PR108487]

LWG 3291 make std::ranges::iota_view's iterator have input_iterator_tag
as its iterator_category, even though it satisfies the C++20
std::forward_iterator concept. This means that the traditional
std::vector::vector(InputIterator, InputIterator) constructor treats
iota_view iterators as input iterators, because it only understands the
C++17 iterator requirements, not the C++20 iterator concepts. This
results in a loop that calls emplace_back for each individual element of
the iota_view, requiring the vector to reallocate repeatedly as the
values are inserted. This makes it unnecessarily slow to construct a
vector from an iota_view.

This change adds a new _M_range_initialize_n function for initializing a
vector from a range (which doesn't have to be common) and a size. This
new function can be used by vector(InputIterator, InputIterator) when
std::ranges::distance can be used to get the size. It can also be used
by the _M_range_initialize overload that gets the size for a
Cpp17ForwardIterator pair using std::distance, and by the
vector(initializer_list) constructor.

With this new function constructing a std::vector from iota_view does
a single allocation of the correct size and so doesn't need to
reallocate in a loop.

libstdc++-v3/ChangeLog:

	PR libstdc++/108487
	* include/bits/stl_vector.h (vector(initializer_list)): Call
	_M_range_initialize_n instead of _M_range_initialize.
	(vector(InputIterator, InputIterator)): Use _M_range_initialize_n
	for C++20 sized sentinels and forward iterators.
	(vector::_M_range_initialize(FwIt, FwIt, forward_iterator_tag)):
	Use _M_range_initialize_n.
	(vector::_M_range_initialize_n): New function.
	* testsuite/23_containers/vector/cons/108487.cc: New test.

gcc/testsuite/ChangeLog:

	* g++.dg/tree-ssa/initlist-opt1.C: Match _M_range_initialize_n
	instead of _M_range_initialize.
	* g++.dg/tree-ssa/initlist-opt2.C: Likewise.

Reviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>
(cherry picked from commit e200f53a5556516ec831e6b7a34aaa0f10a4ab0a)