This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of Tentatively NAD status.

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.