[libc++] Implement the deque functions of P1206R7

[Mordante]

Thanks for working on this. I did a shallow review and hope to find time for a more in depth review at another time.

libcxx/include/CMakeLists.txt

195

Can you update the C++2b status page with the status |Partial| and add a note which section is implemented.
(I guess a full status page is a bit overkill.)

libcxx/include/__concepts/container_compatible_range.h

24

s/_Type/_Tp

libcxx/include/__ranges/from_range_t.h

22

Please update the appropriate synopsis.

24

I don't see any tests for this trivial public type.

libcxx/include/deque

14

Please update the synopsis.

1391

When the range is a temporary are we allowed to move the elements from the range instead?

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

15

Can we add some test validating that ranges not passing the concept __container_compatible_range are rejected? For example an output range?

47

http://eel.is/c++draft/sequence.reqmts#12 requires Cpp17MoveInsertable, please validates this works. (Based on earlier observations I expect it to fail).

48

Can you also test the complexity requirements.

[ldionne]

This is an awesome patch! I think there's a bunch of stuff that needs to be investigated per our live review just now, but we will all end up with a better understanding of how deque works so that's great.

libcxx/include/__algorithm/iterator_operations.h

47

I think you'll find that you don't need this anymore once you rebase.

libcxx/include/__ranges/from_range_t.h

18

This will soon not be useful anymore, but I think we should do it for consistency.

libcxx/include/__split_buffer

121–126

I think we should make those _LIBCPP_HIDE_FROM_ABI. Especially since we're modifying them in a way that might not be backwards compatible if this had leaked into a user's ABI.

libcxx/include/deque

1339

&& _LIBCPP_HAS_NO_INCOMPLETE_RANGES, here and elsewhere. We'll bulk-remove those in the future.

1385–1394

We could factor something out here, it seems like a potentially useful algorithm to me (in fact I thought the stdlib already had this algorithm):

template <class _Iter1, class _Sent1, class _Iter2, class _Sent2>
std::pair<_Iter1, _Iter2> __copy_shortest(_Iter1 __it1, _Sent1 __sent1, _Iter2 __it2, _Sent2 __sent2) {
    while (__first1 != __sent1 && __first2 != __sent2) {
      *__first2 = *__first1;
      ++__first1;
      ++__first2;
    }
    return {__first1, __first2};
}

And in fact, we can optimize the above for sized_sentinels, which would get rid of the need for the overload of assign_range we have below. And that would not add as many new dependencies to <deque> (views::take and friends).

---

Alternatively, per our live discussion, if you want to keep only the overload below (with the removed sized_range constraint), I'd be OK with that, BUT:

1. We need to show that there is no significant compile-time impact to existing users of <deque>. In particular, if we end up pulling in a significant part of <ranges> just to implement this function, that doesn't work.

2. We need to show that the code generated is comparable to what I suggested above (and if we added an optimization for sized sentinels that basically lowered to std::copy aka memmove). If that's not the case, then we should use the lower-level version, and also file a bug against Clang so we can find ways to improve the codegen of ranges. Note that this exercise it useful on its own.

Yeah, sorry, I know I'm a pain but I think the bar for using higher-level and more complicated constructs from lower-level ones should be high, and that's what I'm enforcing here.

1410

Any reason for not using this? IMO it's strictly clearer and it skips one level of indirection through ranges::distance if we already have a sized_range. And if we don't have a sized_range, we definitely don't want to be calling ranges::distance over it!

1511

1516–1517

When you have a sized_range, we should be able to use std::uninitialized_allocator_copy here with __deque_iterator, and update the size at the end only. When we don't have a sized_range, the for loop with emplace_back seems like the best we can do.

Also, can you file a bug report to track creating a high-level libc++-internal abstraction for chunked iterators? Ideally, we should be able to generalize the overloads of std::copy & friends we have at the top of this file, and also use std::uninitialized_allocator_copy here, and have it do just the right thing. Then, once we use that abstraction in uninitialized_allocator_copy, we'd get improved perf for free.

1524

1529–1538

I think you should be checking for a sized_range before you check for a bidirectional_range.

1539

You are missing a <vector> include here, and I must admit that makes me frown.

This also leads me to think that you should instead use __split_buffer here, that seems like the class used in both vector and deque to do these things. Furthermore, it should be possible in theory to instead do this:

