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) and
vector(from_range_t, R&&) 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.

Previously the _M_range_initialize overload for Cpp17ForwardIterator was
using a local RAII _Guard_alloc object to own the storage, but that was
redundant. The _Vector_base can own the storage right away, and its
destructor will deallocate it if _M_range_initialize exits via an
exception.

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(from_range_t, R&&)): Use _M_range_initialize_n for sized
	ranges and forward ranges.
	(vector::_M_range_initialize(FwIt, FwIt, forward_iterator_tag)):
	Likewise.
	(vector::_M_range_initialize_n): New function.
	* testsuite/23_containers/vector/cons/108487.cc: New test.

Reviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>

0 files changed, 0 insertions, 0 deletions