[libc++][ranges] Implement the changes to `deque` from P1206 (`ranges::to`):

[var-const]

Summary

• add the from_range_t constructors and the related deduction guides;
• add the insert_range/assign_range/etc. member functions.

(Note: this patch is split from https://reviews.llvm.org/D142335)

[ldionne]

libcxx/include/__algorithm/copy_n.h

42

I think this needs a LWG issue.std::copy_n and ranges::copy_n have the exact same specification (http://eel.is/c++draft/alg.copy#lib:copy_n), but std::copy_n seems to be expected not to increment the input iterator if it can avoid it. ranges::copy_n does increment the iterator. For something like istream_iterator, this means we will be extracting different numbers of elements from the underlying stream.

This feels similar to the views::take issue we discussed in Issaquah, it might be worth checking whether that issue did talk about copy_n as another case of the same problem.

But for certain, I think we'll break users if we start increment this here, so we shouldn't do it unless we're blessed by the standard explicitly.

[var-const]

Fix the CI and rebase.

[var-const]

Sort includes

[var-const]

Fix CI.

[var-const]

Rebase on main (now that the vector patch is committed, the delta is significantly reduced).

[var-const]

libcxx/include/__algorithm/copy_n.h

42

Digging through the list of LWG issues, this has been raised before ranges as http://wg21.link/lwg2471. Ranges do make the issue more noticeable, though, because now the discrepancy is not just between copy_n and uninitialized_copy_n, but also copy_n and ranges::copy_n. It doesn't look like there's been any update on the issue, though.

@jwakely Were there any updates on this issue? I seem to remember this issue being brought up in Issaquah, but I couldn't find anything in LWG notes, so I might be confusing this with something. I can file a new LWG issue to talk specifically about the discrepancy between copy_n and ranges::copy_n -- do you think it makes sense?

[var-const]

Feedback

libcxx/include/__algorithm/copy_n.h

42

@ldionne I ended up doing two versions of assign_with_size -- one for random access iterators and one for everything else. The random-access iterator version is essentially the previous implementation that uses std::copy (with all the potential optimizations). The other version essentially inlines copy_n (thankfully it's trivial without optimizations, which don't apply in this case) but keeps track of the incremented input iterator to avoid going through the input range twice. It's still more efficient than assign_with_sentinel: only one comparison per iteration when copying input elements into the existing capacity (the sentinel version has to compare both the input iterator and the deque iterator to their respective sentinels), and it can also allocate the necessary additional capacity at once.

[ldionne]

LGTM w/ comments. In particular it would be nice to confirm that this doesn't introduce a regression in the existing deque methods (I don't think it would, but it's simple to confirm). Thanks!

libcxx/include/deque

1286–1297

Feel free to clang-format this bit.

1290

I would either use the integer as a counter (since then we know comparison is cheap), or at least cache end() since it's kind of expensive and we don't know for sure whether the compiler is smart enough hoist it out.

libcxx/test/std/containers/sequences/deque/deque.cons/from_range.pass.cpp

2

I think we should also add benchmarks in libcxx/benchmarks/ContainerBenchmarks.h for the new construction methods we're adding.

[var-const]

libcxx/test/std/containers/sequences/deque/deque.cons/from_range.pass.cpp

2

Done (also added for vector). This patch doesn't seem to make any difference for existing constructors (seems within fluctuation) and the difference between the (iter, iter) constructor and the from_range constructor also appears negligible as expected.

For completeness' sake, here are the results before this patch:

-----------------------------------------------------------------------------------
Benchmark                                         Time             CPU   Iterations
-----------------------------------------------------------------------------------
BM_ConstructSize/deque_byte/5140480          232868 ns       220132 ns         3163
BM_ConstructSizeValue/deque_byte/5140480     189452 ns       172314 ns         4026
BM_ConstructIterIter/deque_char/1024           79.0 ns         78.9 ns      9187075
BM_ConstructIterIter/deque_size_t/1024          300 ns          300 ns      2223959
BM_ConstructIterIter/deque_string/1024       107435 ns       107390 ns         6744

And with this patch:

-----------------------------------------------------------------------------------
Benchmark                                         Time             CPU   Iterations
-----------------------------------------------------------------------------------
BM_ConstructSize/deque_byte/5140480          231027 ns       219294 ns         3148
BM_ConstructSizeValue/deque_byte/5140480     176521 ns       170531 ns         4105
BM_ConstructIterIter/deque_char/1024           77.5 ns         76.0 ns      9186111
BM_ConstructIterIter/deque_size_t/1024          301 ns          301 ns      2327840
BM_ConstructIterIter/deque_string/1024       105603 ns       105535 ns         6881
BM_ConstructFromRange/deque_char/1024          74.3 ns         74.2 ns      9481112
BM_ConstructFromRange/deque_size_t/1024         301 ns          301 ns      2288232
BM_ConstructFromRange/deque_string/1024      100816 ns       100813 ns         6983

And also vector with this patch:

------------------------------------------------------------------------------------
Benchmark                                          Time             CPU   Iterations
------------------------------------------------------------------------------------
BM_ConstructSize/vector_byte/5140480          272017 ns       271861 ns         2394
BM_ConstructSizeValue/vector_byte/5140480     260968 ns       260866 ns         2566
BM_ConstructIterIter/vector_char/1024           39.5 ns         39.5 ns     17688158
BM_ConstructIterIter/vector_size_t/1024          139 ns          139 ns      5072096
BM_ConstructIterIter/vector_string/1024        94366 ns        94365 ns         7484
BM_ConstructFromRange/vector_char/1024          40.1 ns         40.1 ns     17496195
BM_ConstructFromRange/vector_size_t/1024         157 ns          148 ns      4767970
BM_ConstructFromRange/vector_string/1024      107067 ns       102741 ns         6937

[var-const]

Address feedback and rebase.

[var-const]

A note in case it every comes in handy later: while working on this patch, I noticed that deque tests are significantly (5-10x) slower compared to the equivalent vector tests when compiled by GCC; with Clang, the difference is almost negligible. This is a preexisting issue -- running the test suite for insert_range while using the old insert function that takes two iterators on main shows a similarly large performance difference when compiling with GCC. From a conversation with @ldionne, one explanation could be that when compiling under GCC, many functions get force-inlined which might affect deque more significantly (and negatively) than vector. In any case, this patch doesn't make the situation worse.

[var-const]

Fix bug.

[ldionne]

Thanks for adding benchmarks! LGTM once CI passes, which I think will require a CMake update on the Windows bots or some other workaround.

[var-const]

Remove the benchmarks (moved to a separate patch: https://reviews.llvm.org/D150747).

[var-const]

Note: the benchmarks have been moved to https://reviews.llvm.org/D150747 (because they fail on the CI under Windows and I don't want to block this patch on that investigation).

libcxx/include/__algorithm/copy_n.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_COPY_N_H
 #define _LIBCPP___ALGORITHM_COPY_N_H
 
 #include <__algorithm/copy.h>
+#include <__algorithm/iterator_operations.h>
 #include <__config>
 #include <__iterator/iterator_traits.h>
 #include <__type_traits/enable_if.h>
 #include <__utility/convert_to_integral.h>
+#include <__utility/move.h>
+#include <__utility/pair.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template<class _InputIterator, class _Size, class _OutputIterator>
+template <class _AlgPolicy, class _InputIterator, class _Size, class _OutputIterator>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20
 typename enable_if
 <
     __is_cpp17_input_iterator<_InputIterator>::value &&
    !__is_cpp17_random_access_iterator<_InputIterator>::value,
-    _OutputIterator
+    pair<_InputIterator, _OutputIterator>
 >::type
-copy_n(_InputIterator __first, _Size __orig_n, _OutputIterator __result)
+__copy_n(_InputIterator __first, _Size __orig_n, _OutputIterator __result)
 {
     typedef decltype(_VSTD::__convert_to_integral(__orig_n)) _IntegralSize;
     _IntegralSize __n = __orig_n;
     if (__n > 0)
     {
         *__result = *__first;
+        ++__first;
         ++__result;
         for (--__n; __n > 0; --__n)
         {
-            ++__first;
             *__result = *__first;
+            ++__first;
             ++__result;
         }
     }
-    return __result;
+    return std::make_pair(std::move(__first), std::move(__result));
 }
 
-template<class _InputIterator, class _Size, class _OutputIterator>
+template <class _AlgPolicy, class _InputIterator, class _Size, class _OutputIterator>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20
 typename enable_if
 <
     __is_cpp17_random_access_iterator<_InputIterator>::value,
-    _OutputIterator
+    pair<_InputIterator, _OutputIterator>
 >::type
-copy_n(_InputIterator __first, _Size __orig_n, _OutputIterator __result)
+__copy_n(_InputIterator __first, _Size __orig_n, _OutputIterator __result)
 {
-    typedef typename iterator_traits<_InputIterator>::difference_type difference_type;
+    using difference_type = typename _IterOps<_AlgPolicy>:: template __difference_type<_InputIterator>;
     typedef decltype(_VSTD::__convert_to_integral(__orig_n)) _IntegralSize;
     _IntegralSize __n = __orig_n;
-    return _VSTD::copy(__first, __first + difference_type(__n), __result);
+    return std::__copy<_AlgPolicy>(__first, __first + difference_type(__n), __result);
+}
+
+template<class _InputIterator, class _Size, class _OutputIterator>
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
+_OutputIterator copy_n(_InputIterator __first, _Size __n, _OutputIterator __result)
+{
+  return std::__copy_n<_ClassicAlgPolicy>(std::move(__first), __n, std::move(__result)).second;
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_COPY_N_H

libcxx/include/deque

public:
     explicit deque(size_type n);
     explicit deque(size_type n, const allocator_type& a); // C++14
     deque(size_type n, const value_type& v);
     deque(size_type n, const value_type& v, const allocator_type& a);
     template <class InputIterator>
         deque(InputIterator f, InputIterator l);
     template <class InputIterator>
         deque(InputIterator f, InputIterator l, const allocator_type& a);
+    template<container-compatible-range<T> R>
+        deque(from_range_t, R&& rg, const Allocator& = Allocator()); // C++23
     deque(const deque& c);
     deque(deque&& c)
         noexcept(is_nothrow_move_constructible<allocator_type>::value);
     deque(initializer_list<value_type> il, const Allocator& a = allocator_type());
     deque(const deque& c, const allocator_type& a);
     deque(deque&& c, const allocator_type& a);
     ~deque();
 
     deque& operator=(const deque& c);
     deque& operator=(deque&& c)
         noexcept(
              allocator_type::propagate_on_container_move_assignment::value &&
              is_nothrow_move_assignable<allocator_type>::value);
     deque& operator=(initializer_list<value_type> il);
 
     template <class InputIterator>
         void assign(InputIterator f, InputIterator l);
+    template<container-compatible-range<T> R>
+      void assign_range(R&& rg); // C++23
     void assign(size_type n, const value_type& v);
     void assign(initializer_list<value_type> il);
 
     allocator_type get_allocator() const noexcept;
 
     // iterators:
 
     iterator       begin() noexcept;
public:
     reference front();
     const_reference front() const;
     reference back();
     const_reference back() const;
 
     // modifiers:
     void push_front(const value_type& v);
     void push_front(value_type&& v);
+    template<container-compatible-range<T> R>
+      void prepend_range(R&& rg); // C++23
     void push_back(const value_type& v);
     void push_back(value_type&& v);
+    template<container-compatible-range<T> R>
+      void append_range(R&& rg); // C++23
     template <class... Args> reference emplace_front(Args&&... args);  // reference in C++17
     template <class... Args> reference emplace_back(Args&&... args);   // reference in C++17
     template <class... Args> iterator emplace(const_iterator p, Args&&... args);
     iterator insert(const_iterator p, const value_type& v);
     iterator insert(const_iterator p, value_type&& v);
     iterator insert(const_iterator p, size_type n, const value_type& v);
     template <class InputIterator>
         iterator insert(const_iterator p, InputIterator f, InputIterator l);
+    template<container-compatible-range<T> R>
+      iterator insert_range(const_iterator position, R&& rg); // C++23
     iterator insert(const_iterator p, initializer_list<value_type> il);
     void pop_front();
     void pop_back();
     iterator erase(const_iterator p);
     iterator erase(const_iterator f, const_iterator l);
     void swap(deque& c)
         noexcept(allocator_traits<allocator_type>::is_always_equal::value);  // C++17
     void clear() noexcept;
 };
 
 template <class InputIterator, class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
    deque(InputIterator, InputIterator, Allocator = Allocator())
    -> deque<typename iterator_traits<InputIterator>::value_type, Allocator>; // C++17
 
+template<ranges::input_range R, class Allocator = allocator<ranges::range_value_t<R>>>
+  deque(from_range_t, R&&, Allocator = Allocator())
+    -> deque<ranges::range_value_t<R>, Allocator>; // C++23
+
 template <class T, class Allocator>
     bool operator==(const deque<T,Allocator>& x, const deque<T,Allocator>& y);
 template <class T, class Allocator>
     bool operator< (const deque<T,Allocator>& x, const deque<T,Allocator>& y); // removed in C++20
 template <class T, class Allocator>
     bool operator!=(const deque<T,Allocator>& x, const deque<T,Allocator>& y); // removed in C++20
 template <class T, class Allocator>
     bool operator> (const deque<T,Allocator>& x, const deque<T,Allocator>& y); // removed in C++20
template <class T, class Allocator, class Predicate>
     erase_if(deque<T, Allocator>& c, Predicate pred);    // C++20
 
 }  // std
 
 */
 
 #include <__algorithm/copy.h>
 #include <__algorithm/copy_backward.h>
+#include <__algorithm/copy_n.h>
 #include <__algorithm/equal.h>
 #include <__algorithm/fill_n.h>
+#include <__algorithm/iterator_operations.h>
 #include <__algorithm/lexicographical_compare.h>
 #include <__algorithm/lexicographical_compare_three_way.h>
 #include <__algorithm/min.h>
 #include <__algorithm/remove.h>
 #include <__algorithm/remove_if.h>
 #include <__algorithm/unwrap_iter.h>
 #include <__assert> // all public C++ headers provide the assertion handler
 #include <__config>
 #include <__format/enable_insertable.h>
+#include <__iterator/distance.h>
 #include <__iterator/iterator_traits.h>
 #include <__iterator/next.h>
 #include <__iterator/prev.h>
 #include <__iterator/reverse_iterator.h>
 #include <__iterator/segmented_iterator.h>
 #include <__memory/addressof.h>
 #include <__memory/allocator_destructor.h>
 #include <__memory/pointer_traits.h>
 #include <__memory/temp_value.h>
 #include <__memory/unique_ptr.h>
 #include <__memory_resource/polymorphic_allocator.h>
+#include <__ranges/access.h>
+#include <__ranges/concepts.h>
+#include <__ranges/container_compatible_range.h>
+#include <__ranges/from_range.h>
+#include <__ranges/size.h>
 #include <__split_buffer>
 #include <__type_traits/is_allocator.h>
 #include <__type_traits/is_convertible.h>
 #include <__type_traits/is_same.h>
 #include <__type_traits/type_identity.h>
 #include <__utility/forward.h>
 #include <__utility/move.h>
+#include <__utility/pair.h>
 #include <__utility/swap.h>
 #include <limits>
 #include <stdexcept>
 #include <version>
 
 // standard-mandated includes
 
 // [iterator.range]
#endif
     }
 
     template <class _InputIter>
     _LIBCPP_HIDE_FROM_ABI deque(_InputIter __f, _InputIter __l,
               typename enable_if<__is_cpp17_input_iterator<_InputIter>::value>::type* = 0);
     template <class _InputIter>
     _LIBCPP_HIDE_FROM_ABI deque(_InputIter __f, _InputIter __l, const allocator_type& __a,
               typename enable_if<__is_cpp17_input_iterator<_InputIter>::value>::type* = 0);
+
+#if _LIBCPP_STD_VER >= 23
+  template <_ContainerCompatibleRange<_Tp> _Range>
+  _LIBCPP_HIDE_FROM_ABI deque(from_range_t, _Range&& __range,
+      const allocator_type& __a = allocator_type())
+    : __map_(__pointer_allocator(__a)), __start_(0), __size_(0, __a) {
+    if constexpr (ranges::forward_range<_Range> || ranges::sized_range<_Range>) {
+      __append_with_size(ranges::begin(__range), ranges::distance(__range));
+
+    } else {
+      for (auto&& __e : __range) {
+        emplace_back(std::forward<decltype(__e)>(__e));
+      }
+    }
+  }
+#endif
+
     _LIBCPP_HIDE_FROM_ABI deque(const deque& __c);
     _LIBCPP_HIDE_FROM_ABI deque(const deque& __c, const __type_identity_t<allocator_type>& __a);
 
     _LIBCPP_HIDE_FROM_ABI deque& operator=(const deque& __c);
 
 #ifndef _LIBCPP_CXX03_LANG
     _LIBCPP_HIDE_FROM_ABI deque(initializer_list<value_type> __il);
     _LIBCPP_HIDE_FROM_ABI deque(initializer_list<value_type> __il, const allocator_type& __a);
#endif // _LIBCPP_CXX03_LANG
 
     template <class _InputIter>
     _LIBCPP_HIDE_FROM_ABI void assign(_InputIter __f, _InputIter __l,
                     typename enable_if<__is_cpp17_input_iterator<_InputIter>::value &&
                                       !__is_cpp17_random_access_iterator<_InputIter>::value>::type* = 0);
     template <class _RAIter>
     _LIBCPP_HIDE_FROM_ABI void assign(_RAIter __f, _RAIter __l,
                     typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type* = 0);
+
+#if _LIBCPP_STD_VER >= 23
+    template <_ContainerCompatibleRange<_Tp> _Range>
+    _LIBCPP_HIDE_FROM_ABI
+    void assign_range(_Range&& __range) {
+      if constexpr (ranges::forward_range<_Range> || ranges::sized_range<_Range>) {
+        auto __n = static_cast<size_type>(ranges::distance(__range));
+        __assign_with_size(ranges::begin(__range), __n);
+
+      } else {
+        __assign_with_sentinel(ranges::begin(__range), ranges::end(__range));
+      }
+    }
+#endif
+
     _LIBCPP_HIDE_FROM_ABI void assign(size_type __n, const value_type& __v);
 
     _LIBCPP_HIDE_FROM_ABI
     allocator_type get_allocator() const _NOEXCEPT;
   _LIBCPP_HIDE_FROM_ABI allocator_type& __alloc() _NOEXCEPT { return __size_.second(); }
   _LIBCPP_HIDE_FROM_ABI const allocator_type& __alloc() const _NOEXCEPT { return __size_.second(); }
 
   // iterators:

 #else
     template <class... _Args> _LIBCPP_HIDE_FROM_ABI void      emplace_front(_Args&&... __args);
     template <class... _Args> _LIBCPP_HIDE_FROM_ABI void      emplace_back (_Args&&... __args);
 #endif
     template <class... _Args> _LIBCPP_HIDE_FROM_ABI iterator emplace(const_iterator __p, _Args&&... __args);
 
     _LIBCPP_HIDE_FROM_ABI void push_front(value_type&& __v);
     _LIBCPP_HIDE_FROM_ABI void push_back(value_type&& __v);
+
+#if _LIBCPP_STD_VER >= 23
+    template <_ContainerCompatibleRange<_Tp> _Range>
+    _LIBCPP_HIDE_FROM_ABI
+    void prepend_range(_Range&& __range) {
+      insert_range(begin(), std::forward<_Range>(__range));
+    }
+
+    template <_ContainerCompatibleRange<_Tp> _Range>
+    _LIBCPP_HIDE_FROM_ABI
+    void append_range(_Range&& __range) {
+      insert_range(end(), std::forward<_Range>(__range));
+    }
+#endif
+
     _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __v);
 
     _LIBCPP_HIDE_FROM_ABI
     iterator insert(const_iterator __p, initializer_list<value_type> __il)
         {return insert(__p, __il.begin(), __il.end());}
 #endif // _LIBCPP_CXX03_LANG
     _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __v);
     _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, size_type __n, const value_type& __v);
     template <class _InputIter>
     _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, _InputIter __f, _InputIter __l,
                          typename enable_if<__is_exactly_cpp17_input_iterator<_InputIter>::value>::type* = 0);
     template <class _ForwardIterator>
     _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, _ForwardIterator __f, _ForwardIterator __l,
                         typename enable_if<__is_exactly_cpp17_forward_iterator<_ForwardIterator>::value>::type* = 0);
     template <class _BiIter>
     _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, _BiIter __f, _BiIter __l,
                          typename enable_if<__is_cpp17_bidirectional_iterator<_BiIter>::value>::type* = 0);
 