1. Allocate a buffer and append the elements to it
2. Link that buffer to the beginning of the deque directly, to avoid having to reallocate and copy elements twice
3. Copy just the n elements at the end of that buffer to the original beginning of the deque.

As you go through this exercise, it might be useful to take some notes about how the data structure works and we can promote them to documentation in the future.

1582

1585

I have the same kind of hunch as above here -- why can't we reuse the buffer we just allocated, at least in part?

1742

libcxx/include/CMakeLists.txt

set(files
   __compare/weak_order.h
   __concepts/arithmetic.h
   __concepts/assignable.h
   __concepts/boolean_testable.h
   __concepts/class_or_enum.h
   __concepts/common_reference_with.h
   __concepts/common_with.h
   __concepts/constructible.h
+  __concepts/container_compatible_range.h
   __concepts/convertible_to.h
   __concepts/copyable.h
   __concepts/derived_from.h
   __concepts/destructible.h
   __concepts/different_from.h
   __concepts/equality_comparable.h
   __concepts/invocable.h
   __concepts/movable.h
set(files
   __ranges/dangling.h
   __ranges/data.h
   __ranges/drop_view.h
   __ranges/empty.h
   __ranges/empty_view.h
   __ranges/enable_borrowed_range.h
   __ranges/enable_view.h
   __ranges/filter_view.h
+  __ranges/from_range_t.h
   __ranges/iota_view.h
   __ranges/join_view.h
   __ranges/lazy_split_view.h
   __ranges/non_propagating_cache.h
   __ranges/owning_view.h
   __ranges/range_adaptor.h
   __ranges/rbegin.h
   __ranges/ref_view.h

libcxx/include/__algorithm/iterator_operations.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___ALGORIHTM_ITERATOR_OPERATIONS_H
 #define _LIBCPP___ALGORIHTM_ITERATOR_OPERATIONS_H
 
 #include <__config>
 #include <__iterator/advance.h>
 #include <__iterator/distance.h>
 #include <__iterator/iterator_traits.h>
+#include <__iterator/next.h>
+#include <__iterator/prev.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 #if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
 struct _RangesIterOps {
   static constexpr auto advance = ranges::advance;
   static constexpr auto distance = ranges::distance;
+  static constexpr auto next = ranges::next;
+  static constexpr auto prev = ranges::prev;
 };
 #endif
 
 struct _StdIterOps {
 
   template <class _Iterator, class _Distance>
   _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_AFTER_CXX11 void advance(_Iterator& __iter, _Distance __count) {
     return std::advance(__iter, __count);
   }
 
   template <class _Iterator>
   _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_AFTER_CXX11
   typename iterator_traits<_Iterator>::difference_type distance(_Iterator __first, _Iterator __last) {
     return std::distance(__first, __last);
   }
 
+  template <class _Iterator>
+  _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_AFTER_CXX11
+  _Iterator next(_Iterator __x, typename iterator_traits<_Iterator>::difference_type __n) {
+    return std::next(__x, __n);
+  }
+
+  template <class _Iterator>
+  _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_AFTER_CXX11
+  _Iterator next(_Iterator, _Iterator __last) {
+    return __last;
+  }
+
+  template <class _Iterator>
+  _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_AFTER_CXX11
+  _Iterator prev(_Iterator __iter, typename iterator_traits<_Iterator>::difference_type __n) {
+    return std::prev(__iter, __n);
+  }
 };
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORIHTM_ITERATOR_OPERATIONS_H

libcxx/include/__concepts/container_compatible_range.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___CONCEPTS_CONTAINER_COMPATIBLE_RANGE_H
+#define _LIBCPP___CONCEPTS_CONTAINER_COMPATIBLE_RANGE_H
+
+#include <__concepts/convertible_to.h>
+#include <__config>
+#include <__ranges/concepts.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+#if _LIBCPP_STD_VER > 20
+
+template <class _Range, class _Type>
+concept __container_compatible_range =
+    ranges::input_range<_Range> && convertible_to<ranges::range_reference_t<_Range>, _Type>;
+
+#endif // _LIBCPP_STD_VER > 20
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP___CONCEPTS_CONTAINER_COMPATIBLE_RANGE_H

libcxx/include/__ranges/from_range_t.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___RANGES_FROM_RANGE_T_H
+#define _LIBCPP___RANGES_FROM_RANGE_T_H
+
+#include <__config>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+#if _LIBCPP_STD_VER > 20
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+struct from_range_t {
+  explicit from_range_t() = default;
+};
+
+inline constexpr from_range_t from_range{};
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP_STD_VER > 20
+
+#endif // _LIBCPP___RANGES_FROM_RANGE_T_H

libcxx/include/__split_buffer

public:
     template <class... _Args>
         void emplace_back(_Args&&... __args);
 
     _LIBCPP_INLINE_VISIBILITY void pop_front() {__destruct_at_begin(__begin_+1);}
     _LIBCPP_INLINE_VISIBILITY void pop_back() {__destruct_at_end(__end_-1);}
 
     void __construct_at_end(size_type __n);
     void __construct_at_end(size_type __n, const_reference __x);
-    template <class _InputIter>
+    template <class _InputIter, class _Sent>
     __enable_if_t<__is_exactly_cpp17_input_iterator<_InputIter>::value>
-        __construct_at_end(_InputIter __first, _InputIter __last);
-    template <class _ForwardIterator>
+        __construct_at_end(_InputIter __first, _Sent __last);
+    template <class _ForwardIterator, class _Sent>
     __enable_if_t<__is_cpp17_forward_iterator<_ForwardIterator>::value>
-        __construct_at_end(_ForwardIterator __first, _ForwardIterator __last);
+        __construct_at_end(_ForwardIterator __first, _Sent __last);
 
     _LIBCPP_INLINE_VISIBILITY void __destruct_at_begin(pointer __new_begin)
         {__destruct_at_begin(__new_begin, is_trivially_destructible<value_type>());}
         _LIBCPP_INLINE_VISIBILITY
         void __destruct_at_begin(pointer __new_begin, false_type);
         _LIBCPP_INLINE_VISIBILITY
         void __destruct_at_begin(pointer __new_begin, true_type);
 
__split_buffer<_Tp, _Allocator>::__construct_at_end(size_type __n, const_reference __x)
     _ConstructTransaction __tx(&this->__end_, __n);
     for (; __tx.__pos_ != __tx.__end_; ++__tx.__pos_) {
         __alloc_traits::construct(this->__alloc(),
             _VSTD::__to_address(__tx.__pos_), __x);
     }
 }
 
 template <class _Tp, class _Allocator>
-template <class _InputIter>
+template <class _InputIter, class _Sent>
 __enable_if_t<__is_exactly_cpp17_input_iterator<_InputIter>::value>
-__split_buffer<_Tp, _Allocator>::__construct_at_end(_InputIter __first, _InputIter __last)
+__split_buffer<_Tp, _Allocator>::__construct_at_end(_InputIter __first, _Sent __last)
 {
     __alloc_rr& __a = this->__alloc();
     for (; __first != __last; ++__first)
     {
         if (__end_ == __end_cap())
         {
             size_type __old_cap = __end_cap() - __first_;
             size_type __new_cap = _VSTD::max<size_type>(2 * __old_cap, 8);
             __split_buffer __buf(__new_cap, 0, __a);
             for (pointer __p = __begin_; __p != __end_; ++__p, (void) ++__buf.__end_)
                 __alloc_traits::construct(__buf.__alloc(),
                         _VSTD::__to_address(__buf.__end_), _VSTD::move(*__p));
             swap(__buf);
         }
         __alloc_traits::construct(__a, _VSTD::__to_address(this->__end_), *__first);
         ++this->__end_;
     }
 }
 
 template <class _Tp, class _Allocator>
-template <class _ForwardIterator>
+template <class _ForwardIterator, class _Sent>
 __enable_if_t<__is_cpp17_forward_iterator<_ForwardIterator>::value>
-__split_buffer<_Tp, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last)
+__split_buffer<_Tp, _Allocator>::__construct_at_end(_ForwardIterator __first, _Sent __last)
 {
     _ConstructTransaction __tx(&this->__end_, _VSTD::distance(__first, __last));
     for (; __tx.__pos_ != __tx.__end_; ++__tx.__pos_, (void) ++__first) {
         __alloc_traits::construct(this->__alloc(),
             _VSTD::__to_address(__tx.__pos_), *__first);
     }
 }
 

