[Bug libstdc++/100070] Standard library container iterator-pair constructors should check C++20 iterator concepts
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100070 --- Comment #11 from Jonathan Wakely --- https://wg21.link/p2408 is in this area, but doesn't touch the containers. https://wg21.link/p1206 solves the problem, although it's not as convenient as Barry asked for. You can construct a subrange from the new-style iterators and then pass that to the new container members that accept ranges.
[Bug libstdc++/100070] Standard library container iterator-pair constructors should check C++20 iterator concepts
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100070 Jonathan Wakely changed: What|Removed |Added See Also||https://gcc.gnu.org/bugzill ||a/show_bug.cgi?id=102181 --- Comment #10 from Jonathan Wakely --- (In reply to Jonathan Wakely from comment #4) > Barry suggested out-of-band that we could change std::__iterator_category to > determine the result based on the C++20 iterator concepts. That looks > promising. > > std::distance dispatches on the result of std::__iterator_category, and > doesn't care whether some meets all the Cpp17RandomAccessIterator > requirements, it only cares whether (last - first) is valid and efficient. I have a patch to do this for PR 102181 however the suggested direction for lwg 3197 is to require Cpp17InputIterator for std distance, and not Do The Right Thing for C++20 iterators. We could of course so it anyway as a valid interpretation of a precondition violation.
[Bug libstdc++/100070] Standard library container iterator-pair constructors should check C++20 iterator concepts
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100070 Patrick Palka changed: What|Removed |Added See Also||https://gcc.gnu.org/bugzill ||a/show_bug.cgi?id=100795 --- Comment #9 from Patrick Palka --- This seems to be related to the correctness bug PR100795: some of our ranges::algos (e.g. ranges::inplace_merge) are implemented as simple wrappers over the corresponding std::algo, but that breaks in cases where the std::algo has a minimum requirement on the range's iterator_category..
[Bug libstdc++/100070] Standard library container iterator-pair constructors should check C++20 iterator concepts
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100070 Patrick Palka changed: What|Removed |Added CC||ppalka at gcc dot gnu.org --- Comment #8 from Patrick Palka --- (In reply to Jonathan Wakely from comment #7) > Note to self/Patrick: > > Measure whether it helps to specialize transform_view's iterator so that > when _Base_iter is __normal_iterator we unwrap it and store a raw pointer. > > Also, I suspect the indirections in > > return std::__invoke(*_M_parent->_M_fun, *_M_current); > > are making the optimizer give up. > > We have an indirection to the parent to access the semi-regular box, which > has its own indirections. Maybe we could just get rid of the semi-regular > box for a function pointer and store a function pointer (i.e. decay_t) > directly. > > And maybe store a function pointer directly in the transform_view iterator, > so we don't need to go to the parent to get it on every dereference. Makes sense to me. I think we could then get rid of the iterator's _M_parent data member since it's used only to access the transformation function. And doing so would also reduce the size of the iterator in the case where the transformation function is an empty functor (and so [[no_unique_address]] could optimize away its storage). > > Barry pointed out that range-v3 elides the use of semi-regular box for some > cases, and he confirmed that storing a function pointer in the iterator > helps. FWIW we already elide the semiregular box for types which are semiregular, via a partial specialization of __box that is just a [[no_unique_wrapper]] for the underlying semiregular type.
[Bug libstdc++/100070] Standard library container iterator-pair constructors should check C++20 iterator concepts
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100070 --- Comment #7 from Jonathan Wakely --- Note to self/Patrick: Measure whether it helps to specialize transform_view's iterator so that when _Base_iter is __normal_iterator we unwrap it and store a raw pointer. Also, I suspect the indirections in return std::__invoke(*_M_parent->_M_fun, *_M_current); are making the optimizer give up. We have an indirection to the parent to access the semi-regular box, which has its own indirections. Maybe we could just get rid of the semi-regular box for a function pointer and store a function pointer (i.e. decay_t) directly. That would have the same syntax (i.e. operator*) to access it as the semi-regular box, but would be less abstraction to un-abstract. And maybe store a function pointer directly in the transform_view iterator, so we don't need to go to the parent to get it on every dereference. Barry pointed out that range-v3 elides the use of semi-regular box for some cases, and he confirmed that storing a function pointer in the iterator helps.
[Bug libstdc++/100070] Standard library container iterator-pair constructors should check C++20 iterator concepts
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100070
--- Comment #6 from Jonathan Wakely ---
I'm not sure we should make std::__iterator_category just return
std::__detail::__iter_concept, because that has a fallback of
random_access_iterator_tag and I keep forgetting why that is. And I don't think
it's what we want here.
So just:
--- a/libstdc++-v3/include/bits/stl_iterator_base_types.h
+++ b/libstdc++-v3/include/bits/stl_iterator_base_types.h
@@ -236,7 +236,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
inline _GLIBCXX_CONSTEXPR
typename iterator_traits<_Iter>::iterator_category
__iterator_category(const _Iter&)
-{ return typename iterator_traits<_Iter>::iterator_category(); }
+{
+#if __cpp_lib_concepts
+ if constexpr (random_access_iterator<_Iter>)
+ return random_access_iterator_tag{};
+ else if constexpr (bidirectional_iterator<_Iter>)
+ return bidirectional_iterator_tag{};
+ else if constexpr (forward_iterator<_Iter>)
+ return forward_iterator_tag{};
+ else
+#endif
+ return typename iterator_traits<_Iter>::iterator_category();
+}
///@}
[Bug libstdc++/100070] Standard library container iterator-pair constructors should check C++20 iterator concepts
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100070 --- Comment #5 from Jonathan Wakely --- If there is code that cares, we could always add std::__cpp17_iterator_category for the cases where we really care about the traditional category (or where we're forwarding the result of *i to user code which might care but we can't tell).
[Bug libstdc++/100070] Standard library container iterator-pair constructors should check C++20 iterator concepts
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100070 --- Comment #4 from Jonathan Wakely --- Barry suggested out-of-band that we could change std::__iterator_category to determine the result based on the C++20 iterator concepts. That looks promising. std::distance dispatches on the result of std::__iterator_category, and doesn't care whether some meets all the Cpp17RandomAccessIterator requirements, it only cares whether (last - first) is valid and efficient. We need to audit all the uses of std::__iterator_category to see whether any code in libstdc++ that gets used for std::forward_iterator_tag actually depends on the reference type being a reference. So far it looks like the answer is no.
[Bug libstdc++/100070] Standard library container iterator-pair constructors should check C++20 iterator concepts
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100070 --- Comment #3 from Jonathan Wakely --- So I think there is a *lot* work needed throughout the library to solve the general problem that the existing container code uses C++17 iterator categories and C++17 std::algos (not ranges::algos). We might be better off just waiting for a vector(range&&) constructor.
[Bug libstdc++/100070] Standard library container iterator-pair constructors should check C++20 iterator concepts
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100070
--- Comment #2 from Jonathan Wakely ---
This is a partial solution:
--- a/libstdc++-v3/include/bits/stl_vector.h
+++ b/libstdc++-v3/include/bits/stl_vector.h
@@ -654,6 +654,19 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
const allocator_type& __a = allocator_type())
: _Base(__a)
{
+#if __cpp_lib_concepts
+ if constexpr (forward_iterator<_InputIterator>)
+ {
+ size_type __n;
+ if constexpr (random_access_iterator<_InputIterator>)
+ __n = __last - __first;
+ else
+ __n = std::distance(__first, __last);
+ _M_range_initialize_n(__first, __last, __n);
+ return;
+ }
+ else
+#endif
_M_range_initialize(__first, __last,
std::__iterator_category(__first));
}
@@ -1577,7 +1590,15 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
_M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
std::forward_iterator_tag)
{
- const size_type __n = std::distance(__first, __last);
+ _M_range_initialize_n(__first, __last,
+ std::distance(__first, __last));
+ }
+
+ template
+ void
+ _M_range_initialize_n(_InputIterator __first, _InputIterator __last,
+ size_type __n)
+ {
this->_M_impl._M_start
= this->_M_allocate(_S_check_init_len(__n, _M_get_Tp_allocator()));
this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
This doubles the speed of the vector construction, but it's still slow because
it uses std::copy to copy the range elements into the vector, and std::copy
also dispatches on the iterator_category.
[Bug libstdc++/100070] Standard library container iterator-pair constructors should check C++20 iterator concepts
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100070 --- Comment #1 from Jonathan Wakely --- We want to do the same thing in insert and assign too. And in std::deque.
[Bug libstdc++/100070] Standard library container iterator-pair constructors should check C++20 iterator concepts
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100070 Jonathan Wakely changed: What|Removed |Added Status|UNCONFIRMED |NEW Ever confirmed|0 |1 Component|c++ |libstdc++ Last reconfirmed||2021-04-13
