Hi,

On 11 November 2022 23:51:03 GMT, Jason McKesson via Std-Proposals <std-proposals_at_[hidden]> wrote:
>On Fri, Nov 11, 2022 at 5:12 PM Lénárd Szolnoki via Std-Proposals
><std-proposals_at_[hidden]> wrote:
>>
>> Hi,
>>
>> I suppose this applies to unsized ranges. But range does not have to be random access to have std::ranges::size, which is O(1) and meant to be cheap.
>>
>> For sized ranges it absolutely makes sense to do the preallocation, and it doesn't require traversing the range twice.
>>
>> I would say that for unsized ranges it makes more sense to not do this, and do the usual multiple reallocations.
>
>I disagree. For most ranges that don't have a size, traversal is
>inexpensive next to the cost of memory allocations (and the requisite
>copying/moving of data). Even complex views that need to invoke some
>functor (like `filter_view` and the like) will generally be cheaper
>than doing potentially dozens of memory allocations. Indeed, it's
>pretty rare to find a forward range for whom iteration is so slow that
>multiple memory allocation is preferred.

Fair enough. However note that if the cost of allocations is sublinear on allocation size, then its cost is sub-O(n) for the vector constructor. The reallocation overhead is dominated by the O(n) cost of data copying.

Comparing it to the cost of complex views is less clear cut, IMO. Especially if you have something like transform | filter in the mix.

Anyway, the question is more about control. It's reasonable for the user to be able to choose between the two approaches. I think the most general approach is to have range adaptors, one that downgrades the range to input, and an other that upgrades to sized (by potentially traversing on construction).

The behaviour of container constructors is predictable for these two kind of ranges. However they implement construction from unsized forward is up to the implementation.

Cheers,
Lénárd