libcxx/include/deque

 // -*- 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_DEQUE
 #define _LIBCPP_DEQUE
 
 /*
     deque synopsis
 
 namespace std
 {
 
 template <class T, class Allocator = allocator<T> >
 class deque
 {
 public:

 }  // std
 
 */
 
 #include <__algorithm/copy.h>
 #include <__algorithm/copy_backward.h>
 #include <__algorithm/equal.h>
 #include <__algorithm/fill_n.h>
+#include <__algorithm/iterator_operations.h>
 #include <__algorithm/lexicographical_compare.h>
 #include <__algorithm/min.h>
+#include <__algorithm/ranges_copy.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 <__concepts/container_compatible_range.h>
 #include <__config>
 #include <__format/enable_insertable.h>
 #include <__iterator/iterator_traits.h>
 #include <__iterator/next.h>
 #include <__iterator/prev.h>
 #include <__iterator/reverse_iterator.h>
+#include <__ranges/access.h>
+#include <__ranges/from_range_t.h>
+#include <__ranges/reverse_view.h>
+#include <__ranges/take_view.h>
+#include <__ranges/views.h>
 #include <__split_buffer>
 #include <__utility/forward.h>
 #include <__utility/move.h>
 #include <__utility/swap.h>
 #include <limits>
 #include <stdexcept>
 #include <type_traits>
 #include <version>
