[libc++] Algorithms like `copy` and `copy_n` can use batch insertion for insert iterators into containers

[kelbon]

As far as I can see, its not currently handled if output iterator is a back_inserter. But it is potentially much better to do

out._container.insert(_container.end(), b, e) // uninitialized_copy_n or smth inside

instead of many .push_backs

In msvc stl its also not handled, but vector of bool is special case

[frederick-vs-ja]

I edited the issue title to make the intent clearer. Please double check it and edit it again if something was misunderstood.

Unfortunately, we can't directly use uninitialized_copy_n in general cases due to required construction via allocators. But we can use some allocator-aware variants instead.

[kelbon]

I edited the issue title to make the intent clearer. Please double check it and edit it again if something was misunderstood.

Unfortunately, we can't directly use uninitialized_copy_n in general cases due to required construction via allocators. But we can use some allocator-aware variants instead.

I mean vector.insert(end, b, e) will use uninitialized_copy_n

[kelbon]

I created repository with benchmark and motivation

https://github.com/kelbon/copy_optimization_motivation

[frederick-vs-ja]

I mean vector.insert(end, b, e) will use uninitialized_copy_n

We can't do this unless there's no customized alloc.construct(p, args).

It seems that we can reuse the logic of insert_range, append_range, and prepend_range, except that we need to avoid exposing these names before C++23.

[kelbon]

I mean vector.insert(end, b, e) will use uninitialized_copy_n

We can't do this unless there's no customized alloc.construct(p, args).

It seems that we can reuse the logic of insert_range, append_range, and prepend_range, except that we need to avoid exposing these names before C++23.

vector uses uninitialized_copy_n INSIDE of its implementation

[kelbon]

I mean vector.insert(end, b, e) will use uninitialized_copy_n

We can't do this unless there's no customized alloc.construct(p, args).

It seems that we can reuse the logic of insert_range, append_range, and prepend_range, except that we need to avoid exposing these names before C++23.

insert(end, b, e) makes same as append range, with only difference - it and sentinel same type

[philnik777]

I mean vector.insert(end, b, e) will use uninitialized_copy_n

We can't do this unless there's no customized alloc.construct(p, args).
It seems that we can reuse the logic of insert_range, append_range, and prepend_range, except that we need to avoid exposing these names before C++23.

vector uses uninitialized_copy_n INSIDE of its implementation

No, it doesn't.

[kelbon]

@philnik777 i dont understand why its matter what vector do inside .insert, main point that it will be more effective than many push backs

one of std lib implementations:

[philnik777]

@philnik777 i dont understand why its matter what vector do inside .insert, main point that it will be more effective than many push backs

You keep saying insert uses uninitialized_copy_n internally, which it doesn't. I agree it doesn't really matter.