[libc++] Optimize input_iterator-pair `insert` for std::vector (#113768)

As a follow-up to #113852, this PR optimizes the performance of the
`insert(const_iterator pos, InputIt first, InputIt last)

[libc++] Optimize input_iterator-pair `insert` for std::vector (#113768)

As a follow-up to #113852, this PR optimizes the performance of the
`insert(const_iterator pos, InputIt first, InputIt last)` function for
`input_iterator`-pair inputs in `std::vector` for cases where
reallocation occurs during insertion. Additionally, this optimization
enhances exception safety by replacing the traditional `try-catch`
mechanism with a modern exception guard for the `insert` function.

The optimization targets cases where insertion trigger reallocation. In
scenarios without reallocation, the implementation remains unchanged.

Previous implementation
-----------------------
The previous implementation of `insert` is inefficient in reallocation
scenarios because it performs the following steps separately:
- `reserve()`: This leads to the first round of relocating old
elements to new memory;
- `rotate()`: This leads to the second round of reorganizing the
existing elements;
- Move-forward: Moves the elements after the insertion position to
their final positions.
- Insert: performs the actual insertion.

This approach results in a lot of redundant operations, requiring the
elements to undergo three rounds of relocations/reorganizations to be
placed in their final positions.

Proposed implementation
-----------------------
The proposed implementation jointly optimize the above 4 steps in the
previous implementation such that each element is placed in its final
position in just one round of relocation. Specifically, this
optimization reduces the total cost from 2 relocations + 1 std::rotate
call to just 1 relocation, without needing to call `std::rotate`,
thereby significantly improving overall performance.

show more ...

Optimize vector::assign for InputIterator-only pair inputs (#113852)

This PR optimizes the input iterator overload of `assign(_InputIterator,
_InputIterator)` in `std::vector<_Tp, _Allocator>` by d

Optimize vector::assign for InputIterator-only pair inputs (#113852)

This PR optimizes the input iterator overload of `assign(_InputIterator,
_InputIterator)` in `std::vector<_Tp, _Allocator>` by directly assigning
to already initialized memory, rather than first destroying existing
elements and then constructing new ones. By eliminating unnecessary
destruction and construction, the proposed algorithm enhances the
performance by up to 2x for trivial element types (e.g.,
`std::vector<int>`), up to 2.6x for non-trivial element types like
`std::vector<std::string>`, and up to 3.4x for more complex non-trivial
types (e.g., `std::vector<std::vector<int>>`).

### Google Benchmarks

Benchmark tests (`libcxx/test/benchmarks/vector_operations.bench.cpp`)
were conducted for the `assign()` implementations before and after this
patch. The tests focused on trivial element types like
`std::vector<int>`, and non-trivial element types such as
`std::vector<std::string>` and `std::vector<std::vector<int>>`.



#### Before
```
-------------------------------------------------------------------------------------------------
Benchmark Time CPU Iterations
-------------------------------------------------------------------------------------------------
BM_AssignInputIterIter/vector_int/1024/1024 1157 ns 1169 ns 608188
BM_AssignInputIterIter<32>/vector_string/1024/1024 14559 ns 14710 ns 47277
BM_AssignInputIterIter<32>/vector_vector_int/1024/1024 26846 ns 27129 ns 25925
```


#### After
```
-------------------------------------------------------------------------------------------------
Benchmark Time CPU Iterations
-------------------------------------------------------------------------------------------------
BM_AssignInputIterIter/vector_int/1024/1024 561 ns 566 ns 1242251
BM_AssignInputIterIter<32>/vector_string/1024/1024 5604 ns 5664 ns 128365
BM_AssignInputIterIter<32>/vector_vector_int/1024/1024 7927 ns 8012 ns 88579
```

show more ...

[libc++][test] Speed up input generating functions for benchmark tests (#115544)

The input generating functions for benchmark tests in the GenerateInput.h
file can be slightly improved by invoking

[libc++][test] Speed up input generating functions for benchmark tests (#115544)

The input generating functions for benchmark tests in the GenerateInput.h
file can be slightly improved by invoking vector::reserve before calling
vector::push_back. This slight performance improvement could potentially
speed-up all benchmark tests for containers and algorithms that use these
functions as inputs.

show more ...

[libc++][test] Clean up code in GenerateInput.h for benchmark testing (#115560)

This PR refines the code in `GenerateInput.h` used for benchmark testing
by implementing the following changes:

-

[libc++][test] Clean up code in GenerateInput.h for benchmark testing (#115560)

This PR refines the code in `GenerateInput.h` used for benchmark testing
by implementing the following changes:

- Replaced all unqualified usages of `size_t` with `std::size_t`.
- Removed unnecessary curly braces `{}` from for loops that contain
simple single-statement bodies, in accordance with LLVM coding
standards.

show more ...

[libc++][NFC] Add missing license headers

Also standardize the license comment in several files where it was
different from what we normally do.

[libc++] Move the benchmarks under libcxx/test (#99371)

This is an intermediate and fairly mechanical step towards unifying the
benchmarks with the rest of the test suite. Moving this around requir

[libc++] Move the benchmarks under libcxx/test (#99371)

This is an intermediate and fairly mechanical step towards unifying the
benchmarks with the rest of the test suite. Moving this around requires
a few changes, notably making sure we don't throw a wrench into the
discovery process of the normal test suite. This won't be a problem
anymore once benchmarks are taken into account by the test setup out of
the box.

show more ...