public inbox for gcc-bugs@sourceware.org help / color / mirror / Atom feed
From: "hewillk at gmail dot com" <gcc-bugzilla@gcc.gnu.org> To: gcc-bugs@gcc.gnu.org Subject: [Bug libstdc++/100664] New: ranges::drop_view fails to meet its complexity requirements Date: Wed, 19 May 2021 01:44:52 +0000 [thread overview] Message-ID: <bug-100664-4@http.gcc.gnu.org/bugzilla/> (raw) https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100664 Bug ID: 100664 Summary: ranges::drop_view fails to meet its complexity requirements Product: gcc Version: 12.0 Status: UNCONFIRMED Severity: normal Priority: P3 Component: libstdc++ Assignee: unassigned at gcc dot gnu.org Reporter: hewillk at gmail dot com Target Milestone: --- Hi, in ranges#L2043, the _S_needs_cached_begin of reverse_view is defined as: static constexpr bool _S_needs_cached_begin = !(random_access_range<const _Vp> && sized_range<const _Vp>); I think this definition is insufficient, because there may be a non-simple_view V that can satisfy random_access_range<const _Vp> && sized_range<const _Vp> but not random_access_range<_Vp> && sized_range<_Vp>, in this case, the complexity of ranges::next would be O(n). There is no such view in the standard library, but it can be easily implemented: (https://godbolt.org/z/oxY4e77br) template <view V> struct common_non_const_view : view_interface<common_non_const_view<V>> { private: using I = iterator_t<V>; using S = sentinel_t<V>; V base_ = V(); public: common_non_const_view() = default; constexpr common_non_const_view(V base) : base_(std::move(base)) {} constexpr auto begin() { return std::common_iterator<I, S>{ranges::begin(base_)}; } constexpr auto begin() const requires ranges::range<const V> { return std::ranges::begin(base_); } constexpr auto end() { return std::common_iterator<I, S>{ranges::end(base_)}; } constexpr auto end() const requires ranges::range<const V> { return ranges::end(base_); } constexpr auto size() requires sized_range<V> { return ranges::size(base_); } constexpr auto size() const requires sized_range<const V> { return ranges::size(base_); } }; subrange sub(std::counted_iterator(views::iota(0).begin(), 42), std::default_sentinel); const common_non_const_view cr{sub}; static_assert(random_access_range<decltype(cr)>); static_assert(sized_range<decltype(cr)>); common_non_const_view r{sub}; static_assert(!random_access_range<decltype(r)>); static_assert(forward_range<decltype(r)>); static_assert(sized_range<decltype(r)>); The above *const* common_non_const_view models random_access_range and sized_range, but the non-const one only models sized_range. Since it also models forward_range, we still need to cache the results of ranges::next() in the begin() of drop_view, just as says in [[range.drop#view-4]]: auto drop = r | std::views::drop(41); static_assert(forward_range<decltype(drop)>); auto it = drop.begin(); // need cached
next reply other threads:[~2021-05-19 1:44 UTC|newest] Thread overview: 3+ messages / expand[flat|nested] mbox.gz Atom feed top 2021-05-19 1:44 hewillk at gmail dot com [this message] 2021-05-19 1:45 ` [Bug libstdc++/100664] " hewillk at gmail dot com 2021-05-23 4:50 ` hewillk at gmail dot com
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=bug-100664-4@http.gcc.gnu.org/bugzilla/ \ --to=gcc-bugzilla@gcc.gnu.org \ --cc=gcc-bugs@gcc.gnu.org \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: linkBe sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).