Performance issue in handling range iterators in vector constructor

[AlexBAV]

STL loses iterator category when range iterators are passed to vector constructor. Consider the following code:

#include <ranges>
#include <vector>

namespace sr = std::ranges;
namespace rv = sr::views;

template<sr::random_access_range Range>
auto to_vector(Range &&range)
{
    return std::vector<sr::range_value_t<Range>>{sr::begin(range), sr::end(range)};
}

int main()
{
    std::vector a{ 1,2,3,4,5 };

    auto b = to_vector(a | rv::transform([](auto v) { return static_cast<float>(v); }));
}

Currently STL containers lack constructors accepting ranges. The above snippet, while explicitly requiring random access range (according to definition, a random access range "specifies a range whose iterator type satisfies random_access_iterator") eventually invokes vector's _Range_construct_or_tidy(_Iter _First, _Iter _Last, input_iterator_tag) instead of _Range_construct_or_tidy(_Iter _First, _Iter _Last, forward_iterator_tag), losing iterator category(?). This in turn calls emplace_back in a loop, not preallocating vector storage.

On the other hand, calling to_vector and passing a correctly dispatches to forward_iterator_tag version.

STL version

Microsoft Visual Studio Professional 2019 Preview
Version 16.9.0 Preview 5.0

[miscco]

Some observations, I think Casey Carter (@CaseyCarter) will know better

1. You are missing a constraint that the provided range satisfies common_range Otherwise you will pass an iterator / sentinel pair to the vector constructor which expects an iterator pair.

2. The crux seems to be transform_view iterator category:

        template <_Has_member_iterator_category _Traits, class _Base>
        struct _Category_base<_Traits, _Base> {
            // clang-format on
            using iterator_category =
                conditional_t<is_lvalue_reference_v<invoke_result_t<_Fn&, range_reference_t<_Base>>>,
                    conditional_t<derived_from<typename _Traits::iterator_category, contiguous_iterator_tag>,
                        random_access_iterator_tag, typename _Traits::iterator_category>,
                    input_iterator_tag>;
        };

The provided iterators are definitely random_access iterators, but look at the first condition:

is_lvalue_reference_v<invoke_result_t<_Fn&, range_reference_t<_Base>>>

Your lambda function is taking the content by value and returning it by value. I think this is the crux and I am unsure how you would solve it in this specific use case where you cast to a different type

[AlexBAV]

You are missing a constraint that the provided range satisfies common_range Otherwise you will pass an iterator / sentinel pair to the vector constructor which expects an iterator pair.

This is a simplified version for illustration. The actual code snippet it was taken from has a different code path for !common_range case.

I need to think about your second point on is_lvalue_reference_v<invoke_result_t<_Fn&, range_reference_t<_Base>>> . Theoretically, this vector constructor takes a range size and then calls std::copy(begin, end, vector_buffer) and this would perfectly work with transform_view iterators. Maybe the requirement should be weakened.

See also https://godbolt.org/z/c3sY6j: it confirms that iterator taken from transform view range satisfies the random_access_iterator concept.

[CaseyCarter]

Alex Bessonov (@AlexBAV), thanks for the report. This is a well-known issue in WG21, we just didn't have time to gel a good solution for "materializing" views into containers. There's at least one proposal in progress to fix this problem (WG21-P1206 "ranges::to: A function to convert any range to a container"). A competing proposal will possibly emerge soon that uses special tagged container constructors instead - some folks are bothered that the ranges::to design requires a single library component to understand how to best construct any container when really the containers themselves know best.

In any case, I don't think there's anything we can do here in the STL without direction from WG21.

[AdamBucior]

Can't we just use _Iter_concept and _RANGES distance in C++20 mode? This should fix the issue since _Iter_concept fallbacks to iterator_category if iterator_concept is not present.

[sylveon]

_RANGES distance is constrained, which may prevent some existing code from building (even if the code was already shaky)

[AdamBucior]

_RANGES distance is constrained, which may prevent some existing code from building (even if the code was already shaky)

The only constraint that I could find, that input_or_output_iterator and sentinel_for require and __LegacyForwardIterator doesn't is default_initializable (__LegacyForwardIterator only requires constructible_from<> which in this situation is probably impossible to satisfy without also satisfying default_initializable)