diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -192,6 +192,7 @@ __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 @@ -411,6 +412,7 @@ __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 diff --git a/libcxx/include/__algorithm/iterator_operations.h b/libcxx/include/__algorithm/iterator_operations.h --- a/libcxx/include/__algorithm/iterator_operations.h +++ b/libcxx/include/__algorithm/iterator_operations.h @@ -13,6 +13,8 @@ #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 @@ -24,6 +26,8 @@ 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 @@ -40,6 +44,23 @@ return std::distance(__first, __last); } + template + _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 + _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_AFTER_CXX11 + _Iterator next(_Iterator, _Iterator __last) { + return __last; + } + + template + _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 diff --git a/libcxx/include/__concepts/container_compatible_range.h b/libcxx/include/__concepts/container_compatible_range.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__concepts/container_compatible_range.h @@ -0,0 +1,32 @@ +//===----------------------------------------------------------------------===// +// +// 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 +concept __container_compatible_range = + ranges::input_range<_Range> && convertible_to, _Type>; + +#endif // _LIBCPP_STD_VER > 20 + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP___CONCEPTS_CONTAINER_COMPATIBLE_RANGE_H diff --git a/libcxx/include/__ranges/from_range_t.h b/libcxx/include/__ranges/from_range_t.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__ranges/from_range_t.h @@ -0,0 +1,32 @@ +//===----------------------------------------------------------------------===// +// +// 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 diff --git a/libcxx/include/__split_buffer b/libcxx/include/__split_buffer --- a/libcxx/include/__split_buffer +++ b/libcxx/include/__split_buffer @@ -118,12 +118,12 @@ void __construct_at_end(size_type __n); void __construct_at_end(size_type __n, const_reference __x); - template + template __enable_if_t<__is_exactly_cpp17_input_iterator<_InputIter>::value> - __construct_at_end(_InputIter __first, _InputIter __last); - template + __construct_at_end(_InputIter __first, _Sent __last); + template __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());} @@ -230,9 +230,9 @@ } template -template +template __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) @@ -253,9 +253,9 @@ } template -template +template __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) { diff --git a/libcxx/include/deque b/libcxx/include/deque --- a/libcxx/include/deque +++ b/libcxx/include/deque @@ -164,18 +164,26 @@ #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> @@ -1327,6 +1335,16 @@ template 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& __a); @@ -1359,6 +1377,47 @@ template 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 @@ -1444,6 +1503,47 @@ template void emplace_front(_Args&&... __args); template 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(__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(__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 __buf(get_allocator()); + for (auto&& __e : __range) + __buf.emplace_back(std::forward(__e)); + prepend_range(__buf); + } + } +#endif // _LIBCPP_STD_VER > 20 + template iterator emplace(const_iterator __p, _Args&&... __args); void push_front(value_type&& __v); @@ -1466,7 +1566,31 @@ &&!__is_cpp17_bidirectional_iterator<_ForwardIterator>::value>::type* = 0); template 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 + _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 __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(); @@ -1615,6 +1739,13 @@ -> deque<__iter_value_type<_InputIterator>, _Alloc>; #endif +#if _LIBCPP_STD_VER > 20 + +template >> +deque(from_range_t, _Range&&, _Allocator = _Allocator()) -> deque, _Allocator>; + +#endif // _LIBCPP_STD_VER > 20 + template deque<_Tp, _Allocator>::deque(size_type __n) { @@ -2284,12 +2415,12 @@ } template -template -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 +_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(); @@ -2300,11 +2431,11 @@ // __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; } @@ -2318,8 +2449,8 @@ ++__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 @@ -2330,12 +2461,12 @@ // __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; } @@ -2345,8 +2476,8 @@ 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; diff --git a/libcxx/test/std/containers/sequences/deque/deque.cons/from_range.pass.cpp b/libcxx/test/std/containers/sequences/deque/deque.cons/from_range.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/containers/sequences/deque/deque.cons/from_range.pass.cpp @@ -0,0 +1,63 @@ +//===----------------------------------------------------------------------===// +// +// 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(from_range_t, R&& rg, const Allocator& = Allocator()); + +// UNSUPPORTED: c++03, c++11, c++14, c++17, c++20 + +#include +#include +#include +#include +#include + +#include "test_allocator.h" +#include "test_iterators.h" + +template +void test_iterators() { + int a[] = {1, 2, 3, 4}; + auto range = std::ranges::subrange(Iter(a), Sent(Iter(a))); + std::deque 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>); + } + { + test_allocator alloc; + int a[] = {1, 2, 3, 4}; + std::deque d(std::from_range, a, alloc); + static_assert(std::is_same_v>>); + } +} + +bool test() { + test_iterators, sentinel_wrapper>>(); + test_iterators, sentinel_wrapper>>(); + test_iterators>(); + test_iterators>(); + test_iterators>(); + test_iterators>(); + test_iterators(); + test_iterators(); + + return true; +} + +int main(int, char**) { + test(); + + return 0; +} diff --git a/libcxx/test/std/containers/sequences/deque/deque.modifiers/append_range.pass.cpp b/libcxx/test/std/containers/sequences/deque/deque.modifiers/append_range.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/containers/sequences/deque/deque.modifiers/append_range.pass.cpp @@ -0,0 +1,51 @@ +//===----------------------------------------------------------------------===// +// +// 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(from_range_t, R&& rg, const Allocator& = Allocator()); + +// UNSUPPORTED: c++03, c++11, c++14, c++17, c++20 + +#include +#include +#include +#include +#include + +#include "test_allocator.h" +#include "test_iterators.h" + +template +void test_iterators() { + int a[] = {1, 2, 3, 4}; + auto range = std::ranges::subrange(Iter(a), Sent(Iter(a))); + std::deque 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, sentinel_wrapper>>(); + test_iterators, sentinel_wrapper>>(); + test_iterators>(); + test_iterators, sized_sentinel>>(); + test_iterators>(); + test_iterators>(); + test_iterators>(); + test_iterators(); + test_iterators(); + + return true; +} + +int main(int, char**) { + test(); + + return 0; +} diff --git a/libcxx/test/std/containers/sequences/deque/deque.modifiers/insert_range.pass.cpp b/libcxx/test/std/containers/sequences/deque/deque.modifiers/insert_range.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/containers/sequences/deque/deque.modifiers/insert_range.pass.cpp @@ -0,0 +1,68 @@ +//===----------------------------------------------------------------------===// +// +// 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(from_range_t, R&& rg, const Allocator& = Allocator()); + +// UNSUPPORTED: c++03, c++11, c++14, c++17, c++20 + +#include +#include +#include +#include +#include + +#include "test_allocator.h" +#include "test_iterators.h" + +template +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 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 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 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, sentinel_wrapper>>(); + test_iterators, sentinel_wrapper>>(); + test_iterators>(); + test_iterators>(); + test_iterators>(); + test_iterators>(); + test_iterators(); + test_iterators(); + + return true; +} + +int main(int, char**) { + test(); + + return 0; +} diff --git a/libcxx/test/std/containers/sequences/deque/deque.modifiers/prepend_range.pass.cpp b/libcxx/test/std/containers/sequences/deque/deque.modifiers/prepend_range.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/containers/sequences/deque/deque.modifiers/prepend_range.pass.cpp @@ -0,0 +1,51 @@ +//===----------------------------------------------------------------------===// +// +// 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(from_range_t, R&& rg, const Allocator& = Allocator()); + +// UNSUPPORTED: c++03, c++11, c++14, c++17, c++20 + +#include +#include +#include +#include +#include + +#include "test_allocator.h" +#include "test_iterators.h" + +template +void test_iterators() { + int a[] = {1, 2, 3, 4}; + auto range = std::ranges::subrange(Iter(a), Sent(Iter(a))); + std::deque 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, sentinel_wrapper>>(); + test_iterators, sentinel_wrapper>>(); + test_iterators>(); + test_iterators, sized_sentinel>>(); + test_iterators>(); + test_iterators>(); + test_iterators>(); + test_iterators(); + test_iterators(); + + return true; +} + +int main(int, char**) { + test(); + + return 0; +}