On 24/03/25 10:19 +0100, Tomasz Kaminski wrote:
On Sat, Mar 22, 2025 at 9:40 PM Jonathan Wakely <jwak...@redhat.com> wrote:Unlike insert_range and assign_range, the append_range function does not have a precondition that the range doesn't overlap *this. That means we need to avoid relocating the existing elements until after copying from the range. This means I need to revert r15-8488-g3e1d760bf49d0e which made the from_range_t constructor use append_range, because the constructor can avoid the additional complexity needed by append_range. When relocating the existing elements in append_range we can use std::__relocate_a to do it more efficiently, if that's valid. std::vector<bool>::append_range needs similar treatment, although it's a bit simpler as we know that the elements are trivially copyable and so we don't need to worry about them throwing. assign_range doesn't allow overlapping ranges, so can be rewritten to be more efficient than calling append_range for the forward or sized range case. libstdc++-v3/ChangeLog: * include/bits/stl_bvector.h (vector::assign_range): More efficient implementation for forward/sized ranges. (vector::append_range): Handle potentially overlapping range. * include/bits/stl_vector.h (vector(from_range_t, R&&, Alloc)): Do not use append_range for non-sized input range case. (vector::append_range) (vector::append_range): Handle potentially overlapping range. * include/bits/vector.tcc (vector::insert_range): Forward range instead of moving it. * testsuite/23_containers/vector/bool/modifiers/insert/append_range.cc: Test overlapping ranges. * testsuite/23_containers/vector/modifiers/append_range.cc: * Likewise. --- Tested x86_64-linux. libstdc++-v3/include/bits/stl_bvector.h | 66 +++++-- libstdc++-v3/include/bits/stl_vector.h | 102 ++++++++++- libstdc++-v3/include/bits/vector.tcc | 2 +- .../bool/modifiers/insert/append_range.cc | 50 ++++++ .../vector/modifiers/append_range.cc | 164 ++++++++++++++++++ 5 files changed, 364 insertions(+), 20 deletions(-) diff --git a/libstdc++-v3/include/bits/stl_bvector.h b/libstdc++-v3/include/bits/stl_bvector.h index 2292eec54ad..14a0b0fdbb6 100644 --- a/libstdc++-v3/include/bits/stl_bvector.h +++ b/libstdc++-v3/include/bits/stl_bvector.h @@ -1031,8 +1031,22 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER assign_range(_Rg&& __rg) { static_assert(assignable_from<bool&, ranges::range_reference_t<_Rg>>); - clear(); - append_range(std::forward<_Rg>(__rg)); + if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>) + { + if (auto __n = size_type(ranges::distance(__rg))) + { + reserve(__n); + this->_M_impl._M_finish + = ranges::copy(std::forward<_Rg>(__rg), begin()).out;+ }+ else + clear(); + } + else + { + clear(); + append_range(std::forward<_Rg>(__rg));I think we could call emplace_back in the loop here, to avoid creating a temporary vector.
Yes, OK. Copying elements from the temporary vector into *this is cheap because it's just an array of unsigned long, but the same reasoning applies to growing and reallocating *this.
+ } } #endif @@ -1381,24 +1395,52 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER constexpr void append_range(_Rg&& __rg) { + // N.B. append_range(r) allows r to overlap with *this, + // e.g. it could be *this | views::filter(pred) | views::to_input + // and so we must not invalidate existing elements too soon. 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; + const auto __n = size_type(ranges::distance(__rg)); + const auto __sz = size(); + + // If there are no existing elements it's safe to allocate now. + if (__sz == 0) + reserve(__n); + + const auto __capacity = capacity(); + if ((__capacity - __sz) >= __n) + { + this->_M_impl._M_finish + = ranges::copy(std::forward<_Rg>(__rg), end()).out;+ return;+ } + + vector __tmp(get_allocator()); + __tmp.reserve(_M_check_len(__n, "vector::append_range")); + __tmp._M_impl._M_finish + = _M_copy_aligned(cbegin(), cend(), __tmp.begin()); + __tmp._M_impl._M_finish + = ranges::copy(std::forward<_Rg>(__rg), __tmp.end()).out; + swap(__tmp); } 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) + + // Fill up to the end of current capacity. + for (auto __free = capacity() - size(); + __first != __last && __free > 0; + ++__first, (void) --__free) emplace_back(*__first); - if (__first != __last) - { - ranges::subrange __rest(std::move(__first), __last); - append_range(vector(from_range, __rest, get_allocator())); - } + + if (__first == __last) + return; + + // Copy the rest of the range to a new vector. + ranges::subrange __rest(std::move(__first), __last); + vector __tmp(from_range, __rest, get_allocator()); + insert(end(), __tmp.begin(), __tmp.end()); } } #endif // ranges_to_container diff --git a/libstdc++-v3/include/bits/stl_vector.h b/libstdc++-v3/include/bits/stl_vector.h index 09fd53696d1..36fd5bcfce5 100644 --- a/libstdc++-v3/include/bits/stl_vector.h +++ b/libstdc++-v3/include/bits/stl_vector.h @@ -65,7 +65,7 @@ #if __cplusplus >= 202002L # include <compare> #endif -#if __cplusplus > 202002L +#if __glibcxx_ranges_to_container // C++ >= 23 # include <bits/ranges_algobase.h> // ranges::copy # include <bits/ranges_util.h> // ranges::subrange #endif @@ -771,7 +771,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER _Base::_M_append_range(__rg); } else - append_range(std::move(__rg)); + { + auto __first = ranges::begin(__rg); + const auto __last = ranges::end(__rg); + for (; __first != __last; ++__first) + emplace_back(*__first); + } } #endif @@ -1648,20 +1653,103 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER constexpr void append_range(_Rg&& __rg) { + // N.B. append_range(r) allows r to overlap with *this, + // e.g. it could be *this | views::filter(pred) | views::to_input + // and so we must not invalidate existing elements too soon. 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); + const auto __sz = size(); + + // If there are no existing elements it's safe to allocate now. + if (__sz == 0) + reserve(__n); + + const auto __capacity = capacity(); + if ((__capacity - __sz) >= __n) + { + _GLIBCXX_ASAN_ANNOTATE_GROW(__n); + _Base::_M_append_range(__rg); + _GLIBCXX_ASAN_ANNOTATE_GREW(__n); + return; + } + + const size_type __len = _M_check_len(__n, "vector::append_range"); + + pointer __old_start = this->_M_impl._M_start; + pointer __old_finish = this->_M_impl._M_finish; + + allocator_type& __a = _M_get_Tp_allocator(); + const pointer __start = this->_M_allocate(__len); + const pointer __mid = __start + __sz; + const pointer __back = __mid + __n; + _Guard_alloc __guard(__start, __len, *this); + std::__uninitialized_copy_a(ranges::begin(__rg), + ranges::end(__rg), + __mid, __a); + + if constexpr (_S_use_relocate()) + _S_relocate(__old_start, __old_finish, __start, __a); + else + { + // RAII type to destroy initialized elements. + struct _Guard_elts + { + pointer _M_first, _M_last; // Elements to destroy + _Tp_alloc_type& _M_alloc; + + constexpr + _Guard_elts(pointer __f, pointer __l, _Tp_alloc_type& __a) + : _M_first(__f), _M_last(__l), _M_alloc(__a) + { } + + constexpr + ~_Guard_elts() + { std::_Destroy(_M_first, _M_last, _M_alloc); } + + private: + _Guard_elts(const _Guard_elts&);Could you just delete the copy constructor, as we are in C++23.
Ah yes, this was copy&paste from other code that needs to be valid in C++98, but that isn't needed here.
+ }; + _Guard_elts __guard_elts{__mid, __back, __a}; + + std::__uninitialized_move_a(__old_start, __old_finish, + __start, __a); + + // Let old elements get destroyed by __guard_elts: + __guard_elts._M_first = __old_start; + __guard_elts._M_last = __old_finish; + } + + // Now give ownership of old storage to __guard: + __guard._M_storage = __old_start; + __guard._M_len = __capacity; + // Finally, take ownership of new storage: + this->_M_impl._M_start = __start; + this->_M_impl._M_finish = __back; + this->_M_impl._M_end_of_storage = __start + __len; } else { auto __first = ranges::begin(__rg); const auto __last = ranges::end(__rg); - for (; __first != __last; ++__first) + + // Fill up to the end of current capacity. + for (auto __free = capacity() - size(); + __first != __last && __free > 0; + ++__first, (void) --__free) emplace_back(*__first); + + if (__first == __last) + return; + + // Copy the rest of the range to a new vector. + vector __tmp(_M_get_Tp_allocator()); + for (; __first != __last; ++__first) + __tmp.emplace_back(*__first); + reserve(_M_check_len(__tmp.size(), "vector::append_range")); + ranges::subrange __r(std::make_move_iterator(__tmp.begin()), + std::make_move_iterator(__tmp.end())); + append_range(__r); // This will take the fast path above. } } #endif // ranges_to_container diff --git a/libstdc++-v3/include/bits/vector.tcc b/libstdc++-v3/include/bits/vector.tcc index acb2f5fca1e..f197278d52e 100644 --- a/libstdc++-v3/include/bits/vector.tcc +++ b/libstdc++-v3/include/bits/vector.tcc @@ -1094,7 +1094,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER return begin() + __ins_idx; } else - return insert_range(__pos, vector(from_range, std::move(__rg), + return insert_range(__pos, vector(from_range, std::forward<_Rg>(__rg), _M_get_Tp_allocator())); } #endif // ranges_to_container 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 index a35ed0f2026..bb103a47202 100644 --- 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 @@ -83,6 +83,56 @@ test_constexpr() { // XXX: this doesn't test the non-forward_range code paths are constexpr. do_test<std::span<short>, std::allocator<bool>>(); + + using I = std::vector<bool>::iterator; + std::vector<bool> vec(5); + + struct InputRange + { + + struct Sent { I end; }; + + struct Iter + { + using value_type = bool; + using difference_type = int; + constexpr explicit Iter(I i) : i(i) { } + constexpr Iter& operator++() { ++i; return *this; } + constexpr Iter operator++(int) { auto i = *this; ++i; return i; } + constexpr int operator*() const { return *i; } + constexpr bool operator==(const Iter&) const = default; + constexpr bool operator==(const Sent& s) const { return i == s.end; } + I i; + }; + + Iter iter; + Sent sent; + + constexpr InputRange(I f, I l) : iter{f}, sent{l} { } + constexpr Iter begin() const { return iter; } + constexpr Sent end() const { return sent; } + };Could we make viest::to_input available earier? Like in C++23?
We would need to give it a different name like __to_input_view, so this seemed like less effort (and it's only needed for a test). What would be useful is if __gnu_test::test_range etc. could be use in constexpr. Then this could just have used __gnu_test::test_input_range. Thanks for the review, I'll send a new patch.
