[Bug libstdc++/49561] New: gcc does not meet the standard for std::list container

[Bug libstdc++/49561] New: gcc does not meet the standard for std::list container

[yoch.melka at gmail dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49561

           Summary: gcc does not meet the standard for std::list container
           Product: gcc
           Version: 4.5.2
            Status: UNCONFIRMED
          Severity: major
          Priority: P3
         Component: libstdc++
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: yoch.melka@gmail.com


I realized that the complexity of std::list::size() is O(n), not O(1).

This does not conform to standard. The standard states that size() function is
in constant time for alls containers. So, the behavior of gcc is not as
expected.

This also affects parts of std::list::splice() function, as mentioned in the
last drat (n3242 - 23.3.5.5):

[quote]
1 Since lists allow fast insertion and erasing from the middle of a list,
certain operations are provided specifically
for them.
2 list provides three splice operations that destructively move elements from
one list to another.[...]

void splice(const_iterator position, list<T,Allocator>& x) noexcept;
void splice(const_iterator position, list<T,Allocator>&& x) noexcept;
[...]
4 Effects: Inserts the contents of x before position and x becomes empty.
Pointers and references to
the moved elements of x now refer to those same elements but as members of
*this. Iterators referring
to the moved elements will continue to refer to their elements, but they now
behave as iterators into
*this, not into x.
5 Complexity: Constant time.

void splice(const_iterator position, list<T,Allocator>& x, const_iterator i)
noexcept;
void splice(const_iterator position, list<T,Allocator>&& x, const_iterator i)
noexcept;
6 Effects: Inserts an element pointed to by i from list x before position and
removes the element from
x. The result is unchanged if position == i or position == ++i. Pointers and
references to *i
continue to refer to this same element but as a member of *this. Iterators to
*i (including i itself)
continue to refer to the same element, but now behave as iterators into *this,
not into x.
[...]
8 Complexity: Constant time.

void splice(const_iterator position, list<T,Allocator>& x, const_iterator
first,
const_iterator last) noexcept;
void splice(const_iterator position, list<T,Allocator>&& x, const_iterator
first,
const_iterator last) noexcept;
9 Effects: Inserts elements in the range [first,last) before position and
removes the elements from
x.
[...]
11 Complexity: Constant time if &x == this; otherwise, linear time.
[/quote]

[Bug libstdc++/49561] gcc does not meet the standard for std::list container

[redi at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49561

--- Comment #1 from Jonathan Wakely <redi at gcc dot gnu.org> 2011-06-28 08:47:47 UTC ---
(In reply to comment #0)
> I realized that the complexity of std::list::size() is O(n), not O(1).
> 
> This does not conform to standard. The standard states that size() function is
> in constant time for alls containers. 

No, the current standard does not.

The C++0x draft does, but it's not yet a standard, and parts of it are not yet
implemented.

[Bug libstdc++/49561] [C++0x] std::list::size complexity

[paolo.carlini at oracle dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49561

Paolo Carlini <paolo.carlini at oracle dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2011.06.28 10:08:36
            Summary|gcc does not meet the       |[C++0x] std::list::size
                   |standard for std::list      |complexity
                   |container                   |
     Ever Confirmed|0                           |1
           Severity|major                       |normal

[Bug libstdc++/49561] [C++0x] std::list::size complexity

[blelbach at cct dot lsu.edu]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49561

Bryce Lelbach (wash) <blelbach at cct dot lsu.edu> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |blelbach at cct dot lsu.edu

--- Comment #2 from Bryce Lelbach (wash) <blelbach at cct dot lsu.edu> 2011-09-20 00:15:40 UTC ---
(In reply to comment #1)
> (In reply to comment #0)
> > I realized that the complexity of std::list::size() is O(n), not O(1).
> > 
> > This does not conform to standard. The standard states that size() function is
> > in constant time for alls containers. 
> 
> No, the current standard does not.
> 
> The C++0x draft does, but it's not yet a standard, and parts of it are not yet
> implemented.

The current standard is now C++11. 23.2.1, Table 96 explicitly states that the
size() method of Containers must execute in constant time.

Can this bug please be changed to confirmed? As of today (r178989),
std::list<>::size() is still O(N).

[Bug libstdc++/49561] [C++0x] std::list::size complexity

[paolo.carlini at oracle dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49561

--- Comment #3 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-09-20 00:28:37 UTC ---
It's already confirmed, NEW means confirmed.

[Bug libstdc++/49561] [C++0x] std::list::size complexity

[paolo.carlini at oracle dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49561

Paolo Carlini <paolo.carlini at oracle dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
         AssignedTo|unassigned at gcc dot       |paolo.carlini at oracle dot
                   |gnu.org                     |com

--- Comment #4 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-09-21 10:56:00 UTC ---
Maybe I can do this in time for 4.7, I don't make promises however, the changes
are conceptually simple but quite a few throughout the class. Of course then it
will definitely impossible to mix C++98 and C++11 std::lists, a data member
must be added in c++0x mode in order to implement this.

[Bug libstdc++/49561] [C++0x] std::list::size complexity

[paolo at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49561

--- Comment #5 from paolo at gcc dot gnu.org <paolo at gcc dot gnu.org> 2011-10-04 22:19:48 UTC ---
Author: paolo
Date: Tue Oct  4 22:19:44 2011
New Revision: 179528

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=179528
Log:
2011-10-04  Paolo Carlini  <paolo.carlini@oracle.com>

    PR libstdc++/49561
    * include/bits/stl_list.h (_List_base<>::_List_impl::_M_size):
    Add in C++0x mode.
    (_List_base<>::_List_impl, _List_base<>::_M_get_node,
    _List_base<>::_M_put_node, _List_base<>::_List_base(_List_base&&),
    list<>::size, list<>::swap, list<>::splice): Use it.
    (operator==(const list<>&, const list<>&)): Rewrite in C++0x mode.
    * include/bits/list.tcc (list<>::erase): Likewise.
    (list<>::merge): Adjust in C++0x mode.
    * testsuite/23_containers/list/requirements/dr438/assign_neg.cc:
    Adjust dg-error line number.
    * testsuite/23_containers/list/requirements/dr438/insert_neg.cc:
    Likewise.
    * testsuite/23_containers/list/requirements/dr438/
    constructor_1_neg.cc: Likewise.
    * testsuite/23_containers/list/requirements/dr438/
    constructor_2_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++/49561] [C++0x] std::list::size complexity

[paolo.carlini at oracle dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49561

Paolo Carlini <paolo.carlini at oracle dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED
   Target Milestone|---                         |4.7.0

--- Comment #6 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-10-04 22:22:39 UTC ---
Done. If you can, please stress std::list in C++0x mode in order to shake
possible bugs related to the O(1) size in time for the 4.7.0 release.

[Bug libstdc++/49561] [C++0x] std::list::size complexity

[blelbach at cct dot lsu.edu]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49561

--- Comment #7 from Bryce Lelbach (wash) <blelbach at cct dot lsu.edu> 2011-10-04 23:06:01 UTC ---
Thanks - I'll give it a whirl!

[Bug libstdc++/49561] [C++0x] std::list::size complexity

[foom at fuhm dot net]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49561

foom at fuhm dot net changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |foom at fuhm dot net

--- Comment #8 from foom at fuhm dot net 2011-10-07 01:26:28 UTC ---
This change seems like it might be the first major incompatibility added to
gcc's c++0x mode (at least, things appeared to work before, maybe that was just
luck).

I guess it will now be dangerous to even load a shared lib compiled with
--std=c++0x into the same executable as C++ code compiled in the default c++03
mode, because of the potential for the exported weak symbols from out-of-line
std::list functions compiled for one layout to be used on a structure defined
with the other layout in the other shared object. Even when no c++ objects are
ever passed from one shared lib to the other.

This seems like a particularly bad failure mode to have, especially considering
also bug 36022 (invalid), since it's by design difficult to *not* export the
symbols even if you try.

I understand that the versioned namespaces feature is supposed to help with
this sort of issue; is there any plan to use it to give the c++0x std::list
object a different mangled name than the c++03 std::list object?

[Bug libstdc++/49561] [C++0x] std::list::size complexity

[redi at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49561

--- Comment #9 from Jonathan Wakely <redi at gcc dot gnu.org> 2011-10-07 01:36:02 UTC ---
(In reply to comment #8)
> I guess it will now be dangerous to even load a shared lib compiled with
> --std=c++0x into the same executable as C++ code compiled in the default c++03
> mode,

It was already an ODR violation for some code, see PR 45093

There are no promises of interoperability between -std=c++98 and -std=c++0x

[Bug libstdc++/49561] [C++0x] std::list::size complexity

[paolo.carlini at oracle dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49561

--- Comment #10 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-10-07 01:37:34 UTC ---
I can confirm it was just luck, really.

[Bug libstdc++/49561] [C++0x] std::list::size complexity

[paolo at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49561

--- Comment #11 from paolo at gcc dot gnu.org <paolo at gcc dot gnu.org> 2012-07-03 00:47:23 UTC ---
Author: paolo
Date: Tue Jul  3 00:47:17 2012
New Revision: 189185

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=189185
Log:
2012-07-02  Paolo Carlini  <paolo.carlini@oracle.com>

    Revert:
    2011-10-04  Paolo Carlini  <paolo.carlini@oracle.com>

    PR libstdc++/49561
    * include/bits/stl_list.h (_List_base<>::_List_impl::_M_size):
    Add in C++0x mode.
    (_List_base<>::_List_impl, _List_base<>::_M_get_node,
    _List_base<>::_M_put_node, _List_base<>::_List_base(_List_base&&),
    list<>::size, list<>::swap, list<>::splice): Use it.
    (operator==(const list<>&, const list<>&)): Rewrite in C++0x mode.
    * include/bits/list.tcc (list<>::erase): Likewise.
    (list<>::merge): Adjust in C++0x mode.
    * testsuite/23_containers/list/requirements/dr438/assign_neg.cc:
    Adjust dg-error line number.
    * testsuite/23_containers/list/requirements/dr438/insert_neg.cc:
    Likewise.
    * testsuite/23_containers/list/requirements/dr438/
    constructor_1_neg.cc: Likewise.
    * testsuite/23_containers/list/requirements/dr438/
    constructor_2_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++/49561] [C++0x] std::list::size complexity

[paolo at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49561

--- Comment #12 from paolo at gcc dot gnu.org <paolo at gcc dot gnu.org> 2012-07-03 01:37:53 UTC ---
Author: paolo
Date: Tue Jul  3 01:37:48 2012
New Revision: 189186

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=189186
Log:
2012-07-02  Paolo Carlini  <paolo.carlini@oracle.com>

    Revert:
    2011-10-04  Paolo Carlini  <paolo.carlini@oracle.com>

    PR libstdc++/49561
    * include/bits/stl_list.h (_List_base<>::_List_impl::_M_size):
    Add in C++0x mode.
    (_List_base<>::_List_impl, _List_base<>::_M_get_node,
    _List_base<>::_M_put_node, _List_base<>::_List_base(_List_base&&),
    list<>::size, list<>::swap, list<>::splice): Use it.
    (operator==(const list<>&, const list<>&)): Rewrite in C++0x mode.
    * include/bits/list.tcc (list<>::erase): Likewise.
    (list<>::merge): Adjust in C++0x mode.
    * testsuite/23_containers/list/requirements/dr438/assign_neg.cc:
    Adjust dg-error line number.
    * testsuite/23_containers/list/requirements/dr438/insert_neg.cc:
    Likewise.
    * testsuite/23_containers/list/requirements/dr438/
    constructor_1_neg.cc: Likewise.
    * testsuite/23_containers/list/requirements/dr438/
    constructor_2_neg.cc: Likewise.

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

[Bug libstdc++/49561] [C++0x] std::list::size complexity

[paolo.carlini at oracle dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49561

Paolo Carlini <paolo.carlini at oracle dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|RESOLVED                    |REOPENED
         Resolution|FIXED                       |
         AssignedTo|paolo.carlini at oracle dot |unassigned at gcc dot
                   |com                         |gnu.org

--- Comment #13 from Paolo Carlini <paolo.carlini at oracle dot com> 2012-07-03 01:40:12 UTC ---
Patch reverted, thus in C++11 mode size() is back to O(n) but std::list can
interoperate with the C++98 version of it.

[Bug libstdc++/49561] [C++0x] std::list::size complexity

[blelbach at cct dot lsu.edu]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49561

--- Comment #14 from Bryce Lelbach (wash) <blelbach at cct dot lsu.edu> 2012-07-03 03:35:31 UTC ---
(In reply to comment #13)
> Patch reverted, thus in C++11 mode size() is back to O(n) but std::list can
> interoperate with the C++98 version of it.

Why has this been reverted? If std::list<>::size() is not O(1), then GCC's
C++11 standard library is not compliant with the C++11 international standard.
I have personally spoken with multiple members of the standard body and
confirmed that this behavior is REQUIRED by the C++11 standard.

Please re-apply this patch for C++11 mode, or state somewhere in the GCC docs
that GCC is not compliant with the C++11 standard. In the C++03 and C++98
standards, it was highly suggested that compiler vendors implement
std::list<>::size() as O(1).

I understand this is a breaking change, but honestly, the C++ standard has been
suggesting the O(1) implementation for over a decade, and the GCC standard
library developers have chosen to implement different behavior. You've had many
years of warning about this.

(In reply to comment #10)
> I can confirm it was just luck, really.

^ Paolo, this is correct. I think it's a really, really bad idea for any
particular vendor to cherrypick elements of an ISO standard to implement. If
you feel that the C++11 standard is wrong to require an O(1) implementation,
please file a standard defect (I'm afraid you can expect me to fight it).
Otherwise, I'd like to ask that you please reconsider applying this patch.

[Bug libstdc++/49561] [C++0x] std::list::size complexity

[blelbach at cct dot lsu.edu]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49561

--- Comment #15 from Bryce Lelbach (wash) <blelbach at cct dot lsu.edu> 2012-07-03 03:38:52 UTC ---
Also, didn't this already make it into the 4.7 release? Wouldn't reverting it
now just cause incompatibilities with 4.7 and both older and newer releases?

[Bug libstdc++/49561] [C++0x] std::list::size complexity

[redi at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49561

--- Comment #16 from Jonathan Wakely <redi at gcc dot gnu.org> 2012-07-03 08:31:18 UTC ---
(In reply to comment #14)
> (In reply to comment #13)
> > Patch reverted, thus in C++11 mode size() is back to O(n) but std::list can
> > interoperate with the C++98 version of it.
> 
> Why has this been reverted? If std::list<>::size() is not O(1), then GCC's
> C++11 standard library is not compliant with the C++11 international standard.
> I have personally spoken with multiple members of the standard body and
> confirmed that this behavior is REQUIRED by the C++11 standard.

Yes, we're well aware of that, thanks.

This patch made c++98 and c++11 code incompatible and is causing serious
problems for distros.

You've lived with O(n) size for 15 years, you can live with it for a while
longer until libstdc++'s ABI changes.

> Please re-apply this patch for C++11 mode, or state somewhere in the GCC docs
> that GCC is not compliant with the C++11 standard. In the C++03 and C++98
> standards, it was highly suggested that compiler vendors implement
> std::list<>::size() as O(1).
>
> I understand this is a breaking change, but honestly, the C++ standard has been
> suggesting the O(1) implementation for over a decade, and the GCC standard
> library developers have chosen to implement different behavior. You've had many
> years of warning about this.

You seem to think we were taken by surprise, that has nothing to do with it.
GCC has maintained ABI compatibility since version 3.4, including between c++98
and c++11 mode in most cases. This change broke that and caused a lot of
problems in real systems (not just "you don't implement the standard!") and has
been reverted until the entire library ABI gets updated at a later date.

> (In reply to comment #10)
> > I can confirm it was just luck, really.
> 
> ^ Paolo, this is correct. I think it's a really, really bad idea for any
> particular vendor to cherrypick elements of an ISO standard to implement. If
> you feel that the C++11 standard is wrong to require an O(1) implementation,
> please file a standard defect (I'm afraid you can expect me to fight it).
> Otherwise, I'd like to ask that you please reconsider applying this patch.

Calm down. Noone thinks it's wrong, but maintaining ABI compatibility has been
decided to be more important for the current releases. See the mailing lists
for more information.

[Bug libstdc++/49561] [C++0x] std::list::size complexity

[redi at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49561

--- Comment #17 from Jonathan Wakely <redi at gcc dot gnu.org> 2012-07-03 08:34:51 UTC ---
(In reply to comment #15)
> Also, didn't this already make it into the 4.7 release? Wouldn't reverting it
> now just cause incompatibilities with 4.7 and both older and newer releases?

Yes. But 4.7.0 and 4.7.1 are already incompatible with older releases. The
maintainers have taken the decision to restore compatibility with older
releases.

We plan to try and reimplement the change in a cleaner way asap.

[Bug libstdc++/49561] [C++0x] std::list::size complexity

[redi at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49561

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |ABI

--- Comment #18 from Jonathan Wakely <redi at gcc dot gnu.org> 2012-08-22 19:47:03 UTC ---
setting ABI keyword as this can't be properly fixed without an incompatible
change

[Bug libstdc++/49561] [C++0x] std::list::size complexity

[pinskia at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49561

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.7.0                       |---

[Bug libstdc++/49561] [C++0x] std::list::size complexity

[redi at gcc dot gnu.org]

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

--- Comment #19 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Author: redi
Date: Fri Oct 10 15:33:57 2014
New Revision: 216094

URL: https://gcc.gnu.org/viewcvs?rev=216094&root=gcc&view=rev
Log:
    PR libstdc++/49561
    * acinclude.m4 (GLIBCXX_ENABLE_LIBSTDCXX_CXX11_ABI): Define.
    * configure.ac: Use GLIBCXX_ENABLE_LIBSTDCXX_CXX11_ABI.
    * configure: Regenerate.
    * include/Makefile.am (stamp-cxx11-abi): New target.
    (c++config.h): Set _GLIBCXX_USE_CXX11_ABI macro.
    * include/Makefile.in: Regenerate.
    * include/bits/c++config: Add _GLIBCXX_USE_CXX11_ABI placeholder and
    define _GLIBCXX_DEFAULT_ABI_TAG.
    * include/bits/list.tcc (list::emplace(const_iterator, _Args&...)):
    Increment size.
    (list::emplace(const_iterator, const value_type&)): Likewise.
    (list::merge(list&), list::merge(list&, _StrictWeakOrdering)): Adjust
    list sizes.
    * include/bits/stl_list.h (_List_base, list): Add ABI tag macro.
    (_List_base::_M_size): New data member in cxx11 ABI mode.
    (_List_base::_S_distance(_List_node_base*, _List_node_base*)): New
    function.
    (_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_distance, _List_base::_M_node_count): New functions for
    accessing list size correctly for the ABI mode.
    (_List_base::_List_base(_List_base&&)): Copy size and reset source.
    (_List_base::_M_init()): Initialize size member.
    (list::size()): Use _List_base::_M_node_count.
    (list::swap(list&)): Swap sizes.
    (list::splice(iterator, list&)): Update sizes.
    (list::splice(iterator, list&, iterator)): Likewise.
    (list::insert(iterator, const value_type&)): Update size.
    (list::insert(iterator, _Args&&...)): Likewise.
    (list::_M_erase(iterator)): Likewise.
    * testsuite/23_containers/list/requirements/dr438/assign_neg.cc:
    Adjust.
    * testsuite/23_containers/list/requirements/dr438/constructor_1_neg.cc:
    Adjust.
    * testsuite/23_containers/list/requirements/dr438/constructor_2_neg.cc:
    Adjust.
    * testsuite/23_containers/list/requirements/dr438/insert_neg.cc:
    Adjust.
    * testsuite/ext/profile/mutex_extensions_neg.cc: Adjust.

Modified:
    trunk/libstdc++-v3/ChangeLog
    trunk/libstdc++-v3/acinclude.m4
    trunk/libstdc++-v3/configure
    trunk/libstdc++-v3/configure.ac
    trunk/libstdc++-v3/include/Makefile.am
    trunk/libstdc++-v3/include/Makefile.in
    trunk/libstdc++-v3/include/bits/c++config
    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
    trunk/libstdc++-v3/testsuite/ext/profile/mutex_extensions_neg.cc

[Bug libstdc++/49561] [C++0x] std::list::size complexity

[redi at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|REOPENED                    |RESOLVED
         Resolution|---                         |FIXED
   Target Milestone|---                         |5.0

--- Comment #20 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Fixed for 5.0

[Bug libstdc++/49561] [C++0x] std::list::size complexity

[redi at gcc dot gnu.org]

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

--- Comment #21 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Author: redi
Date: Fri Oct 10 16:14:52 2014
New Revision: 216097

URL: https://gcc.gnu.org/viewcvs?rev=216097&root=gcc&view=rev
Log:
    PR libstdc++/49561
    * acinclude.m4 (GLIBCXX_ENABLE_LIBSTDCXX_CXX11_ABI): Define.
    * configure.ac: Use GLIBCXX_ENABLE_LIBSTDCXX_CXX11_ABI.
    * configure: Regenerate.
    * include/Makefile.am (stamp-cxx11-abi): New target.
    (c++config.h): Set _GLIBCXX_USE_CXX11_ABI macro.
    * include/Makefile.in: Regenerate.
    * include/bits/c++config: Add _GLIBCXX_USE_CXX11_ABI placeholder and
    define _GLIBCXX_DEFAULT_ABI_TAG.
    * include/bits/list.tcc (list::emplace(const_iterator, _Args&...)):
    Increment size.
    (list::emplace(const_iterator, const value_type&)): Likewise.
    (list::merge(list&), list::merge(list&, _StrictWeakOrdering)): Adjust
    list sizes.
    * include/bits/stl_list.h (_List_base, list): Add ABI tag macro.
    (_List_base::_M_size): New data member in cxx11 ABI mode.
    (_List_base::_S_distance(_List_node_base*, _List_node_base*)): New
    function.
    (_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_distance, _List_base::_M_node_count): New functions for
    accessing list size correctly for the ABI mode.
    (_List_base::_List_base(_List_base&&)): Copy size and reset source.
    (_List_base::_M_init()): Initialize size member.
    (list::size()): Use _List_base::_M_node_count.
    (list::swap(list&)): Swap sizes.
    (list::splice(iterator, list&)): Update sizes.
    (list::splice(iterator, list&, iterator)): Likewise.
    (list::insert(iterator, const value_type&)): Update size.
    (list::insert(iterator, _Args&&...)): Likewise.
    (list::_M_erase(iterator)): Likewise.
    * testsuite/23_containers/list/requirements/dr438/assign_neg.cc:
    Adjust.
    * testsuite/23_containers/list/requirements/dr438/constructor_1_neg.cc:
    Adjust.
    * testsuite/23_containers/list/requirements/dr438/constructor_2_neg.cc:
    Adjust.
    * testsuite/23_containers/list/requirements/dr438/insert_neg.cc:
    Adjust.
    * testsuite/ext/profile/mutex_extensions_neg.cc: Adjust.
# End of auto-generated commit message
Fix date and whitespace in libstdc++-v3/ChangeLog

Modified:
    trunk/libstdc++-v3/ChangeLog