+#if _LIBCPP_STD_VER >= 23
+    template <_ContainerCompatibleRange<_Tp> _Range>
+    _LIBCPP_HIDE_FROM_ABI
+    iterator insert_range(const_iterator __position, _Range&& __range) {
+      if constexpr (ranges::bidirectional_range<_Range>) {
+        auto __n = static_cast<size_type>(ranges::distance(__range));
+        return __insert_bidirectional(__position, ranges::begin(__range), ranges::end(__range), __n);
+
+      } else if constexpr (ranges::forward_range<_Range> || ranges::sized_range<_Range>) {
+        auto __n = static_cast<size_type>(ranges::distance(__range));
+        return __insert_with_size(__position, ranges::begin(__range), __n);
+
+      } else {
+        return __insert_with_sentinel(__position, ranges::begin(__range), ranges::end(__range));
+      }
+    }
+#endif
+
     _LIBCPP_HIDE_FROM_ABI void pop_front();
     _LIBCPP_HIDE_FROM_ABI void pop_back();
     _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p);
     _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __f, const_iterator __l);
 
     _LIBCPP_HIDE_FROM_ABI
     void swap(deque& __c)
 #if _LIBCPP_STD_VER >= 14
bool __maybe_remove_back_spare(bool __keep_one = true) {
         __alloc_traits::deallocate(__alloc(), __map_.back(),
                                    __block_size);
         __map_.pop_back();
         return true;
       }
       return false;
     }
 
