On Mon, Mar 24, 2025 at 1:08 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.
> ---
>
> Changed vector<bool, A>::assign_range to just use a loop for the
> non-sized input range case, instead of calling append_range.
>
> Changed private copy ctor to deleted move ctor in RAII type.
>
> Testing x86_64-linux now.
>
LGTM.
As a note reserving for empty vector:
+ // If there are no existing elements it's safe to allocate
now.
+ if (__sz == 0)
+ reserve(__n);
Will invalidate v.begin(), v.end(), so if the incoming range stored these
iterators as a range, and uses it internally, this will be broken.
If these iterator are saved before the call, this does not run into
re-entrancy.
We could change that to look if capacity is 0 (to optimize default_construct
+ append case), but I am fine with not supporting this case.
> libstdc++-v3/include/bits/stl_bvector.h | 69 ++++++--
> libstdc++-v3/include/bits/stl_vector.h | 101 ++++++++++-
> libstdc++-v3/include/bits/vector.tcc | 2 +-
> .../bool/modifiers/insert/append_range.cc | 50 ++++++
> .../vector/modifiers/append_range.cc | 164 ++++++++++++++++++
> 5 files changed, 366 insertions(+), 20 deletions(-)
>
> diff --git a/libstdc++-v3/include/bits/stl_bvector.h
> b/libstdc++-v3/include/bits/stl_bvector.h
> index 3ee15eaa938..5addab048c9 100644
> --- a/libstdc++-v3/include/bits/stl_bvector.h
> +++ b/libstdc++-v3/include/bits/stl_bvector.h
> @@ -1035,8 +1035,25 @@ _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();
> + auto __first = ranges::begin(__rg);
> + const auto __last = ranges::end(__rg);
> + for (; __first != __last; ++__first)
> + emplace_back(*__first);
> + }
> }
> #endif
>
> @@ -1385,24 +1402,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..7f0b62e9b93 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,102 @@ _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); }
> +
> + _Guard_elts(_Guard_elts&&) = delete;
> + };
> + _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; }
> + };
> + static_assert( std::ranges::input_range<InputRange> );
> + static_assert( ! std::ranges::forward_range<InputRange> );
> +
> + // Test input ranges
> + vec.resize(vec.capacity());
> + vec.append_range(InputRange(vec.begin(), vec.begin() + 3)); // no
> capacity
> + vec.reserve(vec.capacity() + 2);
> + vec.append_range(InputRange(vec.begin(), vec.begin() + 4)); // some
> capacity
> + vec.reserve(vec.capacity() + 6);
> + vec.append_range(InputRange(vec.begin(), vec.begin() + 5)); // enough
> capacity
> +
> + using R = std::ranges::subrange<I>;
> +
> + // Test forward ranges
> + vec.resize(vec.capacity());
> + vec.append_range(R(vec.begin(), vec.begin() + 3)); // no capacity
> + vec.reserve(vec.size() + 2);
> + vec.append_range(R(vec.begin(), vec.begin() + 4)); // some capacity
> + vec.reserve(vec.size() + 6);
> + vec.append_range(R(vec.begin(), vec.begin() + 5)); // enough capacity
> +
> return true;
> }
>
> diff --git
> a/libstdc++-v3/testsuite/23_containers/vector/modifiers/append_range.cc
> b/libstdc++-v3/testsuite/23_containers/vector/modifiers/append_range.cc
> index 5725cd2ad48..6bfe2047d1c 100644
> --- a/libstdc++-v3/testsuite/23_containers/vector/modifiers/append_range.cc
> +++ b/libstdc++-v3/testsuite/23_containers/vector/modifiers/append_range.cc
> @@ -82,16 +82,180 @@ test_ranges()
> return true;
> }
>
> +void
> +test_overlapping()
> +{
> + using __gnu_test::test_input_range;
> + using __gnu_test::test_forward_range;
> +
> + struct X {
> + unsigned* p;
> + constexpr X(int i = 0) : p(new unsigned(i)) { }
> + constexpr X(const X& m) : p(new unsigned(*m.p)) { }
> + constexpr X(X&& m) noexcept : p(m.p) { m.p = nullptr; }
> + constexpr ~X() { delete p; }
> + };
> +
> + std::vector<X> vec;
> + unsigned size = 5;
> + vec.reserve(size);
> + for (unsigned i = 0; i < size; ++i)
> + vec.emplace_back(i);
> +
> + // Append an input range that overlaps with vec.
> + {
> + __gnu_test::test_input_range<X> r(vec.data(), vec.data() + size);
> + vec.append_range(r);
> + VERIFY( vec.size() == 2 * size );
> + for (unsigned i = 0; i < size; ++i)
> + {
> + VERIFY( *vec[i].p == i );
> + VERIFY( *vec[i+size].p == i );
> + }
> + }
> +
> + size = vec.size() - 2;
> + vec.resize(size);
> + for (unsigned i = 0; i < size; ++i)
> + *vec[i].p = i;
> +
> + // Repeat with unused capacity in the vector.
> + {
> + __gnu_test::test_input_range<X> r(vec.data(), vec.data() + size);
> + vec.append_range(r);
> + VERIFY( vec.size() == 2 * size );
> + for (unsigned i = 0; i < size; ++i)
> + {
> + VERIFY( *vec[i].p == i );
> + VERIFY( *vec[i+size].p == i );
> + }
> + }
> +
> + size = vec.size() - 2;
> + vec.resize(size);
> + for (unsigned i = 0; i < size; ++i)
> + *vec[i].p = i;
> +
> + // Repeat with input range that doesn't overlap full vector.
> + {
> + __gnu_test::test_input_range<X> r(vec.data() + 1, vec.data() + 4);
> + vec.append_range(r);
> + VERIFY( vec.size() == size + 3 );
> + for (unsigned i = 0; i < size; ++i)
> + {
> + VERIFY( *vec[i].p == i );
> + if (i < 3)
> + VERIFY( *vec[i+size].p == i+1 );
> + }
> + }
> +
> + size = 5;
> + vec.resize(size);
> + for (unsigned i = 0; i < size; ++i)
> + *vec[i].p = i;
> +
> + // Append a forward range that overlaps with vec.
> + {
> + __gnu_test::test_forward_range<X> r(vec.data(), vec.data() + size);
> + vec.append_range(r);
> + VERIFY( vec.size() == 2 * size );
> + for (unsigned i = 0; i < size; ++i)
> + {
> + VERIFY( *vec[i].p == i );
> + VERIFY( *vec[i+size].p == i );
> + }
> + }
> +
> + size = vec.size() - 2;
> + vec.resize(size);
> + for (unsigned i = 0; i < size; ++i)
> + *vec[i].p = i;
> +
> + // Repeat with insufficient unused capacity in the vector.
> + {
> + __gnu_test::test_forward_range<X> r(vec.data(), vec.data() + size);
> + vec.append_range(r);
> + VERIFY( vec.size() == 2 * size );
> + for (unsigned i = 0; i < size; ++i)
> + {
> + VERIFY( *vec[i].p == i );
> + VERIFY( *vec[i+size].p == i );
> + }
> + }
> +
> + size = vec.size() / 2;
> + vec.resize(size);
> +
> + // Repeat with sufficient unused capacity in the vector.
> + {
> + __gnu_test::test_forward_range<X> r(vec.data(), vec.data() + size);
> + vec.append_range(r);
> + VERIFY( vec.size() == 2 * size );
> + for (unsigned i = 0; i < size; ++i)
> + {
> + VERIFY( *vec[i].p == i );
> + VERIFY( *vec[i+size].p == i );
> + }
> + }
> +}
> +
> constexpr bool
> test_constexpr()
> {
> // XXX: this doesn't test the non-forward_range code paths are
> constexpr.
> do_test<std::span<short>, std::allocator<int>>();
> +
> + std::vector<int> vec(5);
> +
> + struct InputRange
> + {
> + struct Sent { const void* end; };
> +
> + struct Iter
> + {
> + using value_type = int;
> + using difference_type = int;
> + constexpr explicit Iter(int* p) : ptr(p) { }
> + constexpr Iter& operator++() { ++ptr; return *this; }
> + constexpr Iter operator++(int) { auto i = *this; ++ptr; return i; }
> + constexpr int operator*() const { return *ptr; }
> + constexpr bool operator==(const Iter&) const = default;
> + constexpr bool operator==(const Sent& s) const { return ptr ==
> s.end; }
> + int* ptr;
> + };
> +
> + Iter iter;
> + Sent sent;
> +
> + constexpr InputRange(int* f, int* l) : iter{f}, sent{l} { }
> + constexpr Iter begin() const { return iter; }
> + constexpr Sent end() const { return sent; }
> + };
> + static_assert( std::ranges::input_range<InputRange> );
> + static_assert( ! std::ranges::forward_range<InputRange> );
> +
> + // Test input ranges
> + vec.resize(vec.capacity());
> + vec.append_range(InputRange(vec.data(), vec.data() + 3)); // no capacity
> + vec.reserve(vec.capacity() + 2);
> + vec.append_range(InputRange(vec.data(), vec.data() + 4)); // some
> capacity
> + vec.reserve(vec.capacity() + 6);
> + vec.append_range(InputRange(vec.data(), vec.data() + 5)); // enough
> capacity
> +
> + // Test forward ranges
> + vec.resize(vec.capacity());
> + vec.append_range(std::span<int>(vec)); // no capacity
> + vec.reserve(vec.size() + 2);
> + vec.append_range(std::span<int>(vec).subspan(1, 4)); // some capacity
> + vec.reserve(vec.size() + 6);
> + vec.append_range(std::span<int>(vec).subspan(1, 5)); // enough capacity
> +
> return true;
> }
>
> int main()
> {
> + test_overlapping();
> test_ranges();
> static_assert( test_constexpr() );
> }
> --
> 2.49.0
>
>
