Title
ranges::to should prioritize the "reserve" branch
Status
nad
Section
[range.utility.conv.to]
Submitter
Hewill Kang

Created on 2023-07-17.00:00:00 last changed 7 months ago

Messages

Date: 2023-10-30.16:39:42

Proposed resolution:

This wording is relative to N4950.

  1. Modify [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.

Date: 2023-10-15.00:00:00

[ 2023-10-30; Reflector poll ]

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

Date: 2023-07-17.00:00:00

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.

History
Date User Action Args
2023-10-30 16:39:42adminsetmessages: + msg13783
2023-10-30 16:39:42adminsetstatus: new -> nad
2023-07-17 15:53:09adminsetmessages: + msg13684
2023-07-17 00:00:00admincreate