[RFC] std::inplace_vector::assign avoid double loops

[Tomasz Kaminski]

On Tue, Sep 22, 2026 at 12:21 PM Jonathan Wakely <jwakely@redhat.com> wrote:

> On Mon, 21 Sept 2026 at 19:10, Tomasz Kaminski <tkaminsk@redhat.com>
> wrote:
> >
> > Double loop allows us to check capacity (and throw) early and avoid
> insertions when
> > range is forward.
>
> And typical uses of std::inplace_vector will not be for huge sequences
> with many thousands of elements, so the cost of computing the distance
> first is bounded and should be reasonable.
>
> I don't think we should try to remove the double loop. What could be
> useful is not using ranges::distance or std::distance for non-sized
> sentinels, because what we could do is stop counting after finding
> that the range will not fit.
>
We could use auto c = ranges::advance(it, n, end) for that and then check
if
c == n && it != end to throw. We will need separate loop for C++17
iterators.


>
> If the remaining capacity is 5 and we try to insert a range of 200
> elements, we only need to count to 5 to determine that we haven't
> reached the sentinel and so it won't fit. Counting the other 195
> elements is wasted work.
>
>
> >
> > On Mon, Sep 21, 2026 at 7:44 PM François Dumont <frs.dumont@gmail.com>
> wrote:
> >>
> >> Hi
> >>
> >> I wonder what you think about this patch.
> >>
> >> Maybe this has already been discuss, sorry if so.
> >>
> >> If fine I'll try to isolate _S_distance in a testable helper.
> >>
> >>      libstdc++: Do not loop several times on range given to
> >> std::inplace_vector::assign
> >>
> >>      std::inplace_vector::assign first compute the distance between the
> >> input iterators
> >>      before running the assignment loop. The distance is computed as
> >> long as the input
> >>      range is a sized-sentinel or forward iterators. It means that when
> >> computing distance
> >>      on a forward_list like in the added test the range will be loop
> >> through twice.
> >>
> >>      As inplace_vector do not need reallocation to increase its capacity
> >> it seems more
> >>      optimal to only get the distance if it can be done in O(1).
> >> Otherwise we just loop
> >>      through the range and add elements using emplace_back.
> >>
> >>      libstdc++-v3/ChangeLog:
> >>
> >>              * include/std/inplace_vector (inplace_vector::_S_distance):
> >> Return a distance
> >>              only if sized_sentinel_for or iterator is derived from
> >> random_access_iterator_tag.
> >>              *
> >> testsuite/23_containers/inplace_vector/modifiers/assign_forward_list.cc:
> >> New test
> >>              case. Only checking that the right thing is done but not
> >> that it is done with only
> >>              one loop on the input range.
> >>
> >> Quickly tested with the added test case for now.
> >>
> >> François
> >>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://gcc.gnu.org/pipermail/libstdc++/attachments/20260922/73aaa3d4/attachment-0001.htm>