+    template <class _Iterator, class _Sentinel>
+    _LIBCPP_HIDE_FROM_ABI
+    void __assign_with_sentinel(_Iterator __f, _Sentinel __l);
+
+    template <class _Iterator>
+    _LIBCPP_HIDE_FROM_ABI
+    void __assign_with_size(_Iterator __f, difference_type __n);
+
+    template <class _Iterator, class _Sentinel>
+    _LIBCPP_HIDE_FROM_ABI
+    iterator __insert_with_sentinel(const_iterator __p, _Iterator __f, _Sentinel __l);
+
+    template <class _Iterator>
+    _LIBCPP_HIDE_FROM_ABI
+    iterator __insert_with_size(const_iterator __p, _Iterator __f, size_type __n);
+
+    template <class _BiIter, class _Sentinel>
+    _LIBCPP_HIDE_FROM_ABI
+    iterator __insert_bidirectional(const_iterator __p, _BiIter __f, _Sentinel __sent, size_type __n);
+    template <class _BiIter>
+    _LIBCPP_HIDE_FROM_ABI
+    iterator __insert_bidirectional(const_iterator __p, _BiIter __f, _BiIter __l, size_type __n);
+
     template <class _InpIter>
     _LIBCPP_HIDE_FROM_ABI void __append(_InpIter __f, _InpIter __l,
                  typename enable_if<__is_exactly_cpp17_input_iterator<_InpIter>::value>::type* = 0);
     template <class _ForIter>
     _LIBCPP_HIDE_FROM_ABI void __append(_ForIter __f, _ForIter __l,
                       typename enable_if<__is_cpp17_forward_iterator<_ForIter>::value>::type* = 0);
