[libcxx][nfc] Remove <algorithm>'s dependence on <iterator> and related changes.

[zoecarver]

Summary

This removes a few dependencies on <iterator> which removes the dependency cycle between iterator -> variant -> array -> iterator and iterator -> algorithm -> iterator and iterator -> memory -> algorithm -> iterator so that we can use variant in common_iterator.

[zoecarver]

Rebase on main.

[zoecarver]

A simpler way to say the words in the title: this removes <algorithm>'s dependency on both <memory> and <iterator>. (<memory> still depends on <iterator>.)

[zoecarver]

Fix rebase fallout (in <iterator>).

[• Quuxplusone]

libcxx/include/__algorithm/equal.h

16

a-z plz

libcxx/include/__algorithm/is_permutation.h

17

a-z plz (and throughout, anywhere I missed)

libcxx/include/__functional/function.h

22

a-z plz

libcxx/include/algorithm

655

This line is duplicated (see below in a-z order)

libcxx/include/array

116

a-z plz

libcxx/include/functional

518

As @EricWF and @ldionne (and I) have said, removing user-visible inclusions really ought to be done in separate commits and advertised. If we're breaking

#include <functional>
std::unique_ptr<int> p;

then that needs to be advertised somehow before we do it. Or discussed. Or something. (I mean, we just keep churning these headers — I'm sure we've broken many things already — but expect to keep hearing the same old squeaky wheels until the churn stops.)

[cjdb]

Splitting stuff out of <memory> is good, but please don't remove any header inclusions just yet. A cross-sectional plan (that I'm working out) needs to be put into place before we can delete our inclusions.

EDIT: if we need to remove something, we'll need to precisely document it in our release notes (including why we needed to push the deletion ahead of schedule), and give users the chance to respond to this change.

[zoecarver]

EDIT: if we need to remove something, we'll need to precisely document it in our release notes (including why we needed to push the deletion ahead of schedule), and give users the chance to respond to this change.

If we want to use variant in common_iterator (which I am neutral on at best) we do need to remove something. We can do one of the following:

1. Remove <iterator> and <algorithm> from <array>
2. Remove <memory> and <iterator> from <algorithm> (current).

Putting this here preemptively: based on recent discussions, I'm going to do the first one, as that seems to be lower-impact. I'm also going to keep all the changes to internal headers, but make sure that external headers still provide the same includes (except for <array>).

[ldionne]

Zoe and I just spoke.

He's going to turn this into a NFC where we don't remove includes from the "public" headers, but still split stuff out of <memory>.

In a follow-up patch, we can try to break the cycle between <variant> and <array> by using a raw C array in variant's implementation and removing #include <array> from <variant>. Yes, that will be a breaking change. But I don't think we need a formal release note and discussion for just that one - we've been making small breaking changes such as this without even noticing it for years. While we should have a discussion if we're going to do something major and systematic like in D104980, we shouldn't prevent ourselves from making progress for something as simple as this.

