3958. ranges::to should prioritize the "reserve" branch

Section: 25.5.7.2 [range.utility.conv.to] Status: Tentatively NAD Submitter: Hewill Kang Opened: 2023-07-17 Last modified: 2024-01-29

Priority: Not Prioritized

View other active issues in [range.utility.conv.to].

View all other issues in [range.utility.conv.to].

View all issues with Tentatively NAD status.

Discussion:

When the constructed range object has no range version constructor, ranges::to falls into a branch designed specifically for C++17-compliant containers, which calls the legacy constructor that accepts an iterator pair with C(ranges::begin(r), ranges::end(r), std::forward<Args>(args)...).

However, this kind of initialization may bring some performance issues, because we split the original range into pairs of iterators, which may lose information contained in the original range, for example: 

#include <boost/container/vector.hpp>
#include <sstream>
#include <ranges>

int main() {
  std::istringstream ints("1 2 3 4 5");
  std::ranges::subrange s(std::istream_iterator<int>(ints),
                          std::istream_iterator<int>(),
                          5);
  auto r = std::ranges::to<boost::container::vector>(s); // discard size info
}

Above, subrange saves the size information of the stream, but ranges::to only extracts its iterator pair to create the object, so that the original size information is discarded, resulting in unnecessary allocations.

I believe we should prefer to use the "reserve" branch here because it is really designed for this situation.

[2023-10-30; Reflector poll]

Set status to Tentatively NAD after reflector poll. "This optimizes exotic cases at the expense of realistic cases."

Proposed resolution:

This wording is relative to N4950.

  1. Modify 25.5.7.2 [range.utility.conv.to] as indicated:

    template<class C, input_range R, class... Args> requires (!view<C>)
  constexpr C to(R&& r, Args&&... args);

    -1- Mandates: C is a cv-unqualified class type.

    -2- Returns: An object of type C constructed from the elements of r in the following manner:

    1. (2.1) — If C does not satisfy input_range or convertible_to<range_reference_t<R>, range_value_t<C>> is true:

      1. (2.1.1) — If constructible_from<C, R, Args...> is true:

        C(std::forward<R>(r), std::forward<Args>(args)...)

      2. (2.1.2) — Otherwise, if constructible_from<C, from_range_t, R, Args...> is true:

        C(from_range, std::forward<R>(r), std::forward<Args>(args)...)

      3. (2.1.3) — Otherwise, if

        1. (2.1.3.1) — common_range<R> is true,

        2. (2.1.3.2) — the qualified-id iterator_traits<iterator_t<R>>::iterator_category is valid and denotes a type that models derived_from<input_iterator_tag>, and

        3. (2.1.3.3) — constructible_from<C, iterator_t<R>, sentinel_t<R>, Args...> is true:

          C(ranges::begin(r), ranges::end(r), std::forward<Args>(args)...)

      4. (2.1.4) — Otherwise, if

        1. (2.1.4.1) — constructible_from<C, Args...> is true, and

        2. (2.1.4.2) — container-insertable<C, range_reference_t<R>> is true:

          C c(std::forward<Args>(args)...);
if constexpr (sized_range<R> && reservable-container<C>)
  c.reserve(static_cast<range_size_t<C>>(ranges::size(r)));
ranges::copy(r, container-inserter<range_reference_t<R>>(c));

      5. (?.?.?) — Otherwise, if

        1. (?.?.?.?) — common_range<R> is true,

        2. (?.?.?.?) — the qualified-id iterator_traits<iterator_t<R>>::iterator_category is valid and denotes a type that models derived_from<input_iterator_tag>, and

        3. (?.?.?.?) — constructible_from<C, iterator_t<R>, sentinel_t<R>, Args...> is true:

          C(ranges::begin(r), ranges::end(r), std::forward<Args>(args)...)

    2. (2.2) — Otherwise, if input_range<range_reference_t<R>> is true:

      to<C>(r | views::transform([](auto&& elem) {
  return to<range_value_t<C>>(std::forward<decltype(elem)>(elem));
}), std::forward<Args>(args)...);

    3. (2.3) — Otherwise, the program is ill-formed.