+
+    template <class _InputIterator>
+    _LIBCPP_HIDE_FROM_ABI void __append_with_size(_InputIterator __from, size_type __n);
+    template <class _InputIterator, class _Sentinel>
+    _LIBCPP_HIDE_FROM_ABI void __append_with_sentinel(_InputIterator __f, _Sentinel __l);
+
     _LIBCPP_HIDE_FROM_ABI void __append(size_type __n);
     _LIBCPP_HIDE_FROM_ABI void __append(size_type __n, const value_type& __v);
     _LIBCPP_HIDE_FROM_ABI void __erase_to_end(const_iterator __f);
     _LIBCPP_HIDE_FROM_ABI void __add_front_capacity();
     _LIBCPP_HIDE_FROM_ABI void __add_front_capacity(size_type __n);
     _LIBCPP_HIDE_FROM_ABI void __add_back_capacity();
     _LIBCPP_HIDE_FROM_ABI void __add_back_capacity(size_type __n);
     _LIBCPP_HIDE_FROM_ABI iterator __move_and_check(iterator __f, iterator __l, iterator __r,
template<class _InputIterator,
          class _Alloc,
          class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>,
          class = enable_if_t<__is_allocator<_Alloc>::value>
          >
 deque(_InputIterator, _InputIterator, _Alloc)
   -> deque<__iter_value_type<_InputIterator>, _Alloc>;
 #endif
 
+#if _LIBCPP_STD_VER >= 23
+template <ranges::input_range _Range,
+          class _Alloc = allocator<ranges::range_value_t<_Range>>,
+          class = enable_if_t<__is_allocator<_Alloc>::value>
+          >
+deque(from_range_t, _Range&&, _Alloc = _Alloc())
+  -> deque<ranges::range_value_t<_Range>, _Alloc>;
+#endif
+
 template <class _Tp, class _Allocator>
 deque<_Tp, _Allocator>::deque(size_type __n)
     : __start_(0), __size_(0, __default_init_tag())
 {
     if (__n > 0)
         __append(__n);
 }
 

 
 template <class _Tp, class _Allocator>
 template <class _InputIter>
 void
 deque<_Tp, _Allocator>::assign(_InputIter __f, _InputIter __l,
                                typename enable_if<__is_cpp17_input_iterator<_InputIter>::value &&
                                                  !__is_cpp17_random_access_iterator<_InputIter>::value>::type*)
 {
+  __assign_with_sentinel(__f, __l);
+}
+
+template <class _Tp, class _Allocator>
+template <class _Iterator, class _Sentinel>
+_LIBCPP_HIDE_FROM_ABI
+void deque<_Tp, _Allocator>::__assign_with_sentinel(_Iterator __f, _Sentinel __l) {
     iterator __i = begin();
     iterator __e = end();
     for (; __f != __l && __i != __e; ++__f, (void) ++__i)
         *__i = *__f;
     if (__f != __l)
-        __append(__f, __l);
+        __append_with_sentinel(std::move(__f), std::move(__l));
     else
         __erase_to_end(__i);
 }
 
 template <class _Tp, class _Allocator>
 template <class _RAIter>
 void
 deque<_Tp, _Allocator>::assign(_RAIter __f, _RAIter __l,
                                typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type*)
 {
-    if (static_cast<size_type>(__l - __f) > size())
+  __assign_with_size(__f, __l - __f);
+}
+
+template <class _Tp, class _Allocator>
+template <class _Iterator>
+_LIBCPP_HIDE_FROM_ABI
+void deque<_Tp, _Allocator>::__assign_with_size(_Iterator __f, difference_type __n) {
+    if (static_cast<size_type>(__n) > size())
     {
-        _RAIter __m = __f + size();
-        _VSTD::copy(__f, __m, begin());
-        __append(__m, __l);
+        auto __rest = std::__copy_n<_ClassicAlgPolicy>(__f, size(), begin()).first;
+        __append_with_size(__rest, __n - size());
     }
     else
-        __erase_to_end(_VSTD::copy(__f, __l, begin()));
+        __erase_to_end(std::__copy_n<_ClassicAlgPolicy>(__f, __n, begin()).second);
 }
 
 template <class _Tp, class _Allocator>
 void
 deque<_Tp, _Allocator>::assign(size_type __n, const value_type& __v)
 {
     if (__n > size())
     {
         _VSTD::fill_n(begin(), size(), __v);
         __n -= size();
         __append(__n, __v);
     }
     else
         __erase_to_end(_VSTD::fill_n(begin(), __n, __v));
 }
 
 template <class _Tp, class _Allocator>
 inline
 _Allocator
 deque<_Tp, _Allocator>::get_allocator() const _NOEXCEPT
 {
     return __alloc();
 }
 
 template <class _Tp, class _Allocator>

 }
 
 template <class _Tp, class _Allocator>
 template <class _InputIter>
 typename deque<_Tp, _Allocator>::iterator
 deque<_Tp, _Allocator>::insert(const_iterator __p, _InputIter __f, _InputIter __l,
                                typename enable_if<__is_exactly_cpp17_input_iterator<_InputIter>::value>::type*)
 {
+  return __insert_with_sentinel(__p, __f, __l);
+}
+
+template <class _Tp, class _Allocator>
+template <class _Iterator, class _Sentinel>
+_LIBCPP_HIDE_FROM_ABI
+typename deque<_Tp, _Allocator>::iterator
+deque<_Tp, _Allocator>::__insert_with_sentinel(const_iterator __p, _Iterator __f, _Sentinel __l) {
     __split_buffer<value_type, allocator_type&> __buf(__alloc());
-    __buf.__construct_at_end(__f, __l);
+    __buf.__construct_at_end_with_sentinel(std::move(__f), std::move(__l));
     typedef typename __split_buffer<value_type, allocator_type&>::iterator __bi;
     return insert(__p, move_iterator<__bi>(__buf.begin()), move_iterator<__bi>(__buf.end()));
 }
 
 template <class _Tp, class _Allocator>
 template <class _ForwardIterator>
 typename deque<_Tp, _Allocator>::iterator
 deque<_Tp, _Allocator>::insert(const_iterator __p, _ForwardIterator __f, _ForwardIterator __l,
                                typename enable_if<__is_exactly_cpp17_forward_iterator<_ForwardIterator>::value>::type*)
 {
-    size_type __n = _VSTD::distance(__f, __l);
+  return __insert_with_size(__p, __f, std::distance(__f, __l));
+}
+
+template <class _Tp, class _Allocator>
+template <class _Iterator>
+_LIBCPP_HIDE_FROM_ABI
+typename deque<_Tp, _Allocator>::iterator
+deque<_Tp, _Allocator>::__insert_with_size(const_iterator __p, _Iterator __f, size_type __n) {
     __split_buffer<value_type, allocator_type&> __buf(__n, 0, __alloc());
-    __buf.__construct_at_end(__f, __l);
+    __buf.__construct_at_end_with_size(__f, __n);
     typedef typename __split_buffer<value_type, allocator_type&>::iterator __fwd;
     return insert(__p, move_iterator<__fwd>(__buf.begin()), move_iterator<__fwd>(__buf.end()));
 }
 
 template <class _Tp, class _Allocator>
 template <class _BiIter>
 typename deque<_Tp, _Allocator>::iterator
 deque<_Tp, _Allocator>::insert(const_iterator __p, _BiIter __f, _BiIter __l,
                                typename enable_if<__is_cpp17_bidirectional_iterator<_BiIter>::value>::type*)
 {
-    size_type __n = _VSTD::distance(__f, __l);
+  return __insert_bidirectional(__p, __f, __l, std::distance(__f, __l));
+}
+
+template <class _Tp, class _Allocator>
+template <class _BiIter, class _Sentinel>
+_LIBCPP_HIDE_FROM_ABI
+typename deque<_Tp, _Allocator>::iterator
+deque<_Tp, _Allocator>::__insert_bidirectional(const_iterator __p, _BiIter __f, _Sentinel, size_type __n) {
+  return __insert_bidirectional(__p, __f, std::next(__f, __n), __n);
+}
+
+template <class _Tp, class _Allocator>
+template <class _BiIter>
+_LIBCPP_HIDE_FROM_ABI
+typename deque<_Tp, _Allocator>::iterator
+deque<_Tp, _Allocator>::__insert_bidirectional(const_iterator __p, _BiIter __f, _BiIter __l, size_type __n) {
     size_type __pos = __p - begin();
     size_type __to_end = size() - __pos;
     allocator_type& __a = __alloc();
     if (__pos < __to_end)
     {   // insert by shifting things backward
         if (__n > __front_spare())
             __add_front_capacity(__n - __front_spare());
         // __n <= __front_spare()

 }
 
 template <class _Tp, class _Allocator>
 template <class _InpIter>
 void
 deque<_Tp, _Allocator>::__append(_InpIter __f, _InpIter __l,
                                  typename enable_if<__is_exactly_cpp17_input_iterator<_InpIter>::value>::type*)
 {
+  __append_with_sentinel(__f, __l);
+}
+
+template <class _Tp, class _Allocator>
+template <class _InputIterator, class _Sentinel>
+_LIBCPP_HIDE_FROM_ABI
+void deque<_Tp, _Allocator>::__append_with_sentinel(_InputIterator __f, _Sentinel __l) {
     for (; __f != __l; ++__f)
 #ifdef _LIBCPP_CXX03_LANG
         push_back(*__f);
 #else
         emplace_back(*__f);
 #endif
 }
 
 template <class _Tp, class _Allocator>
 template <class _ForIter>
 void
 deque<_Tp, _Allocator>::__append(_ForIter __f, _ForIter __l,
                                  typename enable_if<__is_cpp17_forward_iterator<_ForIter>::value>::type*)
 {
-    size_type __n = _VSTD::distance(__f, __l);
+    __append_with_size(__f, std::distance(__f, __l));
+}
+
+template <class _Tp, class _Allocator>
+template <class _InputIterator>
+_LIBCPP_HIDE_FROM_ABI
+void deque<_Tp, _Allocator>::__append_with_size(_InputIterator __f, size_type __n) {
     allocator_type& __a = __alloc();
     size_type __back_capacity = __back_spare();
     if (__n > __back_capacity)
         __add_back_capacity(__n - __back_capacity);
+
     // __n <= __back_capacity
     for (__deque_block_range __br : __deque_range(end(), end() + __n)) {
       _ConstructTransaction __tx(this, __br);
       for (; __tx.__pos_ != __tx.__end_; ++__tx.__pos_, (void)++__f) {
         __alloc_traits::construct(__a, _VSTD::__to_address(__tx.__pos_), *__f);
       }
     }
 }

libcxx/test/std/containers/sequences/deque/deque.cons/deduct.pass.cpp

 //===----------------------------------------------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
 // <deque>
 // UNSUPPORTED: c++03, c++11, c++14
 
 // template <class InputIterator, class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
 //    deque(InputIterator, InputIterator, Allocator = Allocator())
 //    -> deque<typename iterator_traits<InputIterator>::value_type, Allocator>;
 //
+// template<ranges::input_range R, class Allocator = allocator<ranges::range_value_t<R>>>
+//   deque(from_range_t, R&&, Allocator = Allocator())
+//     -> deque<ranges::range_value_t<R>, Allocator>; // C++23
 
-#include <deque>
-#include <iterator>
+#include <array>
 #include <cassert>
-#include <cstddef>
 #include <climits> // INT_MAX
+#include <cstddef>
+#include <deque>
+#include <iterator>
 
 #include "deduction_guides_sfinae_checks.h"
 #include "test_macros.h"
 #include "test_iterators.h"
 #include "test_allocator.h"
 
 struct A {};
 
assert(deq.size() == 0);
 
         {
         std::deque<short, Alloc> source;
         std::deque deq(std::move(source), ConvertibleToAlloc(2));
         static_assert(std::is_same_v<decltype(deq), decltype(source)>);
         }
     }
 
