[Bug libstdc++/61347] New: std::distance(list.first(),list.end()) in O(1)

[Bug libstdc++/61347] New: std::distance(list.first(),list.end()) in O(1)

[glisse at gcc dot gnu.org]

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.

[Bug libstdc++/61347] std::distance(list.first(),list.end()) in O(1)

[redi at gcc dot gnu.org]

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

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2014-05-29
     Ever confirmed|0                           |1

--- Comment #1 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Great idea

[Bug libstdc++/61347] std::distance(list.first(),list.end()) in O(1)

[fdumont at gcc dot gnu.org]

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

François Dumont <fdumont at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |fdumont at gcc dot gnu.org

--- Comment #2 from François Dumont <fdumont at gcc dot gnu.org> ---
If you specialize std::distance for list iterators please do not forget to do
so also in debug mode otherwise operation will go back to O(N) in this mode.

Of course make sure that the ++l.end() == l.begin() won't be run on debug
iterators. It won't appreciate increment past the end iterator.
>From gcc-bugs-return-463253-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Sat Oct 04 10:18:50 2014
Return-Path: <gcc-bugs-return-463253-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 16209 invoked by alias); 4 Oct 2014 10:18:50 -0000
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-bugs.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-help@gcc.gnu.org>
Sender: gcc-bugs-owner@gcc.gnu.org
Delivered-To: mailing list gcc-bugs@gcc.gnu.org
Received: (qmail 15727 invoked by uid 55); 4 Oct 2014 10:18:45 -0000
From: "fxcoudert at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug fortran/36534] Bogus: '__convert_s1_s4' at (1) is obsolescent in fortran 95
Date: Sat, 04 Oct 2014 10:18:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: fortran
X-Bugzilla-Version: 4.4.0
X-Bugzilla-Keywords: diagnostic
X-Bugzilla-Severity: normal
X-Bugzilla-Who: fxcoudert at gcc dot gnu.org
X-Bugzilla-Status: ASSIGNED
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: fxcoudert at gcc dot gnu.org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields:
Message-ID: <bug-36534-4-j5mVicXsDm@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-36534-4@http.gcc.gnu.org/bugzilla/>
References: <bug-36534-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-SW-Source: 2014-10/txt/msg00274.txt.bz2
Content-length: 577

https://gcc.gnu.org/bugzilla/show_bug.cgi?id6534

--- Comment #12 from Francois-Xavier Coudert <fxcoudert at gcc dot gnu.org> ---
Author: fxcoudert
Date: Sat Oct  4 10:18:07 2014
New Revision: 215887

URL: https://gcc.gnu.org/viewcvs?rev!5887&root=gcc&view=rev
Log:
    PR fortran/36534

    * resolve.c (resolve_fl_procedure): Clean up obsolescence warning.
    * gfortran.dg/widechar_10.f90: New test.

Added:
    trunk/gcc/testsuite/gfortran.dg/widechar_10.f90
Modified:
    trunk/gcc/fortran/ChangeLog
    trunk/gcc/fortran/resolve.c
    trunk/gcc/testsuite/ChangeLog

[Bug libstdc++/61347] std::distance(list.first(),list.end()) in O(1)

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61347
Bug 61347 depends on bug 49561, which changed state.

Bug 49561 Summary: [C++0x] std::list::size complexity
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=49561

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|REOPENED                    |RESOLVED
         Resolution|---                         |FIXED

[Bug libstdc++/61347] std::distance(list.first(),list.end()) in O(1)

[glisse at gcc dot gnu.org]

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

--- Comment #3 from Marc Glisse <glisse at gcc dot gnu.org> ---
Author: glisse
Date: Mon Oct 13 10:00:27 2014
New Revision: 216142

URL: https://gcc.gnu.org/viewcvs?rev=216142&root=gcc&view=rev
Log:
2014-10-13  Marc Glisse  <marc.glisse@inria.fr>

    PR libstdc++/61347
    PR libstdc++/63345
    * include/bits/list.tcc (_List_base::_M_clear()): Delay cast so it
    isn't done for the sentinel.
    * include/bits/stl_list.h (_List_base::_M_size): Move...
    (_List_base::_List_impl::_M_node): ... here.
    (_List_base::_M_get_size(), _List_base::_M_set_size(size_t),
    _List_base::_M_inc_size(size_t), _List_base::_M_dec_size(size_t),
    _List_base::_M_node_count): Adapt to the move.
    * 23_containers/list/requirements/dr438/assign_neg.cc: Update
    line number.
    * 23_containers/list/requirements/dr438/constructor_1_neg.cc: Likewise.
    * 23_containers/list/requirements/dr438/constructor_2_neg.cc: Likewise.
    * 23_containers/list/requirements/dr438/insert_neg.cc: Likewise.


Modified:
    trunk/libstdc++-v3/ChangeLog
    trunk/libstdc++-v3/include/bits/list.tcc
    trunk/libstdc++-v3/include/bits/stl_list.h
   
trunk/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/assign_neg.cc
   
trunk/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/constructor_1_neg.cc
   
trunk/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/constructor_2_neg.cc
   
trunk/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/insert_neg.cc

[Bug libstdc++/61347] std::distance(list.first(),list.end()) in O(1)

[glisse at gcc dot gnu.org]

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

--- Comment #4 from Marc Glisse <glisse at gcc dot gnu.org> ---
Created attachment 35231
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=35231&action=edit
Overload of __distance

Here is one way to do it (I will probably protect the new code with
defined(__OPTIMIZE__) as well, if we keep __builtin_constant_p).

(Looking at the generated code, I was surprised to notice that _M_hook and
_M_unhook are in src, they seem rather small for that)

[Bug libstdc++/61347] std::distance(list.first(),list.end()) in O(1)

[glisse at gcc dot gnu.org]

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

--- Comment #5 from Marc Glisse <glisse at gcc dot gnu.org> ---
Author: glisse
Date: Tue Apr 14 11:02:48 2015
New Revision: 222082

URL: https://gcc.gnu.org/viewcvs?rev=222082&root=gcc&view=rev
Log:
2015-04-14  Marc Glisse  <marc.glisse@inria.fr>

    PR libstdc++/61347
    * include/bits/stl_iterator_base_funcs.h (_List_iterator,
    _List_const_iterator): Declare.
    (__distance): Declare new overloads for _List_iterator and
    _List_const_iterator.
    * include/bits/stl_list.h (__distance): New overloads for
    _List_iterator and _List_const_iterator.
    * testsuite/23_containers/list/61347.cc: New testcase.


Added:
    trunk/libstdc++-v3/testsuite/23_containers/list/61347.cc
Modified:
    trunk/libstdc++-v3/ChangeLog
    trunk/libstdc++-v3/include/bits/stl_iterator_base_funcs.h
    trunk/libstdc++-v3/include/bits/stl_list.h