From patchwork Thu Oct 24 14:59:26 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jonathan Wakely X-Patchwork-Id: 2001786 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=redhat.com header.i=@redhat.com header.a=rsa-sha256 header.s=mimecast20190719 header.b=HmhXmTUr; dkim-atps=neutral Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; helo=server2.sourceware.org; envelope-from=gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=patchwork.ozlabs.org) Received: from server2.sourceware.org (server2.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4XZ8H11pphz1xx6 for ; Fri, 25 Oct 2024 02:00:29 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 5CB7E385840D for ; Thu, 24 Oct 2024 15:00:27 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.129.124]) by sourceware.org (Postfix) with ESMTP id 0004E3858D33 for ; Thu, 24 Oct 2024 14:59:58 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 0004E3858D33 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=redhat.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 0004E3858D33 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=170.10.129.124 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1729782004; cv=none; b=VHFTKneHRQe7nBfguoyTR/WGfJ1bapGIxv9a1lXXHTRzyVUB7ysOOZw5O4Guplm8OEz22JVUBhIBxeNLtMbeDXZZD09JYjq86nQ31/rb6I88h9O0k66OkDtSuwva9NNZ7nSJ8jyr06bmsdZpc2ePZieSHyU1+yD1LEhOkdvY8Es= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1729782004; c=relaxed/simple; bh=9aCu3MQaqPLNstnZK5mZxGpbeXSID07QtL3OZxD51FE=; h=DKIM-Signature:From:To:Subject:Date:Message-ID:MIME-Version; b=kpcTe5SHmyybNL5hFOeMo3I8kV6IphQk6OUb0WUT/esPT1Jdov4854ni36ce0sSdFhCkc3yX0DxviUDUcBbzwOexs2d86NuMiEoyVma3FgFr4H9fgburA+mRJNNbX/ntPiIVkJ0X3UGOpbZsgPu2P8TFuWM6n6XPnijwDHuysLc= ARC-Authentication-Results: i=1; server2.sourceware.org DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1729781998; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=FIx+tVuXR36tQT8n4t2gKvI0rsxqiJWIFrxPkUAj9DM=; b=HmhXmTUre+dAnaHZqCA6GAXD4YicdfE9MKsVV8atvkPQWDlO/wEWuisXUEpLeHTco5Kywt dNYy5O+nBH9ePfBEZYc8cF4I9o88aIywhv4pD63JjMPeGy4j8Ustz23VOw+hxsR7maYf7B TMAlI2MQJ9dIsOoD4ZjizCm1Xb9TsrM= Received: from mx-prod-mc-05.mail-002.prod.us-west-2.aws.redhat.com (ec2-54-186-198-63.us-west-2.compute.amazonaws.com [54.186.198.63]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-447-nuu7QhEVNFGfRxGIIYtlLw-1; Thu, 24 Oct 2024 10:59:55 -0400 X-MC-Unique: nuu7QhEVNFGfRxGIIYtlLw-1 Received: from mx-prod-int-03.mail-002.prod.us-west-2.aws.redhat.com (mx-prod-int-03.mail-002.prod.us-west-2.aws.redhat.com [10.30.177.12]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by mx-prod-mc-05.mail-002.prod.us-west-2.aws.redhat.com (Postfix) with ESMTPS id 4F0A61955F45; Thu, 24 Oct 2024 14:59:54 +0000 (UTC) Received: from localhost (unknown [10.42.28.5]) by mx-prod-int-03.mail-002.prod.us-west-2.aws.redhat.com (Postfix) with ESMTP id 2788019560A2; Thu, 24 Oct 2024 14:59:50 +0000 (UTC) From: Jonathan Wakely To: libstdc++@gcc.gnu.org, gcc-patches@gcc.gnu.org Subject: [PATCH] libstdc++: Add P1206R7 from_range members to std::vector [PR111055] Date: Thu, 24 Oct 2024 15:59:26 +0100 Message-ID: <20241024145949.1450378-1-jwakely@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 3.0 on 10.30.177.12 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com X-Spam-Status: No, score=-15.0 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_NONE, TXREP autolearn=unavailable autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org This is another piece of P1206R7, adding new members to std::vector and std::vector. The __uninitialized_copy_a extension needs to be enhanced to support passing non-common ranges (i.e. a sentinel that is a different type from the iterator) and move-only input iterators. libstdc++-v3/ChangeLog: PR libstdc++/111055 * include/bits/ranges_base.h (__container_compatible_range): New concept. * include/bits/stl_bvector.h (vector(from_range, R&&, const Alloc&)) (assign_range, insert_range, append_range): Define. * include/bits/stl_uninitialized.h (__do_uninit_copy): Support non-common ranges. (__uninitialized_copy_a): Likewise. * include/bits/stl_vector.h (_Vector_base::_M_append_range_to): New function. (_Vector_base::_M_append_range): Likewise. (vector(from_range, R&&, const Alloc&), assign_range): Define. (append_range): Define. (insert_range): Declare. * include/debug/vector (vector(from_range, R&&, const Alloc&)) (assign_range, insert_range, append_range): Define. * include/bits/vector.tcc (insert_range): Define. * testsuite/23_containers/vector/bool/cons/from_range.cc: New test. * testsuite/23_containers/vector/bool/modifiers/assign/assign_range.cc: New test. * testsuite/23_containers/vector/bool/modifiers/insert/append_range.cc: New test. * testsuite/23_containers/vector/bool/modifiers/insert/insert_range.cc: New test. * testsuite/23_containers/vector/cons/from_range.cc: New test. * testsuite/23_containers/vector/modifiers/append_range.cc: New test. * testsuite/23_containers/vector/modifiers/assign/assign_range.cc: New test. * testsuite/23_containers/vector/modifiers/insert/insert_range.cc: New test. --- Tested x86_64-linux. libstdc++-v3/include/bits/ranges_base.h | 10 ++ libstdc++-v3/include/bits/stl_bvector.h | 120 +++++++++++++ libstdc++-v3/include/bits/stl_uninitialized.h | 38 +++- libstdc++-v3/include/bits/stl_vector.h | 166 ++++++++++++++++++ libstdc++-v3/include/bits/vector.tcc | 124 +++++++++++++ libstdc++-v3/include/debug/vector | 70 ++++++++ .../vector/bool/cons/from_range.cc | 81 +++++++++ .../bool/modifiers/assign/assign_range.cc | 96 ++++++++++ .../bool/modifiers/insert/append_range.cc | 83 +++++++++ .../bool/modifiers/insert/insert_range.cc | 94 ++++++++++ .../23_containers/vector/cons/from_range.cc | 94 ++++++++++ .../vector/modifiers/append_range.cc | 83 +++++++++ .../vector/modifiers/assign/assign_range.cc | 107 +++++++++++ .../vector/modifiers/insert/insert_range.cc | 94 ++++++++++ 14 files changed, 1252 insertions(+), 8 deletions(-) create mode 100644 libstdc++-v3/testsuite/23_containers/vector/bool/cons/from_range.cc create mode 100644 libstdc++-v3/testsuite/23_containers/vector/bool/modifiers/assign/assign_range.cc create mode 100644 libstdc++-v3/testsuite/23_containers/vector/bool/modifiers/insert/append_range.cc create mode 100644 libstdc++-v3/testsuite/23_containers/vector/bool/modifiers/insert/insert_range.cc create mode 100644 libstdc++-v3/testsuite/23_containers/vector/cons/from_range.cc create mode 100644 libstdc++-v3/testsuite/23_containers/vector/modifiers/append_range.cc create mode 100644 libstdc++-v3/testsuite/23_containers/vector/modifiers/assign/assign_range.cc create mode 100644 libstdc++-v3/testsuite/23_containers/vector/modifiers/insert/insert_range.cc diff --git a/libstdc++-v3/include/bits/ranges_base.h b/libstdc++-v3/include/bits/ranges_base.h index cb2eba1f841..a2c743ff56b 100644 --- a/libstdc++-v3/include/bits/ranges_base.h +++ b/libstdc++-v3/include/bits/ranges_base.h @@ -1079,6 +1079,16 @@ namespace ranges #if __glibcxx_ranges_to_container // C++ >= 23 struct from_range_t { explicit from_range_t() = default; }; inline constexpr from_range_t from_range{}; + +/// @cond undocumented +namespace __detail +{ + template + concept __container_compatible_range + = ranges::input_range<_Rg> + && convertible_to, _Tp>; +} +/// @endcond #endif _GLIBCXX_END_NAMESPACE_VERSION diff --git a/libstdc++-v3/include/bits/stl_bvector.h b/libstdc++-v3/include/bits/stl_bvector.h index 42261ac5915..ebb5ff2c594 100644 --- a/libstdc++-v3/include/bits/stl_bvector.h +++ b/libstdc++-v3/include/bits/stl_bvector.h @@ -892,6 +892,31 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER } #endif +#if __glibcxx_ranges_to_container // C++ >= 23 + /** + * @brief Construct a vector from a range. + * @since C++23 + */ + template<__detail::__container_compatible_range _Rg> + constexpr + vector(from_range_t, _Rg&& __rg, const _Alloc& __a = _Alloc()) + : _Base(__a) + { + if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>) + { + _M_initialize(size_type(ranges::distance(__rg))); + ranges::copy(__rg, begin()); + } + else + { + auto __first = ranges::begin(__rg); + const auto __last = ranges::end(__rg); + for (; __first != __last; ++__first) + emplace_back(*__first); + } + } +#endif + _GLIBCXX20_CONSTEXPR ~vector() _GLIBCXX_NOEXCEPT { } @@ -996,6 +1021,21 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { _M_assign_aux(__l.begin(), __l.end(), random_access_iterator_tag()); } #endif +#if __glibcxx_ranges_to_container // C++ >= 23 + /** + * @brief Assign a range to the vector. + * @since C++23 + */ + template<__detail::__container_compatible_range _Rg> + constexpr void + assign_range(_Rg&& __rg) + { + static_assert(assignable_from>); + clear(); + append_range(std::forward<_Rg>(__rg)); + } +#endif + _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR iterator begin() _GLIBCXX_NOEXCEPT @@ -1279,6 +1319,86 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { return this->insert(__p, __l.begin(), __l.end()); } #endif +#if __glibcxx_ranges_to_container // C++ >= 23 + /** + * @brief Insert a range into the vector. + * @since C++23 + */ + template<__detail::__container_compatible_range _Rg> + constexpr iterator + insert_range(const_iterator __pos, _Rg&& __rg) + { + if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>) + { + if (auto __n = size_type(ranges::distance(__rg))) + { + if (capacity() - size() >= __n) + { + std::copy_backward(__pos._M_const_cast(), end(), + this->_M_impl._M_finish + + difference_type(__n)); + auto __i = ranges::copy(__rg, __pos._M_const_cast()).out; + this->_M_impl._M_finish += difference_type(__n); + return __i; + } + else + { + const size_type __len = + _M_check_len(__n, "vector::insert_range"); + const iterator __begin = begin(), __end = end(); + _Bit_pointer __q = this->_M_allocate(__len); + iterator __start(std::__addressof(*__q), 0); + iterator __i = _M_copy_aligned(__begin, + __pos._M_const_cast(), + __start); + __i = ranges::copy(__rg, __i).out; + iterator __finish = std::copy(__pos._M_const_cast(), + __end, __i); + this->_M_deallocate(); + this->_M_impl._M_end_of_storage = __q + _S_nword(__len); + this->_M_impl._M_start = __start; + this->_M_impl._M_finish = __finish; + return __i; + } + } + else + return __pos._M_const_cast(); + } + else + return insert_range(__pos, + vector(from_range, __rg, get_allocator())); + } + + /** + * @brief Append a range at the end of the vector. + * @since C++23 + */ + template<__detail::__container_compatible_range _Rg> + constexpr void + append_range(_Rg&& __rg) + { + if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>) + { + reserve(size() + size_type(ranges::distance(__rg))); + this->_M_impl._M_finish = ranges::copy(__rg, end()).out; + } + else + { + auto __first = ranges::begin(__rg); + const auto __last = ranges::end(__rg); + size_type __n = size(); + const size_type __cap = capacity(); + for (; __first != __last && __n < __cap; ++__first, (void)++__n) + emplace_back(*__first); + if (__first != __last) + { + ranges::subrange __rest(std::move(__first), __last); + append_range(vector(from_range, __rest, get_allocator())); + } + } + } +#endif // ranges_to_container + _GLIBCXX20_CONSTEXPR void pop_back() diff --git a/libstdc++-v3/include/bits/stl_uninitialized.h b/libstdc++-v3/include/bits/stl_uninitialized.h index de3e8cbeaf5..d5674fa9881 100644 --- a/libstdc++-v3/include/bits/stl_uninitialized.h +++ b/libstdc++-v3/include/bits/stl_uninitialized.h @@ -132,10 +132,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION }; // This is the default implementation of std::uninitialized_copy. - template + // This can be used with C++20 iterators and non-common ranges. + template _GLIBCXX20_CONSTEXPR _ForwardIterator - __do_uninit_copy(_InputIterator __first, _InputIterator __last, + __do_uninit_copy(_InputIterator __first, _Sentinel __last, _ForwardIterator __result) { _UninitDestroyGuard<_ForwardIterator> __guard(__result); @@ -568,11 +570,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // default allocator. For nondefault allocators we do not use // any of the POD optimizations. - template + template _GLIBCXX20_CONSTEXPR _ForwardIterator - __uninitialized_copy_a(_InputIterator __first, _InputIterator __last, + __uninitialized_copy_a(_InputIterator __first, _Sentinel __last, _ForwardIterator __result, _Allocator& __alloc) { _UninitDestroyGuard<_ForwardIterator, _Allocator> @@ -586,17 +588,37 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } #if _GLIBCXX_HOSTED - template + template _GLIBCXX20_CONSTEXPR inline _ForwardIterator - __uninitialized_copy_a(_InputIterator __first, _InputIterator __last, + __uninitialized_copy_a(_InputIterator __first, _Sentinel __last, _ForwardIterator __result, allocator<_Tp>&) { #ifdef __cpp_lib_is_constant_evaluated if (std::is_constant_evaluated()) - return std::__do_uninit_copy(__first, __last, __result); + return std::__do_uninit_copy(std::move(__first), __last, __result); #endif + +#ifdef __glibcxx_ranges + if constexpr (!is_same_v<_InputIterator, _Sentinel>) + { + // Convert to a common range if possible, to benefit from memcpy + // optimizations that std::uninitialized_copy might use. + if constexpr (sized_sentinel_for<_Sentinel, _InputIterator> + && random_access_iterator<_InputIterator>) + return std::uninitialized_copy(__first, + __first + (__last - __first), + __result); + else // Just use default implementation. + return std::__do_uninit_copy(std::move(__first), __last, __result); + } + else + return std::uninitialized_copy(std::move(__first), std::move(__last), + __result); +#else return std::uninitialized_copy(__first, __last, __result); +#endif } #endif diff --git a/libstdc++-v3/include/bits/stl_vector.h b/libstdc++-v3/include/bits/stl_vector.h index 8982ca2b9ee..fb97810acf8 100644 --- a/libstdc++-v3/include/bits/stl_vector.h +++ b/libstdc++-v3/include/bits/stl_vector.h @@ -65,6 +65,10 @@ #if __cplusplus >= 202002L # include #endif +#if __cplusplus > 202002L +# include // ranges::copy +# include // ranges::subrange +#endif #include @@ -399,6 +403,29 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER this->_M_impl._M_finish = this->_M_impl._M_start; this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n; } + +#if __glibcxx_ranges_to_container // C++ >= 23 + // Called by insert_range, and indirectly by assign_range, append_range. + // Initializes new elements in storage at __ptr and updates __ptr to + // point after the last new element. + // Provides strong exception safety guarantee. + // Requires [ptr, ptr+distance(rg)) is a valid range. + template + constexpr void + _M_append_range_to(_Rg&& __rg, pointer& __ptr) + { + __ptr = std::__uninitialized_copy_a(ranges::begin(__rg), + ranges::end(__rg), + __ptr, _M_get_Tp_allocator()); + } + + // Called by assign_range, append_range, insert_range. + // Requires capacity() >= size()+distance(rg). + template + constexpr void + _M_append_range(_Rg&& __rg) + { _M_append_range_to(std::forward<_Rg>(__rg), _M_impl._M_finish); } +#endif }; /** @@ -723,6 +750,47 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER } #endif +#if __glibcxx_ranges_to_container // C++ >= 23 + /** + * @brief Construct a vector from a range. + * @since C++23 + */ + template<__detail::__container_compatible_range<_Tp> _Rg> + constexpr + vector(from_range_t, _Rg&& __rg, const _Alloc& __a = _Alloc()) + : _Base(__a) + { + if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>) + { + const auto __n = size_type(ranges::distance(__rg)); + pointer __start = + this->_M_allocate(_S_check_init_len(__n, + _M_get_Tp_allocator())); + _Guard_alloc __guard(__start, __n, *this); + this->_M_impl._M_finish = this->_M_impl._M_start = __start; + this->_M_impl._M_end_of_storage = __start + __n; + _Base::_M_append_range(__rg); + (void) __guard._M_release(); + } + else + { + // If an exception is thrown ~_Base() will deallocate storage, + // but will not destroy elements. This RAII type destroys them. + struct _Clear + { + ~_Clear() { if (_M_this) _M_this->clear(); } + vector* _M_this; + } __guard{this}; + + auto __first = ranges::begin(__rg); + const auto __last = ranges::end(__rg); + for (; __first != __last; ++__first) + emplace_back(*__first); + __guard._M_this = nullptr; + } + } +#endif + /** * The dtor only erases the elements, and note that if the * elements themselves are pointers, the pointed-to memory is @@ -859,6 +927,62 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER } #endif +#if __glibcxx_ranges_to_container // C++ >= 23 + /** + * @brief Assign a range to the vector. + * @since C++23 + */ + template<__detail::__container_compatible_range<_Tp> _Rg> + constexpr void + assign_range(_Rg&& __rg) + { + static_assert(assignable_from<_Tp&, ranges::range_reference_t<_Rg>>); + + if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>) + { + const auto __n = size_type(ranges::distance(__rg)); + if (__n <= size()) + { + auto __res = ranges::copy(__rg, this->_M_impl._M_start); + _M_erase_at_end(__res.out); + return; + } + + reserve(__n); + auto __first = ranges::copy_n(ranges::begin(__rg), size(), + this->_M_impl._M_start).in; + [[maybe_unused]] const auto __diff = __n - size(); + _GLIBCXX_ASAN_ANNOTATE_GROW(__diff); + _Base::_M_append_range(ranges::subrange(std::move(__first), + ranges::end(__rg))); + _GLIBCXX_ASAN_ANNOTATE_GREW(__diff); + } + else // input_range<_Rg> + { + auto __first = ranges::begin(__rg); + const auto __last = ranges::end(__rg); + pointer __ptr = this->_M_impl._M_start; + pointer const __end = this->_M_impl._M_finish; + + while (__ptr < __end && __first != __last) + { + *__ptr = *__first; + ++__ptr; + ++__first; + } + + if (__first == __last) + _M_erase_at_end(__ptr); + else + { + do + emplace_back(*__first); + while (++__first != __last); + } + } + } +#endif // ranges_to_container + /// Get a copy of the memory allocation object. using _Base::get_allocator; @@ -1515,6 +1639,41 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER } #endif +#if __glibcxx_ranges_to_container // C++ >= 23 + /** + * @brief Insert a range into the vector. + * @since C++23 + */ + template<__detail::__container_compatible_range<_Tp> _Rg> + constexpr iterator + insert_range(const_iterator __pos, _Rg&& __rg); + + /** + * @brief Append a range at the end of the vector. + * @since C++23 + */ + template<__detail::__container_compatible_range<_Tp> _Rg> + constexpr void + append_range(_Rg&& __rg) + { + if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>) + { + const auto __n = size_type(ranges::distance(__rg)); + reserve(size() + __n); + _GLIBCXX_ASAN_ANNOTATE_GROW(__n); + _Base::_M_append_range(__rg); + _GLIBCXX_ASAN_ANNOTATE_GREW(__n); + } + else + { + auto __first = ranges::begin(__rg); + const auto __last = ranges::end(__rg); + for (; __first != __last; ++__first) + emplace_back(*__first); + } + } +#endif // ranges_to_container + /** * @brief Remove element at given position. * @param __position Iterator pointing to element to be erased. @@ -2049,6 +2208,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER typename = _RequireAllocator<_Allocator>> vector(_InputIterator, _InputIterator, _Allocator = _Allocator()) -> vector<_ValT, _Allocator>; + +#if __glibcxx_ranges_to_container // C++ >= 23 + template>> + vector(from_range_t, _Rg&&, _Alloc = _Alloc()) + -> vector, _Alloc>; +#endif #endif /** diff --git a/libstdc++-v3/include/bits/vector.tcc b/libstdc++-v3/include/bits/vector.tcc index a99a5b56b77..f9c050726dd 100644 --- a/libstdc++-v3/include/bits/vector.tcc +++ b/libstdc++-v3/include/bits/vector.tcc @@ -974,6 +974,130 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER } } +#if __glibcxx_ranges_to_container // C++ >= 23 + template + template<__detail::__container_compatible_range<_Tp> _Rg> + constexpr auto + vector<_Tp, _Alloc>:: + insert_range(const_iterator __pos, _Rg&& __rg) + -> iterator + { + if (__pos == cend()) + { + append_range(std::forward<_Rg>(__rg)); + return end(); + } + + auto __first = ranges::begin(__rg); + const auto __last = ranges::end(__rg); + + if constexpr (ranges::forward_range<_Rg>) + { + // Start of existing elements: + pointer __old_start = this->_M_impl._M_start; + // End of existing elements: + pointer __old_finish = this->_M_impl._M_finish; + // Insertion point: + const auto __ins_idx = __pos - cbegin(); + pointer __ins = __old_start + __ins_idx; + // Number of new elements to insert: + const auto __n = size_type(ranges::distance(__rg)); + // Number of elements that can fit in unused capacity: + const auto __cap = this->_M_impl._M_end_of_storage - __old_finish; + if (__cap >= __n) + { + // Number of existing elements after insertion point: + const size_type __elems_after = cend() - __pos; + if (__elems_after > __n) + { + _GLIBCXX_ASAN_ANNOTATE_GROW(__n); + std::__uninitialized_move_a(__old_finish - __n, + __old_finish, + __old_finish, + _M_get_Tp_allocator()); + this->_M_impl._M_finish += __n; + _GLIBCXX_ASAN_ANNOTATE_GREW(__n); + std::move_backward(__ins, __old_finish - __n, __old_finish); + ranges::copy(__rg, __ins); + } + else + { + auto __mid = ranges::next(__first, __elems_after); + _GLIBCXX_ASAN_ANNOTATE_GROW(__n); + _Base::_M_append_range(ranges::subrange(__mid, __last)); + _GLIBCXX_ASAN_ANNOTATE_GREW(__n - __elems_after); + std::__uninitialized_move_a(__ins, __old_finish, + this->_M_impl._M_finish, + _M_get_Tp_allocator()); + this->_M_impl._M_finish += __elems_after; + _GLIBCXX_ASAN_ANNOTATE_GREW(__elems_after); + ranges::copy(__first, __mid, __ins); + } + } + else // Reallocate + { + const size_type __len + = _M_check_len(__n, "vector::insert_range"); + + struct _Guard : _Guard_alloc + { + // End of elements to destroy: + pointer _M_finish = _Guard_alloc::_M_storage; + + using _Guard_alloc::_Guard_alloc; + + constexpr + ~_Guard() + { + std::_Destroy(this->_M_storage, _M_finish, + this->_M_vect._M_get_Tp_allocator()); + } + }; + + // Allocate new storage: + pointer __new_start(this->_M_allocate(__len)); + _Guard __guard(__new_start, __len, *this); + + auto& __alloc = _M_get_Tp_allocator(); + + // Populate the new storage in three steps. After each step, + // __guard owns the new storage and any elements that have + // been constructed there. + + // Move elements from before insertion point to new storage: + __guard._M_finish + = std::__uninitialized_move_if_noexcept_a( + __old_start, __ins, __new_start, __alloc); + + // Append new elements to new storage: + _Base::_M_append_range_to(__rg, __guard._M_finish); + + // Move elements from after insertion point to new storage: + __guard._M_finish + = std::__uninitialized_move_if_noexcept_a( + __ins, __old_finish, __guard._M_finish, __alloc); + + _GLIBCXX_ASAN_ANNOTATE_REINIT; // Creates _Asan::_Reinit. + + // All elements are in the new storage, exchange ownership + // with __guard so that it cleans up the old storage: + this->_M_impl._M_start = __guard._M_storage; + this->_M_impl._M_finish = __guard._M_finish; + this->_M_impl._M_end_of_storage = __new_start + __len; + __guard._M_storage = __old_start; + __guard._M_finish = __old_finish; + __guard._M_len = (__old_finish - __old_start) + __cap; + // _Asan::_Reinit destructor marks unused capacity. + // _Guard destructor destroys [old_start,old_finish). + // _Guard_alloc destructor frees [old_start,old_start+len). + } + return begin() + __ins_idx; + } + else + return insert_range(__pos, vector(from_range, std::move(__rg), + _M_get_Tp_allocator())); + } +#endif // ranges_to_container // vector template diff --git a/libstdc++-v3/include/debug/vector b/libstdc++-v3/include/debug/vector index fe43a372485..f2ab4f73764 100644 --- a/libstdc++-v3/include/debug/vector +++ b/libstdc++-v3/include/debug/vector @@ -244,6 +244,19 @@ namespace __debug const allocator_type& __a = allocator_type()) : _Base(__l, __a) { } +#if __glibcxx_ranges_to_container // C++ >= 23 + /** + * @brief Construct a vector from a range. + * @since C++23 + */ + template _Rg> + constexpr + vector(std::from_range_t __t, _Rg&& __rg, + const allocator_type& __a = allocator_type()) + : _Base(__t, std::forward<_Rg>(__rg), __a) + { } +#endif + ~vector() = default; #endif @@ -858,6 +871,56 @@ namespace __debug const _Base& _M_base() const _GLIBCXX_NOEXCEPT { return *this; } +#if __glibcxx_ranges_to_container // C++ >= 23 + template _Rg> + constexpr void + assign_range(_Rg&& __rg) + { + auto __old_begin = _Base::begin(); + auto __old_size = _Base::size(); + _Base::assign_range(__rg); + if (!std::__is_constant_evaluated()) + { + if (_Base::begin() != __old_begin) + this->_M_invalidate_all(); + else if (_Base::size() < __old_size) + this->_M_invalidate_after_nth(_Base::size()); + this->_M_update_guaranteed_capacity(); + } + } + + template<__detail::__container_compatible_range<_Tp> _Rg> + constexpr iterator + insert_range(const_iterator __pos, _Rg&& __rg) + { + auto __old_begin = _Base::begin(); + auto __old_size = _Base::size(); + auto __res = _Base::insert_range(__pos.base(), __rg); + if (!std::__is_constant_evaluated()) + { + if (_Base::begin() != __old_begin) + this->_M_invalidate_all(); + this->_M_update_guaranteed_capacity(); + } + return iterator(__res, this); + } + + template<__detail::__container_compatible_range<_Tp> _Rg> + constexpr void + append_range(_Rg&& __rg) + { + auto __old_begin = _Base::begin(); + auto __old_size = _Base::size(); + _Base::append_range(__rg); + if (!std::__is_constant_evaluated()) + { + if (_Base::begin() != __old_begin) + this->_M_invalidate_all(); + this->_M_update_guaranteed_capacity(); + } + } +#endif + private: void _M_invalidate_after_nth(difference_type __n) _GLIBCXX_NOEXCEPT @@ -937,6 +1000,13 @@ namespace __debug typename = _RequireAllocator<_Allocator>> vector(size_t, _Tp, _Allocator = _Allocator()) -> vector<_Tp, _Allocator>; + +#if __glibcxx_ranges_to_container // C++ >= 23 + template>> + vector(from_range_t, _Rg&&, _Alloc = _Alloc()) + -> vector, _Alloc>; +#endif #endif } // namespace __debug diff --git a/libstdc++-v3/testsuite/23_containers/vector/bool/cons/from_range.cc b/libstdc++-v3/testsuite/23_containers/vector/bool/cons/from_range.cc new file mode 100644 index 00000000000..5836c36d0f3 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/vector/bool/cons/from_range.cc @@ -0,0 +1,81 @@ +// { dg-do compile { target c++23 } } + +#include +#include +#include +#include +#include + +template +constexpr void +do_test(Alloc alloc) +{ + using T = std::ranges::range_value_t; + T a[]{1,1,0,1,0,0,1,0,0}; + + auto eq = [](const std::vector& l, std::span r) { + if (l.size() != r.size()) + return false; + for (auto i = 0u; i < l.size(); ++i) + if (l[i] != r[i]) + return false; + return true; + }; + + std::vector v0(std::from_range, Range(a, a+0)); + VERIFY( v0.empty() ); + VERIFY( v0.get_allocator() == Alloc() ); + + std::vector v4(std::from_range, Range(a, a+4)); + VERIFY( eq(v4, {a, 4}) ); + VERIFY( v4.get_allocator() == Alloc() ); + + std::vector v9(std::from_range, Range(a, a+9), alloc); + VERIFY( eq(v9, {a, 9}) ); + VERIFY( v9.get_allocator() == alloc ); +} + +template +void +do_test_a() +{ + do_test(std::allocator()); + do_test(__gnu_test::uneq_allocator(42)); +} + +bool +test_ranges() +{ + using namespace __gnu_test; + + do_test_a>(); + do_test_a>(); + do_test_a>(); + + do_test_a>(); + do_test_a>(); + do_test_a>(); + + do_test_a>(); + do_test_a>(); + do_test_a>(); + + do_test_a>(); + do_test_a>(); + + return true; +} + +constexpr bool +test_constexpr() +{ + // XXX: this doesn't test the non-forward_range code paths are constexpr. + do_test, std::allocator>; + return true; +} + +int main() +{ + test_ranges(); + static_assert( test_constexpr() ); +} diff --git a/libstdc++-v3/testsuite/23_containers/vector/bool/modifiers/assign/assign_range.cc b/libstdc++-v3/testsuite/23_containers/vector/bool/modifiers/assign/assign_range.cc new file mode 100644 index 00000000000..22c3ce31851 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/vector/bool/modifiers/assign/assign_range.cc @@ -0,0 +1,96 @@ +// { dg-do compile { target c++23 } } + +#include +#include +#include +#include +#include + +template +constexpr void +do_test() +{ + using T = std::ranges::range_value_t; + T a[]{1,1,0,1,0,0,1,0,0}; + + auto eq = [](const std::vector& l, std::span r) { + if (l.size() != r.size()) + return false; + for (auto i = 0u; i < l.size(); ++i) + if (l[i] != r[i]) + return false; + return true; + }; + + Range r4(a, a+4); + Range r9(a); + + std::vector v; + v.assign_range(Range(a, a)); + VERIFY( v.empty() ); + VERIFY( v.capacity() == 0 ); + v.assign_range(r4); + VERIFY( eq(v, {a, 4}) ); + v.clear(); + v.assign_range(r9); // larger than v.capacity() + VERIFY( eq(v, a) ); + v.assign_range(r9); // equal to size() and equal to capacity() + VERIFY( eq(v, a) ); + v.resize(1); + v.assign_range(r4); // larger than size(), smaller than capacity() + VERIFY( eq(v, {a, 4}) ); + v.clear(); + v.resize(4); + v.assign_range(r4); // equal to size(), smaller than capacity() + VERIFY( eq(v, {a, 4}) ); + v.shrink_to_fit(); + v.assign_range(r9); // larger than capacity() + VERIFY( eq(v, a) ); + v.assign_range(Range(a, a)); + VERIFY( v.empty() ); +} + +template +void +do_test_a() +{ + do_test>(); + do_test>(); +} + +bool +test_ranges() +{ + using namespace __gnu_test; + + do_test_a>(); + do_test_a>(); + do_test_a>(); + + do_test_a>(); + do_test_a>(); + do_test_a>(); + + do_test_a>(); + do_test_a>(); + do_test_a>(); + + do_test_a>(); + do_test_a>(); + + return true; +} + +constexpr bool +test_constexpr() +{ + // XXX: this doesn't test the non-forward_range code paths are constexpr. + do_test, std::allocator>; + return true; +} + +int main() +{ + test_ranges(); + static_assert( test_constexpr() ); +} diff --git a/libstdc++-v3/testsuite/23_containers/vector/bool/modifiers/insert/append_range.cc b/libstdc++-v3/testsuite/23_containers/vector/bool/modifiers/insert/append_range.cc new file mode 100644 index 00000000000..13cbddda9df --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/vector/bool/modifiers/insert/append_range.cc @@ -0,0 +1,83 @@ +// { dg-do compile { target c++23 } } + +#include +#include +#include +#include +#include + +template +constexpr void +do_test() +{ + using T = std::ranges::range_value_t; + T a[]{1,1,0,1,0,0,1,0,0}; + + auto eq = [](const std::vector& l, std::span r) { + if (l.size() != r.size()) + return false; + for (auto i = 0u; i < l.size(); ++i) + if (l[i] != r[i]) + return false; + return true; + }; + + Range r4(a, a+4); + Range r5(a+4, a+9); + + std::vector v; + v.append_range(r4); + VERIFY( eq(v, {a, 4}) ); + v.append_range(r5); // larger than v.capacity() + VERIFY( eq(v, a) ); + v.append_range(Range(a, a)); + VERIFY( eq(v, a) ); + v.clear(); + v.append_range(Range(a, a)); + VERIFY( v.empty() ); +} + +template +void +do_test_a() +{ + do_test>(); + do_test>(); +} + +bool +test_ranges() +{ + using namespace __gnu_test; + + do_test_a>(); + do_test_a>(); + do_test_a>(); + + do_test_a>(); + do_test_a>(); + do_test_a>(); + + do_test_a>(); + do_test_a>(); + do_test_a>(); + + do_test_a>(); + do_test_a>(); + + return true; +} + +constexpr bool +test_constexpr() +{ + // XXX: this doesn't test the non-forward_range code paths are constexpr. + do_test, std::allocator>; + return true; +} + +int main() +{ + test_ranges(); + static_assert( test_constexpr() ); +} diff --git a/libstdc++-v3/testsuite/23_containers/vector/bool/modifiers/insert/insert_range.cc b/libstdc++-v3/testsuite/23_containers/vector/bool/modifiers/insert/insert_range.cc new file mode 100644 index 00000000000..4f530466efe --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/vector/bool/modifiers/insert/insert_range.cc @@ -0,0 +1,94 @@ +// { dg-do compile { target c++23 } } + +#include +#include +#include +#include +#include + +template +constexpr void +do_test() +{ + using T = std::ranges::range_value_t; + T a[]{1,1,0,1,0,0,1,0,0}; + + auto eq = [](const std::vector& l, std::span r) { + if (l.size() != r.size()) + return false; + for (auto i = 0u; i < l.size(); ++i) + if (l[i] != r[i]) + return false; + return true; + }; + + std::vector v; + v.insert_range(v.begin(), Range(a, a+0)); + VERIFY( v.empty() ); + VERIFY( v.capacity() == 0 ); + v.insert_range(v.begin(), Range(a, a+4)); + VERIFY( eq(v, {a, a+4}) ); + v.clear(); + v.insert_range(v.begin(), Range(a, a+5)); + VERIFY( eq(v, {a+4, a+9}) ); + v.insert_range(v.begin(), Range(a, a+4)); + VERIFY( eq(v, a) ); + v.clear(); + v.shrink_to_fit(); + v.insert_range(v.begin(), Range(a, a+3)); + v.insert_range(v.end(), Range(a+6, a+9)); + v.insert_range(v.begin()+3, Range(a+3, a+6)); + VERIFY( eq(v, a) ); + v.resize(3); + v.insert_range(v.begin()+1, Range(a+4, a+9)); + v.insert_range(v.begin()+1, Range(a+1, a+3)); + v.resize(9); + VERIFY( eq(v, a) ); + v.insert_range(v.begin(), Range(a, a)); + VERIFY( eq(v, a) ); +} + +template +void +do_test_a() +{ + do_test>(); + do_test>(); +} + +bool +test_ranges() +{ + using namespace __gnu_test; + + do_test_a>(); + do_test_a>(); + do_test_a>(); + + do_test_a>(); + do_test_a>(); + do_test_a>(); + + do_test_a>(); + do_test_a>(); + do_test_a>(); + + do_test_a>(); + do_test_a>(); + + return true; +} + +constexpr bool +test_constexpr() +{ + // XXX: this doesn't test the non-forward_range code paths are constexpr. + do_test, std::allocator>; + return true; +} + +int main() +{ + test_ranges(); + static_assert( test_constexpr() ); +} diff --git a/libstdc++-v3/testsuite/23_containers/vector/cons/from_range.cc b/libstdc++-v3/testsuite/23_containers/vector/cons/from_range.cc new file mode 100644 index 00000000000..9c06e185b3f --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/vector/cons/from_range.cc @@ -0,0 +1,94 @@ +// { dg-do compile { target c++23 } } + +#include +#include +#include +#include +#include + +void +test_deduction_guide(long* p) +{ + __gnu_test::test_input_range r(p, p); + std::vector v(std::from_range, r); + static_assert(std::is_same_v>); + + using Alloc = __gnu_test::SimpleAllocator; + Alloc alloc; + std::vector v2(std::from_range, r, alloc); + static_assert(std::is_same_v>); +} + +template +constexpr void +do_test(Alloc alloc) +{ + using T = std::ranges::range_value_t; + T a[]{1,2,3,4,5,6,7,8,9}; + + auto eq = [](const std::vector& l, std::span r) { + if (l.size() != r.size()) + return false; + for (auto i = 0u; i < l.size(); ++i) + if (l[i] != r[i]) + return false; + return true; + }; + + std::vector v0(std::from_range, Range(a, a+0)); + VERIFY( v0.empty() ); + VERIFY( v0.get_allocator() == Alloc() ); + + std::vector v4(std::from_range, Range(a, a+4)); + VERIFY( eq(v4, {a, 4}) ); + VERIFY( v4.get_allocator() == Alloc() ); + + std::vector v9(std::from_range, Range(a, a+9), alloc); + VERIFY( eq(v9, {a, 9}) ); + VERIFY( v9.get_allocator() == alloc ); +} + +template +void +do_test_a() +{ + do_test(std::allocator()); + do_test(__gnu_test::uneq_allocator(42)); +} + +bool +test_ranges() +{ + using namespace __gnu_test; + + do_test_a>(); + do_test_a>(); + do_test_a>(); + + do_test_a>(); + do_test_a>(); + do_test_a>(); + + do_test_a>(); + do_test_a>(); + do_test_a>(); + + do_test_a>(); + do_test_a>(); + + return true; +} + +constexpr bool +test_constexpr() +{ + // XXX: this doesn't test the non-forward_range code paths are constexpr. + do_test, std::allocator>; + return true; +} + +int main() +{ + test_ranges(); + static_assert( test_constexpr() ); +} diff --git a/libstdc++-v3/testsuite/23_containers/vector/modifiers/append_range.cc b/libstdc++-v3/testsuite/23_containers/vector/modifiers/append_range.cc new file mode 100644 index 00000000000..6faa7a4d198 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/vector/modifiers/append_range.cc @@ -0,0 +1,83 @@ +// { dg-do compile { target c++23 } } + +#include +#include +#include +#include +#include + +template +constexpr void +do_test() +{ + using T = std::ranges::range_value_t; + T a[]{1,2,3,4,5,6,7,8,9}; + + auto eq = [](const std::vector& l, std::span r) { + if (l.size() != r.size()) + return false; + for (auto i = 0u; i < l.size(); ++i) + if (l[i] != r[i]) + return false; + return true; + }; + + Range r4(a, a+4); + Range r5(a+4, a+9); + + std::vector v; + v.append_range(r4); + VERIFY( eq(v, {a, 4}) ); + v.append_range(r5); // larger than v.capacity() + VERIFY( eq(v, a) ); + v.append_range(Range(a, a)); + VERIFY( eq(v, a) ); + v.clear(); + v.append_range(Range(a, a)); + VERIFY( v.empty() ); +} + +template +void +do_test_a() +{ + do_test>(); + do_test>(); +} + +bool +test_ranges() +{ + using namespace __gnu_test; + + do_test_a>(); + do_test_a>(); + do_test_a>(); + + do_test_a>(); + do_test_a>(); + do_test_a>(); + + do_test_a>(); + do_test_a>(); + do_test_a>(); + + do_test_a>(); + do_test_a>(); + + return true; +} + +constexpr bool +test_constexpr() +{ + // XXX: this doesn't test the non-forward_range code paths are constexpr. + do_test, std::allocator>; + return true; +} + +int main() +{ + test_ranges(); + static_assert( test_constexpr() ); +} diff --git a/libstdc++-v3/testsuite/23_containers/vector/modifiers/assign/assign_range.cc b/libstdc++-v3/testsuite/23_containers/vector/modifiers/assign/assign_range.cc new file mode 100644 index 00000000000..e28c883a1fa --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/vector/modifiers/assign/assign_range.cc @@ -0,0 +1,107 @@ +// { dg-do compile { target c++23 } } + +#include +#include +#include +#include +#include + +template +constexpr void +do_test() +{ + using T = std::ranges::range_value_t; + T a[]{1,2,3,4,5,6,7,8,9}; + + auto eq = [](const std::vector& l, std::span r) { + if (l.size() != r.size()) + return false; + for (auto i = 0u; i < l.size(); ++i) + if (l[i] != r[i]) + return false; + return true; + }; + + Range r4(a, a+4); + Range r9(a); + + // assign to empty vector + std::vector v; + v.assign_range(Range(a, a)); + VERIFY( v.empty() ); + VERIFY( v.capacity() == 0 ); + v.assign_range(r4); + VERIFY( eq(v, {a, 4}) ); + v.clear(); + v.assign_range(r9); // larger than v.capacity() + VERIFY( eq(v, a) ); + v.clear(); + v.assign_range(r4); // smaller than v.capacity() + VERIFY( eq(v, {a, 4}) ); + v.clear(); + v.assign_range(r9); // equal to v.capacity() + VERIFY( eq(v, a) ); + + // assign to non-empty vector + v.assign_range(r4); // smaller than size() + VERIFY( eq(v, {a, 4}) ); + v.assign_range(r9); // larger than size(), equal to capacity() + VERIFY( eq(v, a) ); + v.resize(1); + v.assign_range(r4); // larger than size(), smaller than capacity() + VERIFY( eq(v, {a, 4}) ); + v.clear(); + v.resize(4); + v.assign_range(r4); // equal to size(), smaller than capacity() + VERIFY( eq(v, {a, 4}) ); + v.shrink_to_fit(); + v.assign_range(r9); // larger than capacity() + VERIFY( eq(v, a) ); + v.assign_range(Range(a, a)); + VERIFY( v.empty() ); +} + +template +void +do_test_a() +{ + do_test>(); + do_test>(); +} + +bool +test_ranges() +{ + using namespace __gnu_test; + + do_test_a>(); + do_test_a>(); + do_test_a>(); + + do_test_a>(); + do_test_a>(); + do_test_a>(); + + do_test_a>(); + do_test_a>(); + do_test_a>(); + + do_test_a>(); + do_test_a>(); + + return true; +} + +constexpr bool +test_constexpr() +{ + // XXX: this doesn't test the non-forward_range code paths are constexpr. + do_test, std::allocator>; + return true; +} + +int main() +{ + test_ranges(); + static_assert( test_constexpr() ); +} diff --git a/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert/insert_range.cc b/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert/insert_range.cc new file mode 100644 index 00000000000..b81ce6971bb --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert/insert_range.cc @@ -0,0 +1,94 @@ +// { dg-do compile { target c++23 } } + +#include +#include +#include +#include +#include + +template +constexpr void +do_test() +{ + using T = std::ranges::range_value_t; + T a[]{1,2,3,4,5,6,7,8,9}; + + auto eq = [](const std::vector& l, std::span r) { + if (l.size() != r.size()) + return false; + for (auto i = 0u; i < l.size(); ++i) + if (l[i] != r[i]) + return false; + return true; + }; + + std::vector v; + v.insert_range(v.begin(), Range(a, a)); + VERIFY( v.empty() ); + VERIFY( v.capacity() == 0 ); + v.insert_range(v.begin(), Range(a, a+4)); + VERIFY( eq(v, {a, a+4}) ); + v.clear(); + v.insert_range(v.begin(), Range(a, a+5)); + VERIFY( eq(v, {a+4, a+9}) ); + v.insert_range(v.begin(), Range(a, a+4)); + VERIFY( eq(v, a) ); + v.clear(); + v.shrink_to_fit(); + v.insert_range(v.begin(), Range(a, a+3)); + v.insert_range(v.end(), Range(a+6, a+9)); + v.insert_range(v.begin()+3, Range(a+3, a+6)); + VERIFY( eq(v, a) ); + v.resize(3); + v.insert_range(v.begin()+1, Range(a+4, a+9)); + v.insert_range(v.begin()+1, Range(a+1, a+3)); + v.resize(9); + VERIFY( eq(v, a) ); + v.insert_range(v.begin() + 6, Range(a, a)); + VERIFY( eq(v, a) ); +} + +template +void +do_test_a() +{ + do_test>(); + do_test>(); +} + +bool +test_ranges() +{ + using namespace __gnu_test; + + do_test_a>(); + do_test_a>(); + do_test_a>(); + + do_test_a>(); + do_test_a>(); + do_test_a>(); + + do_test_a>(); + do_test_a>(); + do_test_a>(); + + do_test_a>(); + do_test_a>(); + + return true; +} + +constexpr bool +test_constexpr() +{ + // XXX: this doesn't test the non-forward_range code paths are constexpr. + do_test, std::allocator>; + return true; +} + +int main() +{ + test_ranges(); + static_assert( test_constexpr() ); +}