+#if TEST_STD_VER >= 23
+    {
+      {
+        std::deque c(std::from_range, std::array<int, 0>());
+        static_assert(std::is_same_v<decltype(c), std::deque<int>>);
+      }
+
+      {
+        using Alloc = test_allocator<int>;
+        std::deque c(std::from_range, std::array<int, 0>(), Alloc());
+        static_assert(std::is_same_v<decltype(c), std::deque<int, Alloc>>);
+      }
+    }
+#endif
+
     SequenceContainerDeductionGuidesSfinaeAway<std::deque, std::deque<int>>();
 
     return 0;
 }

libcxx/test/std/containers/sequences/deque/deque.cons/from_range.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17, c++20
+
+#include <deque>
+
+#include "../../from_range_sequence_containers.h"
+#include "test_macros.h"
+
+// template<container-compatible-range<T> R>
+//   deque(from_range_t, R&& rg, const Allocator& = Allocator()); // C++23
+
+int main(int, char**) {
+  for_all_iterators_and_allocators<int>([]<class Iter, class Sent, class Alloc>() {
+    test_sequence_container<std::deque, int, Iter, Sent, Alloc>([](const auto& c) {
+      LIBCPP_ASSERT(c.__invariants());
+    });
+  });
+  test_sequence_container_move_only<std::deque>();
+
+  static_assert(test_constraints<std::deque, int, double>());
+
+  // TODO(varconst): `deque`'s constructors currently aren't exception-safe.
+  // See https://github.com/llvm/llvm-project/issues/62056.
+  //test_exception_safety_throwing_copy<std::deque>();
+  //test_exception_safety_throwing_allocator<std::deque, int>();
+
+  return 0;
+}