#endif
     }
 
     template <class _InputIter>
         deque(_InputIter __f, _InputIter __l,
               typename enable_if<__is_cpp17_input_iterator<_InputIter>::value>::type* = 0);
     template <class _InputIter>
         deque(_InputIter __f, _InputIter __l, const allocator_type& __a,
               typename enable_if<__is_cpp17_input_iterator<_InputIter>::value>::type* = 0);
+
+#if _LIBCPP_STD_VER > 20
+
+  template <__container_compatible_range<_Tp> _Range>
+  _LIBCPP_HIDE_FROM_ABI deque(from_range_t, _Range&& __range, const _Allocator& __alloc = _Allocator()) : __base(__alloc) {
+    append_range(__range);
+  }
+
+#endif
+
     deque(const deque& __c);
     deque(const deque& __c, const __type_identity_t<allocator_type>& __a);
 
     deque& operator=(const deque& __c);
 
 #ifndef _LIBCPP_CXX03_LANG
     deque(initializer_list<value_type> __il);
     deque(initializer_list<value_type> __il, const allocator_type& __a);
#endif // _LIBCPP_CXX03_LANG
 
     template <class _InputIter>
         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>
         void assign(_RAIter __f, _RAIter __l,
                     typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type* = 0);
+
+#if _LIBCPP_STD_VER > 20
+
+  template <__container_compatible_range<_Tp> _Range>
+  _LIBCPP_HIDE_FROM_ABI void assign_range(_Range&& __range) {
+    auto __first1 = ranges::begin(__range);
+    auto __last1  = ranges::end(__range);
+    auto __first2 = begin();
+    auto __last2  = end();
+
+    while (__first1 != __last1 && __first2 != __last2) {
+      *__first2 = *__first1;
+      ++__first1;
+      ++__first2;
+    }
+
+    if (__first1 != __last1) {
+      for (; __first1 != __last1; ++__first1)
+        emplace_back(*__first1);
+    } else {
+      __erase_to_end(__first2);
+    }
+  }
+
+  template <__container_compatible_range<_Tp> _Range>
+    requires ranges::sized_range<_Range>
+  _LIBCPP_HIDE_FROM_ABI void assign_range(_Range&& __range) {
+    auto __it = ranges::copy(__range | views::take(size()), begin());
+    if (__it.in != ranges::end(__range)) {
+      if constexpr (ranges::sized_range<_Range>) {
+        append_range(ranges::subrange(__it.in.base(), ranges::end(__range), ranges::distance(__range) - size()));
+      } else {
+        append_range(ranges::subrange(__it.in.base(), ranges::end(__range)));
+      }
+    } else {
+      __erase_to_end(__it.out);
+    }
+  }
+
+#endif // _LIBCPP_STD_VER > 20
+
     void assign(size_type __n, const value_type& __v);
 
     _LIBCPP_INLINE_VISIBILITY
     allocator_type get_allocator() const _NOEXCEPT;
 
     // iterators:
 
     _LIBCPP_INLINE_VISIBILITY

 #ifndef _LIBCPP_CXX03_LANG
 #if _LIBCPP_STD_VER > 14
     template <class... _Args> reference emplace_front(_Args&&... __args);
     template <class... _Args> reference emplace_back (_Args&&... __args);
 #else
     template <class... _Args> void      emplace_front(_Args&&... __args);
     template <class... _Args> void      emplace_back (_Args&&... __args);
 #endif
