public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
* [Bug libstdc++/61347] New: std::distance(list.first(),list.end()) in O(1)
@ 2014-05-28 22:23 glisse at gcc dot gnu.org
  2014-05-29  0:28 ` [Bug libstdc++/61347] " redi at gcc dot gnu.org
                   ` (5 more replies)
  0 siblings, 6 replies; 7+ messages in thread
From: glisse at gcc dot gnu.org @ 2014-05-28 22:23 UTC (permalink / raw)
  To: gcc-bugs

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61347

            Bug ID: 61347
           Summary: std::distance(list.first(),list.end()) in O(1)
           Product: gcc
           Version: 4.10.0
            Status: UNCONFIRMED
          Severity: enhancement
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: glisse at gcc dot gnu.org
        Depends on: 49561

Hello,

since C++11 is making list::size O(1) (never mind my opinion on that), I think
it would be nice to try and make std::distance(list.first(),list.end()) benefit
from that through an overload. Indeed, a number of algorithms take iterator
arguments and first compute their distance, without giving users a chance to
pass list.size() and avoid that O(n) traversal.

The way list is implemented, when we see a call distance(a,b) between list
iterators, we can test ++b==a (preferably not literally) and if it is true I
think it means that a is l.first() and b is l.end(). From l.end() we can
determine the address of the list l and call l.size(). However, instead of
using some kind of ugly offsetof, it may be nicer to change _List_Impl::_M_node
to a _List_node<size_t> and store the size there. I am filing this PR now
because it may influence the exact way PR 49561 will be fixed.

If the cost of testing for this special case seems excessive, I think it would
be ok to make it a __builtin_constant_p test, it should still catch a number of
cases.


^ permalink raw reply	[flat|nested] 7+ messages in thread
end of thread, other threads:[~2015-04-14 11:03 UTC | newest]

Thread overview: 7+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2014-05-28 22:23 [Bug libstdc++/61347] New: std::distance(list.first(),list.end()) in O(1) glisse at gcc dot gnu.org
2014-05-29  0:28 ` [Bug libstdc++/61347] " redi at gcc dot gnu.org
2014-10-04 10:00 ` fdumont at gcc dot gnu.org
2014-10-10 16:00 ` redi at gcc dot gnu.org
2014-10-13 10:01 ` glisse at gcc dot gnu.org
2015-04-05 10:17 ` glisse at gcc dot gnu.org
2015-04-14 11:03 ` glisse at gcc dot gnu.org

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).