libcxx/test/std/containers/sequences/deque/deque.modifiers/append_range.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17, c++20
+
+// template<container-compatible-range<T> R>
+//   constexpr void append_range(R&& rg); // C++23
+
+#include <deque>
+
+#include "../../insert_range_sequence_containers.h"
+#include "test_macros.h"
+
+// Tested cases:
+// - different kinds of insertions (appending an {empty/one-element/mid-sized/long range} into an
+//   {empty/one-element/full} container);
+// - appending move-only elements;
+// - an exception is thrown when copying the elements or when allocating new elements.
+int main(int, char**) {
+  static_assert(test_constraints_append_range<std::deque, int, double>());
+
+  for_all_iterators_and_allocators<int, const int*>([]<class Iter, class Sent, class Alloc>() {
+    test_sequence_append_range<std::deque<int, Alloc>, Iter, Sent>([](auto&& c) {
+      LIBCPP_ASSERT(c.__invariants());
+    });
+  });
+  test_sequence_append_range_move_only<std::deque>();
+
+  test_append_range_exception_safety_throwing_copy<std::deque>();
+  test_append_range_exception_safety_throwing_allocator<std::deque, int>();
+
+  return 0;
+}

libcxx/test/std/containers/sequences/deque/deque.modifiers/assign_range.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17, c++20
+
+// template<container-compatible-range<T> R>
+//   constexpr void assign_range(R&& rg); // C++23
+
+#include <deque>
+
+#include "../../insert_range_sequence_containers.h"
+#include "test_macros.h"
+
+// Tested cases:
+// - different kinds of assignments (assigning an {empty/one-element/mid-sized/long range} to an
+//   {empty/one-element/full} container);
+// - assigning move-only elements;
+// - an exception is thrown when copying the elements or when allocating new elements.
+int main(int, char**) {
+  static_assert(test_constraints_assign_range<std::deque, int, double>());
+
+  for_all_iterators_and_allocators<int, const int*>([]<class Iter, class Sent, class Alloc>() {
+    test_sequence_assign_range<std::deque<int, Alloc>, Iter, Sent>([](auto&& c) {
+      LIBCPP_ASSERT(c.__invariants());
+    });
+  });
+  test_sequence_assign_range_move_only<std::deque>();
+
+  test_assign_range_exception_safety_throwing_copy<std::deque>();
+  test_assign_range_exception_safety_throwing_allocator<std::deque, int>();
+
+  return 0;
+}