+
+#if _LIBCPP_STD_VER > 20
+  template <__container_compatible_range<_Tp> _Range>
+  _LIBCPP_HIDE_FROM_ABI void append_range(_Range&& __range) {
+    if constexpr (ranges::sized_range<_Range>) {
+      auto __n        = ranges::distance(__range);
+      auto __back_cap = __back_spare();
+      if (__n > difference_type(__back_cap))
+        __add_back_capacity(__n - __back_cap);
+    }
+    for (auto&& __e : __range)
+      emplace_back(std::forward<decltype(__e)>(__e));
+  }
+
+  template <__container_compatible_range<_Tp> _Range>
+  _LIBCPP_HIDE_FROM_ABI void prepend_range(_Range&& __range) {
+    if constexpr (ranges::sized_range<_Range>) {
+      auto __front_cap = __front_spare();
+      auto __dist      = ranges::distance(__range);
+      if (difference_type(__front_cap) < __dist)
+        __add_front_capacity(__dist - __front_cap);
+    }
+
+    if constexpr (ranges::bidirectional_range<_Range>) {
+      for (auto&& __e : __range | views::reverse)
+        push_front(std::forward<decltype(__e)>(__e));
+    } else if constexpr (ranges::sized_range<_Range>) {
+      auto __dist = ranges::distance(__range);
+      std::__uninitialized_allocator_copy(
+          get_allocator(), ranges::begin(__range), ranges::end(__range), begin() - __dist);
+      __base::__start_ -= __dist;
+      __base::size() += __dist;
+    } else {
+      vector<value_type, allocator_type> __buf(get_allocator());
+      for (auto&& __e : __range)
+        __buf.emplace_back(std::forward<decltype(__e)>(__e));
+      prepend_range(__buf);
+    }
+  }
+#endif // _LIBCPP_STD_VER > 20
+
     template <class... _Args> iterator emplace(const_iterator __p, _Args&&... __args);
 
     void push_front(value_type&& __v);
     void push_back(value_type&& __v);
     iterator insert(const_iterator __p, value_type&& __v);
 
     _LIBCPP_INLINE_VISIBILITY
     iterator insert(const_iterator __p, initializer_list<value_type> __il)
         {return insert(__p, __il.begin(), __il.end());}
 #endif // _LIBCPP_CXX03_LANG
     iterator insert(const_iterator __p, const value_type& __v);
     iterator insert(const_iterator __p, size_type __n, const value_type& __v);
     template <class _InputIter>
         iterator insert(const_iterator __p, _InputIter __f, _InputIter __l,
                          typename enable_if<__is_cpp17_input_iterator<_InputIter>::value
                                          &&!__is_cpp17_forward_iterator<_InputIter>::value>::type* = 0);
     template <class _ForwardIterator>
         iterator insert(const_iterator __p, _ForwardIterator __f, _ForwardIterator __l,
                                typename enable_if<__is_cpp17_forward_iterator<_ForwardIterator>::value
                                          &&!__is_cpp17_bidirectional_iterator<_ForwardIterator>::value>::type* = 0);
     template <class _BiIter>
         iterator insert(const_iterator __p, _BiIter __f, _BiIter __l,
-                         typename enable_if<__is_cpp17_bidirectional_iterator<_BiIter>::value>::type* = 0);
+                         typename enable_if<__is_cpp17_bidirectional_iterator<_BiIter>::value>::type* = 0) {
+      return __insert<_StdIterOps>(__p, __f, __l);
+    }
+
+  template <class _IterOps, class _Iter, class _Sent>
+  _LIBCPP_HIDE_FROM_ABI iterator __insert(const_iterator __p, _Iter __f, _Sent __l);
+
+#if _LIBCPP_STD_VER > 20
+
+  template <__container_compatible_range<_Tp> _Range>
+  iterator insert_range(const_iterator __position, _Range&& __range) {
+    size_type __n = 0;
+    if constexpr (ranges::sized_range<_Range>)
+      __n = ranges::distance(__range);
+    __split_buffer<value_type, allocator_type&> __buf(__n, 0, get_allocator());
+    __buf.__construct_at_end(ranges::begin(__range), ranges::end(__range));
+    return __insert(__position, move_iterator(__buf.begin()), move_iterator(__buf.end()));
+  }
+
+  template <__container_compatible_range<_Tp> _Range> requires ranges::bidirectional_range<_Range>
+  iterator insert_range(const_iterator __position, _Range&& __range) {
+    return __insert<_RangesIterOps>(__position, ranges::begin(__range), ranges::end(__range));
+  }
+
+#endif // _LIBCPP_STD_VER > 20
 
     void pop_front();
     void pop_back();
     iterator erase(const_iterator __p);
     iterator erase(const_iterator __f, const_iterator __l);
 
     _LIBCPP_INLINE_VISIBILITY
     void swap(deque& __c)
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 > 20
+
+template <ranges::input_range _Range, class _Allocator = allocator<ranges::range_value_t<_Range>>>
+deque(from_range_t, _Range&&, _Allocator = _Allocator()) -> deque<ranges::range_value_t<_Range>, _Allocator>;
+
+#endif // _LIBCPP_STD_VER > 20
+
 template <class _Tp, class _Allocator>
 deque<_Tp, _Allocator>::deque(size_type __n)
 {
     if (__n > 0)
         __append(__n);
 }
 
 #if _LIBCPP_STD_VER > 11