This LGTM once the patch is updated to be a NFC (giving thumbs up proactively because we're not in the same time zone and I want this to be unblocked).

[zoecarver]

• Alphabatize.
• Update module map.
• Make this a NFC for real.

[cjdb]

Now that it's NFC, also proactively LGTMing.

[zoecarver]

Fix modules build (fully expecting it to crash).

[zoecarver]

I may pick this patch up again later, but for now, I am not going to spend hours debugging why clang is crashing. This patch is not blocking anything.

libcxx/include/CMakeLists.txt

set(files
   __libcpp_version
   __locale
   __memory/addressof.h
   __memory/allocation_guard.h
   __memory/allocator_arg_t.h
   __memory/allocator_traits.h
   __memory/allocator.h
   __memory/auto_ptr.h
+  __memory/builtin_new_allocator.h
   __memory/compressed_pair.h
   __memory/construct_at.h
+  __memory/destruct_n.h
   __memory/pointer_safety.h
   __memory/pointer_traits.h
   __memory/raw_storage_iterator.h
   __memory/shared_ptr.h
   __memory/temporary_buffer.h
   __memory/uninitialized_algorithms.h
   __memory/unique_ptr.h
   __memory/uses_allocator.h

libcxx/include/__algorithm/equal.h

 // -*- C++ -*-
 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP___ALGORITHM_EQUAL_H
 #define _LIBCPP___ALGORITHM_EQUAL_H
 
 #include <__config>
 #include <__algorithm/comp.h>
 #include <__iterator/iterator_traits.h>
-#include <iterator> // FIXME: replace with <__iterator/distance.h> when it lands
+#include <__iterator/distance.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
 

libcxx/include/__algorithm/equal_range.h

 #define _LIBCPP___ALGORITHM_EQUAL_RANGE_H
 
 #include <__config>
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
 #include <__algorithm/half_positive.h>
 #include <__algorithm/lower_bound.h>
 #include <__algorithm/upper_bound.h>
-#include <iterator>
+#include <__iterator/distance.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
 

libcxx/include/__algorithm/inplace_merge.h

 #include <__algorithm/comp_ref_type.h>
 #include <__algorithm/comp.h>
 #include <__algorithm/lower_bound.h>
 #include <__algorithm/min.h>
 #include <__algorithm/move.h>
 #include <__algorithm/rotate.h>
 #include <__algorithm/upper_bound.h>
 #include <__iterator/iterator_traits.h>
+#include <__iterator/reverse_iterator.h>
+#include <__memory/destruct_n.h>
+#include <__memory/temporary_buffer.h>
+#include <__memory/unique_ptr.h>
 #include <__utility/swap.h>
-#include <memory>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
 

libcxx/include/__algorithm/is_permutation.h

 // -*- C++ -*-
 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP___ALGORITHM_IS_PERMUTATION_H
 #define _LIBCPP___ALGORITHM_IS_PERMUTATION_H
 
 #include <__algorithm/comp.h>
 #include <__config>
 #include <__iterator/iterator_traits.h>
 #include <__iterator/next.h>
-#include <iterator> // FIXME: replace with <__iterator/distance.h> when it lands
+#include <__iterator/distance.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
 

libcxx/include/__algorithm/lower_bound.h

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP___ALGORITHM_LOWER_BOUND_H
 #define _LIBCPP___ALGORITHM_LOWER_BOUND_H
 
 #include <__config>
 #include <__algorithm/comp.h>
 #include <__algorithm/half_positive.h>
-#include <iterator>
+#include <__iterator/advance.h>
+#include <__iterator/distance.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
 

libcxx/include/__algorithm/partition_point.h

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP___ALGORITHM_PARTITION_POINT_H
 #define _LIBCPP___ALGORITHM_PARTITION_POINT_H
 
 #include <__config>
 #include <__algorithm/half_positive.h>
-#include <iterator>
+#include <__iterator/distance.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
 

libcxx/include/__algorithm/rotate.h

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP___ALGORITHM_ROTATE_H
 #define _LIBCPP___ALGORITHM_ROTATE_H
 
 #include <__algorithm/move.h>
 #include <__algorithm/move_backward.h>
 #include <__algorithm/swap_ranges.h>
 #include <__config>
+#include <__iterator/distance.h>
 #include <__iterator/iterator_traits.h>
 #include <__iterator/next.h>
 #include <__iterator/prev.h>
 #include <__utility/swap.h>
-#include <iterator>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
 

libcxx/include/__algorithm/rotate_copy.h

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP___ALGORITHM_ROTATE_COPY_H
 #define _LIBCPP___ALGORITHM_ROTATE_COPY_H
 
 #include <__config>
 #include <__algorithm/copy.h>
-#include <iterator>
 #include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>

libcxx/include/__algorithm/sample.h

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP___ALGORITHM_SAMPLE_H
 #define _LIBCPP___ALGORITHM_SAMPLE_H
 
 #include <__config>
 #include <__algorithm/min.h>
+#include <__iterator/distance.h>
 #include <__random/uniform_int_distribution.h>
-#include <iterator>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
 

libcxx/include/__algorithm/sort.h

 #define _LIBCPP___ALGORITHM_SORT_H
 
 #include <__config>
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
 #include <__algorithm/min_element.h>
 #include <__algorithm/partial_sort.h>
 #include <__algorithm/unwrap_iter.h>
+#include <__memory/destruct_n.h>
+#include <__memory/unique_ptr.h>
 #include <__utility/swap.h>
-#include <memory>
 #include <type_traits> // swap
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>

libcxx/include/__algorithm/stable_partition.h

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP___ALGORITHM_STABLE_PARTITION_H
 #define _LIBCPP___ALGORITHM_STABLE_PARTITION_H
 
 #include <__config>
 #include <__algorithm/rotate.h>
 #include <__iterator/iterator_traits.h>
+#include <__memory/destruct_n.h>
+#include <__memory/unique_ptr.h>
 #include <__utility/swap.h>
-#include <memory>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
 

libcxx/include/__algorithm/stable_sort.h

 #define _LIBCPP___ALGORITHM_STABLE_SORT_H
 
 #include <__config>
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
 #include <__algorithm/inplace_merge.h>
 #include <__algorithm/sort.h>
 #include <__iterator/iterator_traits.h>
+#include <__memory/destruct_n.h>
+#include <__memory/unique_ptr.h>
 #include <__utility/swap.h>
-#include <memory>
 #include <type_traits> // swap
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>

libcxx/include/__algorithm/unwrap_iter.h

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP___ALGORITHM_UNWRAP_ITER_H
 #define _LIBCPP___ALGORITHM_UNWRAP_ITER_H
 
 #include <__config>
-#include <iterator>
+#include <__iterator/iterator_traits.h>
 #include <__memory/pointer_traits.h>
 #include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS

libcxx/include/__algorithm/upper_bound.h

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP___ALGORITHM_UPPER_BOUND_H
 #define _LIBCPP___ALGORITHM_UPPER_BOUND_H
 
 #include <__config>
 #include <__algorithm/comp.h>
 #include <__algorithm/half_positive.h>
-#include <iterator>
+#include <__iterator/distance.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
 

libcxx/include/__functional/function.h

 #include <__functional/binary_function.h>
 #include <__functional/invoke.h>
 #include <__functional/unary_function.h>
 #include <__iterator/iterator_traits.h>
 #include <__memory/allocator_traits.h>
 #include <__memory/compressed_pair.h>
 #include <__memory/shared_ptr.h>
 #include <exception>
-#include <memory> // TODO: replace with <__memory/__builtin_new_allocator.h>
+#include <__memory/builtin_new_allocator.h>
 #include <type_traits>
 #include <utility>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD

libcxx/include/__memory/builtin_new_allocator.h

+// -*- C++ -*-
+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP___MEMORY_BUILTIN_NEW_ALLOCATOR_H
+#define _LIBCPP___MEMORY_BUILTIN_NEW_ALLOCATOR_H
+
+#include <__config>
+#include <__memory/unique_ptr.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#pragma GCC system_header
+#endif
+
+_LIBCPP_PUSH_MACROS
+#include <__undef_macros>
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+// __builtin_new_allocator -- A non-templated helper for allocating and
+// deallocating memory using __builtin_operator_new and
+// __builtin_operator_delete. It should be used in preference to
+// `std::allocator<T>` to avoid additional instantiations.
+struct __builtin_new_allocator {
+  struct __builtin_new_deleter {
+    typedef void* pointer_type;
+
+    _LIBCPP_CONSTEXPR explicit __builtin_new_deleter(size_t __size, size_t __align)
+        : __size_(__size), __align_(__align) {}
+
+    void operator()(void* p) const _NOEXCEPT {
+        _VSTD::__libcpp_deallocate(p, __size_, __align_);
+    }
+
+   private:
+    size_t __size_;
+    size_t __align_;
+  };
+
+  typedef unique_ptr<void, __builtin_new_deleter> __holder_t;
+
+  static __holder_t __allocate_bytes(size_t __s, size_t __align) {
+      return __holder_t(_VSTD::__libcpp_allocate(__s, __align),
+                     __builtin_new_deleter(__s, __align));
+  }
+
+  static void __deallocate_bytes(void* __p, size_t __s,
+                                 size_t __align) _NOEXCEPT {
+      _VSTD::__libcpp_deallocate(__p, __s, __align);
+  }
+
+  template <class _Tp>
+  _LIBCPP_NODEBUG _LIBCPP_ALWAYS_INLINE
+  static __holder_t __allocate_type(size_t __n) {
+      return __allocate_bytes(__n * sizeof(_Tp), _LIBCPP_ALIGNOF(_Tp));
+  }
+
+  template <class _Tp>
+  _LIBCPP_NODEBUG _LIBCPP_ALWAYS_INLINE
+  static void __deallocate_type(void* __p, size_t __n) _NOEXCEPT {
+      __deallocate_bytes(__p, __n * sizeof(_Tp), _LIBCPP_ALIGNOF(_Tp));
+  }
+};
+
+_LIBCPP_END_NAMESPACE_STD
+
+_LIBCPP_POP_MACROS
+
+#endif // _LIBCPP___MEMORY_BUILTIN_NEW_ALLOCATOR_H

libcxx/include/__memory/destruct_n.h

+// -*- C++ -*-
+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP___MEMORY_DESTRUCT_N_H
+#define _LIBCPP___MEMORY_DESTRUCT_N_H
+
+#include <__config>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#pragma GCC system_header
+#endif
+
+_LIBCPP_PUSH_MACROS
+#include <__undef_macros>
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+struct __destruct_n
+{
+private:
+    size_t __size_;
+
+    template <class _Tp>
+    _LIBCPP_INLINE_VISIBILITY void __process(_Tp* __p, false_type) _NOEXCEPT
+        {for (size_t __i = 0; __i < __size_; ++__i, ++__p) __p->~_Tp();}
+
+    template <class _Tp>
+    _LIBCPP_INLINE_VISIBILITY void __process(_Tp*, true_type) _NOEXCEPT
+        {}
+
+    _LIBCPP_INLINE_VISIBILITY void __incr(false_type) _NOEXCEPT
+        {++__size_;}
+    _LIBCPP_INLINE_VISIBILITY void __incr(true_type) _NOEXCEPT
+        {}
+
+    _LIBCPP_INLINE_VISIBILITY void __set(size_t __s, false_type) _NOEXCEPT
+        {__size_ = __s;}
+    _LIBCPP_INLINE_VISIBILITY void __set(size_t, true_type) _NOEXCEPT
+        {}
+public:
+    _LIBCPP_INLINE_VISIBILITY explicit __destruct_n(size_t __s) _NOEXCEPT
+        : __size_(__s) {}
+
+    template <class _Tp>
+    _LIBCPP_INLINE_VISIBILITY void __incr() _NOEXCEPT
+        {__incr(integral_constant<bool, is_trivially_destructible<_Tp>::value>());}
+
+    template <class _Tp>
+    _LIBCPP_INLINE_VISIBILITY void __set(size_t __s, _Tp*) _NOEXCEPT
+        {__set(__s, integral_constant<bool, is_trivially_destructible<_Tp>::value>());}
+
+    template <class _Tp>
+    _LIBCPP_INLINE_VISIBILITY void operator()(_Tp* __p) _NOEXCEPT
+        {__process(__p, integral_constant<bool, is_trivially_destructible<_Tp>::value>());}
+};
+
+_LIBCPP_END_NAMESPACE_STD
+
+_LIBCPP_POP_MACROS
+
+#endif // _LIBCPP___MEMORY_DESTRUCT_N_H

libcxx/include/__split_buffer

 // -*- C++ -*-
 #ifndef _LIBCPP_SPLIT_BUFFER
 #define _LIBCPP_SPLIT_BUFFER
 
 #include <__config>
 #include <__utility/forward.h>
 #include <algorithm>
+#include <memory>
 #include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>

libcxx/include/algorithm

 
 #include <__config>
 #include <__debug>
 #include <__bits> // __libcpp_clz
 #include <cstddef>
 #include <cstring>
 #include <functional>
 #include <initializer_list>
 #include <utility> // needed to provide swap_ranges.
-#include <memory>
-#include <iterator>
-#include <memory>
 #include <type_traits>
 #include <utility> // swap_ranges
 #include <version>
 
 #include <__algorithm/adjacent_find.h>
 #include <__algorithm/all_of.h>
 #include <__algorithm/any_of.h>
 #include <__algorithm/binary_search.h>

libcxx/include/array

 
 */
 
 #include <__config>
 #include <__debug>
 #include <__tuple>
 #include <algorithm>
 #include <cstdlib> // for _LIBCPP_UNREACHABLE
-#include <iterator>
+#include <__iterator/reverse_iterator.h>
 #include <stdexcept>
 #include <type_traits>
 #include <utility>
 #include <version>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif

libcxx/include/functional

 #include <__functional/ranges_operations.h>
 #include <__functional/reference_wrapper.h>
 #include <__functional/unary_function.h> // TODO: deprecate
 #include <__functional/unary_negate.h>
 #include <__functional/unwrap_ref.h>
 #include <__utility/forward.h>
 #include <concepts>
 #include <exception>
-#include <memory>
 #include <tuple>
 #include <type_traits>
 #include <typeinfo>
 #include <utility>
 #include <version>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 #endif // _LIBCPP_FUNCTIONAL

libcxx/include/memory

 
 #include <__config>
 #include <__functional_base>
 #include <__memory/addressof.h>
 #include <__memory/allocation_guard.h>
 #include <__memory/allocator.h>
 #include <__memory/allocator_arg_t.h>
 #include <__memory/allocator_traits.h>
+#include <__memory/builtin_new_allocator.h>
 #include <__memory/compressed_pair.h>
 #include <__memory/construct_at.h>
+#include <__memory/destruct_n.h>
 #include <__memory/pointer_safety.h>
 #include <__memory/pointer_traits.h>
 #include <__memory/raw_storage_iterator.h>
 #include <__memory/shared_ptr.h>
 #include <__memory/temporary_buffer.h>
 #include <__memory/uninitialized_algorithms.h>
 #include <__memory/unique_ptr.h>
 #include <__memory/uses_allocator.h>

 _LIBCPP_INLINE_VISIBILITY
 void __construct_backward_with_exception_guarantees(_Alloc&, _Tp* __begin1, _Tp* __end1, _Tp*& __end2) {
     ptrdiff_t _Np = __end1 - __begin1;
     __end2 -= _Np;
     if (_Np > 0)
         _VSTD::memcpy(__end2, __begin1, _Np * sizeof(_Tp));
 }
 
-struct __destruct_n
-{
-private:
-    size_t __size_;
-
-    template <class _Tp>
-    _LIBCPP_INLINE_VISIBILITY void __process(_Tp* __p, false_type) _NOEXCEPT
-        {for (size_t __i = 0; __i < __size_; ++__i, ++__p) __p->~_Tp();}
-
-    template <class _Tp>
-    _LIBCPP_INLINE_VISIBILITY void __process(_Tp*, true_type) _NOEXCEPT
-        {}
-
-    _LIBCPP_INLINE_VISIBILITY void __incr(false_type) _NOEXCEPT
-        {++__size_;}
-    _LIBCPP_INLINE_VISIBILITY void __incr(true_type) _NOEXCEPT
-        {}
-
-    _LIBCPP_INLINE_VISIBILITY void __set(size_t __s, false_type) _NOEXCEPT
-        {__size_ = __s;}
-    _LIBCPP_INLINE_VISIBILITY void __set(size_t, true_type) _NOEXCEPT
-        {}
-public:
-    _LIBCPP_INLINE_VISIBILITY explicit __destruct_n(size_t __s) _NOEXCEPT
-        : __size_(__s) {}
-
-    template <class _Tp>
-    _LIBCPP_INLINE_VISIBILITY void __incr() _NOEXCEPT
-        {__incr(integral_constant<bool, is_trivially_destructible<_Tp>::value>());}
-
-    template <class _Tp>
-    _LIBCPP_INLINE_VISIBILITY void __set(size_t __s, _Tp*) _NOEXCEPT
-        {__set(__s, integral_constant<bool, is_trivially_destructible<_Tp>::value>());}
-
-    template <class _Tp>
-    _LIBCPP_INLINE_VISIBILITY void operator()(_Tp* __p) _NOEXCEPT
-        {__process(__p, integral_constant<bool, is_trivially_destructible<_Tp>::value>());}
-};
-
 _LIBCPP_FUNC_VIS void* align(size_t __align, size_t __sz, void*& __ptr, size_t& __space);
 
 // --- Helper for container swap --
 template <typename _Alloc>
 _LIBCPP_INLINE_VISIBILITY
 void __swap_allocator(_Alloc & __a1, _Alloc & __a2, true_type)
 #if _LIBCPP_STD_VER >= 14
     _NOEXCEPT

 
 template<typename _Alloc>
 struct __is_allocator<_Alloc,
        typename __void_t<typename _Alloc::value_type>::type,
        typename __void_t<decltype(declval<_Alloc&>().allocate(size_t(0)))>::type
      >
    : true_type {};
 
-// __builtin_new_allocator -- A non-templated helper for allocating and
-// deallocating memory using __builtin_operator_new and
-// __builtin_operator_delete. It should be used in preference to
-// `std::allocator<T>` to avoid additional instantiations.
-struct __builtin_new_allocator {
-  struct __builtin_new_deleter {
-    typedef void* pointer_type;
-
-    _LIBCPP_CONSTEXPR explicit __builtin_new_deleter(size_t __size, size_t __align)
-        : __size_(__size), __align_(__align) {}
-
-    void operator()(void* p) const _NOEXCEPT {
-        _VSTD::__libcpp_deallocate(p, __size_, __align_);
-    }
-
-   private:
-    size_t __size_;
-    size_t __align_;
-  };
-
-  typedef unique_ptr<void, __builtin_new_deleter> __holder_t;
-
-  static __holder_t __allocate_bytes(size_t __s, size_t __align) {
-      return __holder_t(_VSTD::__libcpp_allocate(__s, __align),
-                     __builtin_new_deleter(__s, __align));
-  }
-
-  static void __deallocate_bytes(void* __p, size_t __s,
-                                 size_t __align) _NOEXCEPT {
-      _VSTD::__libcpp_deallocate(__p, __s, __align);
-  }
-
-  template <class _Tp>
-  _LIBCPP_NODEBUG _LIBCPP_ALWAYS_INLINE
-  static __holder_t __allocate_type(size_t __n) {
-      return __allocate_bytes(__n * sizeof(_Tp), _LIBCPP_ALIGNOF(_Tp));
-  }
-
-  template <class _Tp>
-  _LIBCPP_NODEBUG _LIBCPP_ALWAYS_INLINE
-  static void __deallocate_type(void* __p, size_t __n) _NOEXCEPT {
-      __deallocate_bytes(__p, __n * sizeof(_Tp), _LIBCPP_ALIGNOF(_Tp));
-  }
-};
-
-
 _LIBCPP_END_NAMESPACE_STD
 
 _LIBCPP_POP_MACROS
 
 #if defined(_LIBCPP_HAS_PARALLEL_ALGORITHMS) && _LIBCPP_STD_VER >= 17
 #   include <__pstl_memory>
 #endif
 
 #endif // _LIBCPP_MEMORY

libcxx/include/valarray

 template <class T> unspecified1 end(valarray<T>& v);
 template <class T> unspecified2 end(const valarray<T>& v);
 
 }  // std
 
 */
 
 #include <__config>
+#include <__memory/uninitialized_algorithms.h>
 #include <algorithm>
 #include <cmath>
 #include <cstddef>
 #include <functional>
 #include <initializer_list>
 #include <new>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)

libcxx/include/vector

 
 */
 
 #include <__config>
 #include <__bit_reference>
 #include <__debug>
 #include <__functional_base>
 #include <__iterator/wrap_iter.h>
+#include <__iterator/move_iterator.h>
 #include <__split_buffer>
 #include <__utility/forward.h>
 #include <algorithm>
 #include <climits>
 #include <compare>
 #include <cstring>
 #include <initializer_list>
 #include <iosfwd> // for forward declaration of vector