libcxx/test/std/containers/sequences/deque/deque.modifiers/insert_range.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17, c++20
+
+// template<container-compatible-range<T> R>
+//   constexpr iterator insert_range(const_iterator position, R&& rg); // C++23
+
+#include <deque>
+
+#include "../../insert_range_sequence_containers.h"
+#include "test_macros.h"
+
+// Tested cases:
+// - different kinds of insertions (inserting an {empty/one-element/mid-sized/long range} into an
+//   {empty/one-element/full} container at the {beginning/middle/end});
+// - inserting move-only elements;
+// - an exception is thrown when copying the elements or when allocating new elements.
+int main(int, char**) {
+  static_assert(test_constraints_insert_range<std::deque, int, double>());
+
+  for_all_iterators_and_allocators<int, const int*>([]<class Iter, class Sent, class Alloc>() {
+    test_sequence_insert_range<std::deque<int, Alloc>, Iter, Sent>([](auto&& c) {
+      LIBCPP_ASSERT(c.__invariants());
+    });
+  });
+  test_sequence_insert_range_move_only<std::deque>();
+
+  test_insert_range_exception_safety_throwing_copy<std::deque>();
+  test_insert_range_exception_safety_throwing_allocator<std::deque, int>();
+
+  return 0;
+}

libcxx/test/std/containers/sequences/deque/deque.modifiers/prepend_range.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17, c++20
+
+// template<container-compatible-range<T> R>
+//   constexpr void prepend_range(R&& rg); // C++23
+
+#include <deque>
+
+#include "../../insert_range_sequence_containers.h"
+#include "test_macros.h"
+
+// Tested cases:
+// - different kinds of insertions (prepending an {empty/one-element/mid-sized/long range} into an
+//   {empty/one-element/full} container);
+// - prepending move-only elements;
+// - an exception is thrown when copying the elements or when allocating new elements.
+int main(int, char**) {
+  static_assert(test_constraints_prepend_range<std::deque, int, double>());
+
+  for_all_iterators_and_allocators<int, const int*>([]<class Iter, class Sent, class Alloc>() {
+    test_sequence_prepend_range<std::deque<int, Alloc>, Iter, Sent>([](auto&& c) {
+      LIBCPP_ASSERT(c.__invariants());
+    });
+  });
+  test_sequence_prepend_range_move_only<std::deque>();
+
+  test_prepend_range_exception_safety_throwing_copy<std::deque>();
+  test_prepend_range_exception_safety_throwing_allocator<std::deque, int>();
+
+  return 0;
+}