deque<_Tp, _Allocator>::insert(const_iterator __p, _ForwardIterator __f, _ForwardIterator __l,
     size_type __n = _VSTD::distance(__f, __l);
     __split_buffer<value_type, allocator_type&> __buf(__n, 0, __base::__alloc());
     __buf.__construct_at_end(__f, __l);
     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*)
+template <class _IterOps, class _Iter, class _Sent>
+_LIBCPP_HIDE_FROM_ABI typename deque<_Tp, _Allocator>::iterator
+deque<_Tp, _Allocator>::__insert(const_iterator __p, _Iter __f, _Sent __last)
 {
-    size_type __n = _VSTD::distance(__f, __l);
+    auto __l = _IterOps::next(__f, __last);
+    size_type __n = _IterOps::distance(__f, __l);
     size_type __pos = __p - __base::begin();
     size_type __to_end = __base::size() - __pos;
     allocator_type& __a = __base::__alloc();
     if (__pos < __to_end)
     {   // insert by shifting things backward
         if (__n > __front_spare())
             __add_front_capacity(__n - __front_spare());
         // __n <= __front_spare()
         iterator __old_begin = __base::begin();
         iterator __i = __old_begin;
-        _BiIter __m = __f;
+        _Iter __m = __f;
         if (__n > __pos)
         {
-            __m = __pos < __n / 2 ? _VSTD::prev(__l, __pos) : _VSTD::next(__f, __n - __pos);
-            for (_BiIter __j = __m; __j != __f; --__base::__start_, ++__base::size())
+            __m = __pos < __n / 2 ? _IterOps::prev(__l, __pos) : _IterOps::next(__f, __n - __pos);
+            for (_Iter __j = __m; __j != __f; --__base::__start_, ++__base::size())
                 __alloc_traits::construct(__a, _VSTD::addressof(*--__i), *--__j);
             __n = __pos;
         }
         if (__n > 0)
         {
             iterator __obn = __old_begin + __n;
             for (iterator __j = __obn; __j != __old_begin;)
             {
                 __alloc_traits::construct(__a, _VSTD::addressof(*--__i), _VSTD::move(*--__j));
                 --__base::__start_;
                 ++__base::size();
             }
             if (__n < __pos)
-                __old_begin = _VSTD::move(__obn, __old_begin + __pos, __old_begin);
-            _VSTD::copy(__m, __l, __old_begin);
+                __old_begin = std::__move(__obn, __old_begin + __pos, __old_begin);
+            std::__copy(__m, __l, __old_begin);
         }
     }
     else
     {   // insert by shifting things forward
         size_type __back_capacity = __back_spare();
         if (__n > __back_capacity)
             __add_back_capacity(__n - __back_capacity);
         // __n <= __back_capacity
         iterator __old_end = __base::end();
         iterator __i = __old_end;
-        _BiIter __m = __l;
+        _Iter __m = __l;
         size_type __de = __base::size() - __pos;
         if (__n > __de)
         {
-            __m = __de < __n / 2 ? _VSTD::next(__f, __de) : _VSTD::prev(__l, __n - __de);
-            for (_BiIter __j = __m; __j != __l; ++__i, (void) ++__j, ++__base::size())
+            __m = __de < __n / 2 ? _IterOps::next(__f, __de) : _IterOps::prev(__l, __n - __de);
+            for (_Iter __j = __m; __j != __l; ++__i, (void) ++__j, ++__base::size())
                 __alloc_traits::construct(__a, _VSTD::addressof(*__i), *__j);
             __n = __de;
         }
         if (__n > 0)
         {
             iterator __oen = __old_end - __n;
             for (iterator __j = __oen; __j != __old_end; ++__i, (void) ++__j, ++__base::size())
                 __alloc_traits::construct(__a, _VSTD::addressof(*__i), _VSTD::move(*__j));
             if (__n < __de)
-                __old_end = _VSTD::move_backward(__old_end - __de, __oen, __old_end);
-            _VSTD::copy_backward(__f, __m, __old_end);
+                __old_end = std::__move_backward(__old_end - __de, __oen, __old_end);
+            std::__copy_backward(__f, __m, __old_end);
         }
     }
     return __base::begin() + __pos;
 }
 
 template <class _Tp, class _Allocator>
 template <class _InpIter>
 void

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
+//
+//===----------------------------------------------------------------------===//
+
+// <deque>
+
+// deque(from_range_t, R&& rg, const Allocator& = Allocator());
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17, c++20
+
+#include <algorithm>
+#include <array>
+#include <cassert>
+#include <deque>
+#include <type_traits>
+
+#include "test_allocator.h"
+#include "test_iterators.h"
+
+template <class Iter, class Sent = Iter>
+void test_iterators() {
+  int a[]    = {1, 2, 3, 4};
+  auto range = std::ranges::subrange(Iter(a), Sent(Iter(a)));
+  std::deque<int> d(std::from_range, a);
+  assert(std::ranges::equal(d, a));
+}
+
+void test_ctad() {
+  {
+    int a[] = {1, 2, 3, 4};
+    std::deque d(std::from_range, a);
+    static_assert(std::is_same_v<decltype(d), std::deque<int>>);
+  }
+  {
+    test_allocator<int> alloc;
+    int a[] = {1, 2, 3, 4};
+    std::deque d(std::from_range, a, alloc);
+    static_assert(std::is_same_v<decltype(d), std::deque<int, test_allocator<int>>>);
+  }
+}
+
+bool test() {
+  test_iterators<cpp17_input_iterator<int*>, sentinel_wrapper<cpp17_input_iterator<int*>>>();
+  test_iterators<cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>>();
+  test_iterators<forward_iterator<int*>>();
+  test_iterators<bidirectional_iterator<int*>>();
+  test_iterators<random_access_iterator<int*>>();
+  test_iterators<contiguous_iterator<int*>>();
+  test_iterators<int*>();
+  test_iterators<const int*>();
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+
+  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
+//
+//===----------------------------------------------------------------------===//
+
+// <deque>
+
+// deque(from_range_t, R&& rg, const Allocator& = Allocator());
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17, c++20
+
+#include <algorithm>
+#include <array>
+#include <cassert>
+#include <deque>
+#include <type_traits>
+
+#include "test_allocator.h"
+#include "test_iterators.h"
+
+template <class Iter, class Sent = Iter>
+void test_iterators() {
+  int a[]           = {1, 2, 3, 4};
+  auto range        = std::ranges::subrange(Iter(a), Sent(Iter(a)));
+  std::deque<int> d = {1, 2, 3, 4, 5, 6};
+  d.prepend_range(a);
+  assert(std::ranges::equal(d, std::array{1, 2, 3, 4, 1, 2, 3, 4, 5, 6}));
+}
+
+bool test() {
+  test_iterators<cpp17_input_iterator<int*>, sentinel_wrapper<cpp17_input_iterator<int*>>>();
+  test_iterators<cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>>();
+  test_iterators<forward_iterator<int*>>();
+  test_iterators<forward_iterator<int*>, sized_sentinel<forward_iterator<int*>>>();
+  test_iterators<bidirectional_iterator<int*>>();
+  test_iterators<random_access_iterator<int*>>();
+  test_iterators<contiguous_iterator<int*>>();
+  test_iterators<int*>();
+  test_iterators<const int*>();
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+
+  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
+//
+//===----------------------------------------------------------------------===//
+
+// <deque>
+
+// deque(from_range_t, R&& rg, const Allocator& = Allocator());
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17, c++20
+
+#include <algorithm>
+#include <array>
+#include <cassert>
+#include <deque>
+#include <type_traits>
+
+#include "test_allocator.h"
+#include "test_iterators.h"
+
+template <class Iter, class Sent = Iter>
+void test_iterators() {
+  { // insert at the front
+    int a[]           = {1, 2, 3, 4};
+    auto range        = std::ranges::subrange(Iter(a), Sent(Iter(a)));
+    std::deque<int> d = {1, 2, 3, 4, 5, 6};
+    d.insert_range(d.begin(), a);
+    assert(std::ranges::equal(d, std::array{1, 2, 3, 4, 1, 2, 3, 4, 5, 6}));
+  }
+
+  { // insert in the middle
+    int a[]           = {1, 2, 3, 4};
+    auto range        = std::ranges::subrange(Iter(a), Sent(Iter(a)));
+    std::deque<int> d = {1, 2, 3, 4, 5, 6};
+    d.insert_range(d.begin() + 3, a);
+    assert(std::ranges::equal(d, std::array{1, 2, 3, 1, 2, 3, 4, 4, 5, 6}));
+  }
+
+  { // insert at the back
+    int a[]           = {1, 2, 3, 4};
+    auto range        = std::ranges::subrange(Iter(a), Sent(Iter(a)));
+    std::deque<int> d = {1, 2, 3, 4, 5, 6};
+    d.insert_range(d.begin() + 6, a);
+    assert(std::ranges::equal(d, std::array{1, 2, 3, 4, 5, 6, 1, 2, 3, 4}));
+  }
+}
+
+bool test() {
+  test_iterators<cpp17_input_iterator<int*>, sentinel_wrapper<cpp17_input_iterator<int*>>>();
+  test_iterators<cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>>();
+  test_iterators<forward_iterator<int*>>();
+  test_iterators<bidirectional_iterator<int*>>();
+  test_iterators<random_access_iterator<int*>>();
+  test_iterators<contiguous_iterator<int*>>();
+  test_iterators<int*>();
+  test_iterators<const int*>();
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+
+  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
+//
+//===----------------------------------------------------------------------===//
+
+// <deque>
+
+// deque(from_range_t, R&& rg, const Allocator& = Allocator());
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17, c++20
+
+#include <algorithm>
+#include <array>
+#include <cassert>
+#include <deque>
+#include <type_traits>
+
+#include "test_allocator.h"
+#include "test_iterators.h"
+
+template <class Iter, class Sent = Iter>
+void test_iterators() {
+  int a[]           = {1, 2, 3, 4};
+  auto range        = std::ranges::subrange(Iter(a), Sent(Iter(a)));
+  std::deque<int> d = {1, 2, 3, 4, 5, 6};
+  d.prepend_range(a);
+  assert(std::ranges::equal(d, std::array{1, 2, 3, 4, 1, 2, 3, 4, 5, 6}));
+}
+
+bool test() {
+  test_iterators<cpp17_input_iterator<int*>, sentinel_wrapper<cpp17_input_iterator<int*>>>();
+  test_iterators<cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>>();
+  test_iterators<forward_iterator<int*>>();
+  test_iterators<forward_iterator<int*>, sized_sentinel<forward_iterator<int*>>>();
+  test_iterators<bidirectional_iterator<int*>>();
+  test_iterators<random_access_iterator<int*>>();
+  test_iterators<contiguous_iterator<int*>>();
+  test_iterators<int*>();
+  test_iterators<const int*>();
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+
+  return 0;
+}